Python - Überprüfen der Listenmonotonie

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

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)

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.

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.

@ 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))

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

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:]))

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

L = [1,2,3]
L == sorted(L)

L == sorted(L, reverse=True)

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)

@ 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)

>>> l = [0,1,2,3,3,4]
>>> l == sorted(l) or l == sorted(l, reverse=True)

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.