Python - Überprüfen der Listenmonotonie

81

Was wäre ein effizienter und pythonischer Weg, um die Monotonie der Liste zu überprüfen?
dh dass es monoton ansteigende oder abnehmende Werte hat?

Beispiele:

[0, 1, 2, 3, 3, 4]   # This is a monotonically increasing list
[4.3, 4.2, 4.2, -2]  # This is a monotonically decreasing list
[2, 3, 1]            # This is neither
Jonathan
quelle
5
Es ist besser, die Begriffe "streng steigend" oder "nicht abnehmend" zu verwenden, um Unklarheiten auszuschließen (und auf ähnliche Weise ist es besser, "positiv" zu vermeiden und stattdessen entweder "nicht negativ" oder "streng positiv" zu verwenden)
6502
13
@ 6502 Der Begriff monoton wird entweder als nicht ansteigender oder nicht abnehmender Satz geordneter Werte definiert, sodass die Frage keine Mehrdeutigkeit aufwies.
Autoplektischer
Wenn Sie den Datenteil mit einer gewissen Monotonie
extrahieren möchten,

Antworten:

160

Es ist besser, mehrdeutige Begriffe wie "Erhöhen" oder "Verringern" zu vermeiden, da nicht klar ist, ob Gleichheit akzeptabel ist oder nicht. Sie sollten immer entweder "nicht ansteigend" (eindeutig Gleichheit wird akzeptiert) oder "streng abnehmend" (eindeutig Gleichheit wird NICHT akzeptiert) verwenden.

def strictly_increasing(L):
    return all(x<y for x, y in zip(L, L[1:]))

def strictly_decreasing(L):
    return all(x>y for x, y in zip(L, L[1:]))

def non_increasing(L):
    return all(x>=y for x, y in zip(L, L[1:]))

def non_decreasing(L):
    return all(x<=y for x, y in zip(L, L[1:]))

def monotonic(L):
    return non_increasing(L) or non_decreasing(L)
6502
quelle
14
Dies ist klarer, idiomatischer Python-Code, und seine Komplexität ist O (n), wobei die Sortierantworten alle O (n log n) sind. Eine ideale Antwort würde die Liste nur einmal durchlaufen, damit sie auf jedem Iterator funktioniert. Dies ist jedoch normalerweise gut genug und bei weitem die beste Antwort unter den bisherigen. (Ich würde eine Single-Pass-Lösung anbieten, aber das OP, das eine Antwort vorzeitig akzeptiert, zügelt jeden Drang, den ich dazu haben könnte ...)
Glenn Maynard
2
Nur aus Neugier hat Ihre Implementierung gegen die Verwendung von sortiert getestet. Ihre ist eindeutig viel langsamer [Ich habe L = Bereich (10000000) verwendet]. Es scheint, dass die Komplexität von allem O (n) ist, und ich konnte keine Implementierung von zip finden.
Sternchen
4
Sortieren ist spezialisiert, wenn die Liste bereits sortiert ist. Haben Sie die Geschwindigkeit mit einer zufällig gemischten Liste versucht? Beachten Sie auch, dass Sie bei der Sortierung nicht zwischen streng ansteigend und nicht abnehmend unterscheiden können. Bedenken Sie auch, dass Sie mit Python 2.x itertools.izipanstelle von zipeinen frühen Exit erhalten können (in Python 3 zipfunktioniert dies bereits wie ein Iterator)
6502
3
@ 6502: nur eine Funktion erforderlich: Importoperator; def monoton (L, op): Alle (op (x, y) für x, y in zip (L, L [1:])) zurückgeben und dann einfach eingeben, was Sie wollen: operator.le oder .ge oder was auch immer
Akira
5
zip und der Slice-Operator geben beide ganze Listen zurück, wodurch die Verknüpfungsfähigkeiten von all () vermieden werden. Dies könnte durch die Verwendung von itertools.izip und itertools.islice erheblich verbessert werden, da entweder eine strikte Erhöhung oder eine strikte Verringerung der Verknüpfung sehr früh fehlschlagen sollte.
Hugh Bothwell
36

Wenn Sie große Listen mit Zahlen haben, ist es möglicherweise am besten, numpy zu verwenden, und wenn Sie:

import numpy as np

def monotonic(x):
    dx = np.diff(x)
    return np.all(dx <= 0) or np.all(dx >= 0)

sollte den Trick machen.

Autoplektisch
quelle
Beachten Sie, dass dx [0] np.nan ist. Möglicherweise möchten Sie Folgendes verwenden: dx = np.diff (x) [1:], um daran vorbei zu springen. Ansonsten geben die Aufrufe von np.all () zumindest für mich immer False zurück.
Ryan
@ Ryan, warum dx[0]sollte NaN? Was ist Ihr Eingabearray?
DilithiumMatrix
1
N / m, ich dachte, dass np.diff()das erste Element NaNso gemacht wurde, dass die Form der Ausgabe mit der Eingabe übereinstimmte, aber das war tatsächlich ein anderer Code, der mich so biss. :)
Ryan
24
import itertools
import operator

def monotone_increasing(lst):
    pairs = zip(lst, lst[1:])
    return all(itertools.starmap(operator.le, pairs))

def monotone_decreasing(lst):
    pairs = zip(lst, lst[1:])
    return all(itertools.starmap(operator.ge, pairs))

def monotone(lst):
    return monotone_increasing(lst) or monotone_decreasing(lst)

Dieser Ansatz befindet sich O(N)in der Länge der Liste.

Michael J. Barber
quelle
3
Die richtige (TM) Lösung IMO. Funktionsparadigma für den Sieg!
Mike3996
2
Warum itertools anstelle von einfachen Generatoren verwenden?
6502
3
Funktionale Paradigmen sind in Python normalerweise nicht "der Gewinn".
Glenn Maynard
@ 6502 Gewohnheit, meistens. Auf der anderen Seite mapwird hier genau die Abstraktion benötigt. Warum also mit einem Generatorausdruck neu erstellen?
Michael J. Barber
3
Paare zu berechnen ist O(N)auch. Du könntest machen pairs = itertools.izip(lst, itertools.islice(lst, 1, None)).
Tomasz Elendt
18

@ 6502 hat den perfekten Code für Listen. Ich möchte nur eine allgemeine Version hinzufügen, die für alle Sequenzen funktioniert:

def pairwise(seq):
    items = iter(seq)
    last = next(items)
    for item in items:
        yield last, item
        last = item

def strictly_increasing(L):
    return all(x<y for x, y in pairwise(L))

def strictly_decreasing(L):
    return all(x>y for x, y in pairwise(L))

def non_increasing(L):
    return all(x>=y for x, y in pairwise(L))

def non_decreasing(L):
    return all(x<=y for x, y in pairwise(L))
Jochen Ritzel
quelle
6

Das Pandas- Paket macht dies bequem.

import pandas as pd

Die folgenden Befehle arbeiten mit einer Liste von Ganzzahlen oder Gleitkommazahlen.

Monoton ansteigend (≥):

pd.Series(mylist).is_monotonic_increasing

Streng monoton ansteigend (>):

myseries = pd.Series(mylist)
myseries.is_unique and myseries.is_monotonic_increasing

Alternative mit einer undokumentierten privaten Methode:

pd.Index(mylist)._is_strictly_monotonic_increasing

Monoton abnehmend (≤):

pd.Series(mylist).is_monotonic_decreasing

Streng monoton abnehmend (<):

myseries = pd.Series(mylist)
myseries.is_unique and myseries.is_monotonic_decreasing

Alternative mit einer undokumentierten privaten Methode:

pd.Index(mylist)._is_strictly_monotonic_decreasing
Scharfsinn
quelle
4
import operator, itertools

def is_monotone(lst):
    op = operator.le            # pick 'op' based upon trend between
    if not op(lst[0], lst[-1]): # first and last element in the 'lst'
        op = operator.ge
    return all(op(x,y) for x, y in itertools.izip(lst, lst[1:]))
Akira
quelle
Ich habe über eine Lösung wie diese nachgedacht - aber sie schlägt fehl, wenn die Liste monoton ansteigt und die ersten beiden Elemente gleich sind.
Hugh Bothwell
@ Hugh Bothwell: Ich überprüfe jetzt das erste und das letzte, um den Trend zu erhalten: Wenn sie gleich sind, sollten auch alle anderen Elemente gleich sein, was dann sowohl für operator.le als auch für operator.ge funktioniert
akira
3

Hier ist eine funktionale Lösung mit reduceKomplexität O(n):

is_increasing = lambda L: reduce(lambda a,b: b if a < b else 9999 , L)!=9999

is_decreasing = lambda L: reduce(lambda a,b: b if a > b else -9999 , L)!=-9999

Ersetzen Sie 9999durch die Obergrenze Ihrer Werte und -9999durch die Untergrenze. Wenn Sie beispielsweise eine Liste von Ziffern testen, können Sie 10und verwenden -1.


Ich habe seine Leistung anhand der Antwort von @ 6502 getestet und es ist schneller.

Fall wahr: [1,2,3,4,5,6,7,8,9]

# my solution .. 
$ python -m timeit "inc = lambda L: reduce(lambda a,b: b if a < b else 9999 , L)!=9999; inc([1,2,3,4,5,6,7,8,9])"
1000000 loops, best of 3: 1.9 usec per loop

# while the other solution:
$ python -m timeit "inc = lambda L: all(x<y for x, y in zip(L, L[1:]));inc([1,2,3,4,5,6,7,8,9])"
100000 loops, best of 3: 2.77 usec per loop

Groß- / Kleinschreibung falsch ab dem 2. Element[4,2,3,4,5,6,7,8,7] ::

# my solution .. 
$ python -m timeit "inc = lambda L: reduce(lambda a,b: b if a < b else 9999 , L)!=9999; inc([4,2,3,4,5,6,7,8,7])"
1000000 loops, best of 3: 1.87 usec per loop

# while the other solution:
$ python -m timeit "inc = lambda L: all(x<y for x, y in zip(L, L[1:]));inc([4,2,3,4,5,6,7,8,7])"
100000 loops, best of 3: 2.15 usec per loop
bigOther
quelle
1
L = [1,2,3]
L == sorted(L)

L == sorted(L, reverse=True)
Sternchen
quelle
Ich hätte mich entschieden, sorted()wenn es eigentlich nichts sortiert hätte, überprüfen Sie es einfach. Schlecht benannt - klingt wie ein Prädikat, wenn es nicht ist.
Mike3996
13
Was kommt als nächstes? Verwenden sorted(L)[0]statt min?
6502
4
Dies ist algorithmisch schlecht; Diese Lösung ist O (n log n), wenn dieses Problem in O (n) trivial gelöst werden kann.
Glenn Maynard
@all stimme euch allen zu, danke für konstruktive Kritik.
Sternchen
1
Ich habe alle Lösungen in diesem Thread hier getestet und festgestellt, dass die sortierte Methode tatsächlich die beste ist ... wenn die Liste tatsächlich monoton ansteigt. Wenn die Liste Elemente enthält, die nicht in der richtigen Reihenfolge sind, wird sie am langsamsten.
Matthew Moisen
1

Ich habe alle Antworten in dieser Frage unter verschiedenen Bedingungen zeitlich festgelegt und festgestellt, dass:

  • Die Sortierung war bei weitem die schnellste, wenn die Liste bereits monoton anstieg
  • Das Sortieren war bei weitem am langsamsten, wenn die Liste gemischt / zufällig war oder wenn die Anzahl der Elemente außerhalb der Reihenfolge größer als ~ 1 war. Je mehr außer Betrieb die Liste ist, desto langsamer ist natürlich das Ergebnis.
  • Die Michael J. Barbers-Methode war die schnellste, wenn die Liste meist monoton anstieg oder völlig zufällig war.

Hier ist der Code zum Ausprobieren:

import timeit

setup = '''
import random
from itertools import izip, starmap, islice
import operator

def is_increasing_normal(lst):
    for i in range(0, len(lst) - 1):
        if lst[i] >= lst[i + 1]:
            return False
    return True

def is_increasing_zip(lst):
    return all(x < y for x, y in izip(lst, islice(lst, 1, None)))

def is_increasing_sorted(lst):
    return lst == sorted(lst)

def is_increasing_starmap(lst):
    pairs = izip(lst, islice(lst, 1, None))
    return all(starmap(operator.le, pairs))

if {list_method} in (1, 2):
    lst = list(range({n}))
if {list_method} == 2:
    for _ in range(int({n} * 0.0001)):
        lst.insert(random.randrange(0, len(lst)), -random.randrange(1,100))
if {list_method} == 3:
    lst = [int(1000*random.random()) for i in xrange({n})]
'''

n = 100000
iterations = 10000
list_method = 1

timeit.timeit('is_increasing_normal(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations)

timeit.timeit('is_increasing_zip(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations)

timeit.timeit('is_increasing_sorted(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations)

timeit.timeit('is_increasing_starmap(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations)

Wenn die Liste bereits monoton anstieg ( list_method == 1), war die schnellste bis langsamste:

  1. sortiert
  2. Sternenkarte
  3. normal
  4. Postleitzahl

Wenn die Liste größtenteils monoton anstieg ( list_method == 2), war die schnellste bis langsamste:

  1. Sternenkarte
  2. Postleitzahl
  3. normal
  4. sortiert

(Ob die Sternenkarte oder der Reißverschluss am schnellsten war oder nicht, hing von der Ausführung ab und ich konnte kein Muster identifizieren. Die Sternenkarte schien normalerweise schneller zu sein.)

Wenn die Liste völlig zufällig war ( list_method == 3), war die schnellste bis langsamste:

  1. Sternenkarte
  2. Postleitzahl
  3. normal
  4. sortiert (extrem schlecht)
Matthew Moisen
quelle
Ich habe @Assem Chellis Methode nicht ausprobiert, da sie die Kenntnis des maximalen Elements in der Liste erforderte
Matthew Moisen,
Die zeitlichen Vergleiche würden auch stark von der Größe nder Liste abhängen und könnten erheblich von 100000
abweichen
0

@ 6502 hat dafür einen eleganten Python-Code. Hier ist eine alternative Lösung mit einfacheren Iteratoren und ohne potenziell teure temporäre Slices:

def strictly_increasing(L):
    return all(L[i] < L[i+1] for i in range(len(L)-1))

def strictly_decreasing(L):
    return all(L[i] > L[i+1] for i in range(len(L)-1))

def non_increasing(L):
    return all(L[i] >= L[i+1] for i in range(len(L)-1))

def non_decreasing(L):
    return all(L[i] <= L[i+1] for i in range(len(L)-1))

def monotonic(L):
    return non_increasing(L) or non_decreasing(L)
chqrlie
quelle
-1
>>> l = [0,1,2,3,3,4]
>>> l == sorted(l) or l == sorted(l, reverse=True)
Senthil Kumaran
quelle
-1

Hier ist eine Variante, die sowohl materialisierte als auch nicht materialisierte Sequenzen akzeptiert . Es bestimmt automatisch, ob es sich um monotoniceine Richtung (dh increasingoder decreasing) und eine strictNess handelt. Inline-Kommentare helfen dem Leser. Ähnliches gilt für Testfälle, die am Ende bereitgestellt werden.

    def isMonotonic(seq):
    """
    seq.............: - A Python sequence, materialized or not.
    Returns.........:
       (True,0,True):   - Mono Const, Strict: Seq empty or 1-item.
       (True,0,False):  - Mono Const, Not-Strict: All 2+ Seq items same.
       (True,+1,True):  - Mono Incr, Strict.
       (True,+1,False): - Mono Incr, Not-Strict.
       (True,-1,True):  - Mono Decr, Strict.
       (True,-1,False): - Mono Decr, Not-Strict.
       (False,None,None) - Not Monotonic.
    """    
    items = iter(seq) # Ensure iterator (i.e. that next(...) works).
    prev_value = next(items, None) # Fetch 1st item, or None if empty.
    if prev_value == None: return (True,0,True) # seq was empty.

    # ============================================================
    # The next for/loop scans until it finds first value-change.
    # ============================================================
    # Ex: [3,3,3,78,...] --or- [-5,-5,-5,-102,...]
    # ============================================================
    # -- If that 'change-value' represents an Increase or Decrease,
    #    then we know to look for Monotonically Increasing or
    #    Decreasing, respectively.
    # -- If no value-change is found end-to-end (e.g. [3,3,3,...3]),
    #    then it's Monotonically Constant, Non-Strict.
    # -- Finally, if the sequence was exhausted above, which means
    #    it had exactly one-element, then it Monotonically Constant,
    #    Strict.
    # ============================================================
    isSequenceExhausted = True
    curr_value = prev_value
    for item in items:
        isSequenceExhausted = False # Tiny inefficiency.
        if item == prev_value: continue
        curr_value = item
        break
    else:
        return (True,0,True) if isSequenceExhausted else (True,0,False)
    # ============================================================

    # ============================================================
    # If we tricked down to here, then none of the above
    # checked-cases applied (i.e. didn't short-circuit and
    # 'return'); so we continue with the final step of
    # iterating through the remaining sequence items to
    # determine Monotonicity, direction and strictness.
    # ============================================================
    strict = True
    if curr_value > prev_value: # Scan for Increasing Monotonicity.
        for item in items:
            if item < curr_value: return (False,None,None)
            if item == curr_value: strict = False # Tiny inefficiency.
            curr_value = item
        return (True,+1,strict)
    else:                       # Scan for Decreasing Monotonicity.
        for item in items: 
            if item > curr_value: return (False,None,None)
            if item == curr_value: strict = False # Tiny inefficiency.
            curr_value = item
        return (True,-1,strict)
    # ============================================================


# Test cases ...
assert isMonotonic([1,2,3,4])     == (True,+1,True)
assert isMonotonic([4,3,2,1])     == (True,-1,True)
assert isMonotonic([-1,-2,-3,-4]) == (True,-1,True)
assert isMonotonic([])            == (True,0,True)
assert isMonotonic([20])          == (True,0,True)
assert isMonotonic([-20])         == (True,0,True)
assert isMonotonic([1,1])         == (True,0,False)
assert isMonotonic([1,-1])        == (True,-1,True)
assert isMonotonic([1,-1,-1])     == (True,-1,False)
assert isMonotonic([1,3,3])       == (True,+1,False)
assert isMonotonic([1,2,1])       == (False,None,None)
assert isMonotonic([0,0,0,0])     == (True,0,False)

Ich nehme an, dies könnte mehr sein Pythonic, aber es ist schwierig , weil es Zwischen Sammlungen vermeidet die Erstellung (zB list, genexpsusw.); sowie verwendet einen fall/trickle-throughund short-circuitAnsatz, um durch die verschiedenen Fälle zu filtern: zB Kantensequenzen (wie leere Sequenzen oder Sequenzen mit einem Element; oder Sequenzen mit allen identischen Elementen); Identifizieren zunehmender oder abnehmender Monotonie, Strenge und so weiter. Ich hoffe, es hilft.

NYCeyes
quelle
Warum das Downvote? Es ist gut erklärt und bietet dem Leser einen alternativen Ansatz für andere.
NYCeyes