Python - Jak sprawdzić monotoniczność listy

Jaki byłby skuteczny i pytoniczny sposób sprawdzenia monotoniczności listy?
tzn. że ma monotonicznie rosnące lub malejące wartości?

Przykłady:

[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

Lepiej unikać niejednoznacznych terminów, takich jak „zwiększanie” lub „zmniejszanie”, ponieważ nie jest jasne, czy równość jest akceptowalna, czy nie. Zawsze powinieneś używać na przykład „nie rosnąco” (oczywiście równość jest akceptowana) lub „ściśle malejąca” (oczywiście równość NIE jest akceptowana).

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)

Jeśli masz duże listy liczb, najlepiej użyć numpy, a jeśli jesteś:

import numpy as np

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

powinien załatwić sprawę.

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)

To podejście znajduje się O(N)na całej liście.

@ 6502 ma doskonały kod dla list, chcę tylko dodać ogólną wersję, która działa dla wszystkich sekwencji:

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

Pandy opakowanie sprawia, że to wygodne.

import pandas as pd

Następujące polecenia działają z listą liczb całkowitych lub liczb zmiennoprzecinkowych.

Monotonicznie rosnące (≥):

pd.Series(mylist).is_monotonic_increasing

Ściśle monotonicznie rosnące (>):

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

Alternatywa przy użyciu nieudokumentowanej metody prywatnej:

pd.Index(mylist)._is_strictly_monotonic_increasing

Monotonicznie malejące (≤):

pd.Series(mylist).is_monotonic_decreasing

Ściśle monotonicznie malejące (<):

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

Alternatywa przy użyciu nieudokumentowanej metody prywatnej:

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

Oto funkcjonalne rozwiązanie wykorzystujące reducezłożoność 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

Zastąp 9999górną granicą swoich wartości i -9999dolną granicą. Na przykład, jeśli testujesz listę cyfr, możesz użyć 10i -1.

Przetestowałem jego wydajność z odpowiedzią @ 6502 i jest szybsza.

Przypadek prawdziwy: [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

Case False z drugiego elementu[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

Zmierzyłem czas wszystkich odpowiedzi na to pytanie w różnych warunkach i stwierdziłem, że:

• Sortowanie było najszybsze z dystansu, JEŚLI lista już rosła monotonicznie
• Sortowanie było najwolniejsze z dystansu, JEŻELI lista była przetasowana / losowa lub jeśli liczba elementów w kolejności była większa niż ~ 1. Im bardziej nieuporządkowana lista, oczywiście odpowiada wolniejszemu wynikowi.
• Metoda Michaela J. Barbersa była najszybsza, JEŚLI lista była przeważnie rosnąca monotonicznie lub całkowicie losowo.

Oto kod, aby go wypróbować:

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)

Jeśli lista już rosła monotonicznie ( list_method == 1), od najszybszego do najwolniejszego było:

1. posortowane
2. starmap
3. normalna
4. zamek błyskawiczny

Jeśli lista rosła głównie monotonicznie ( list_method == 2), od najszybszego do najwolniejszego było:

1. starmap
2. zamek błyskawiczny
3. normalna
4. posortowane

(To, czy mapa gwiazd czy zamek błyskawiczny były najszybsze, zależało od wykonania i nie mogłem zidentyfikować wzoru. Starmap wydawał się zwykle szybszy)

Jeśli lista była całkowicie losowa ( list_method == 3), od najszybszego do najwolniejszego było:

1. starmap
2. zamek błyskawiczny
3. normalna
4. posortowane (bardzo źle)

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

L == sorted(L, reverse=True)

@ 6502 ma do tego elegancki kod w Pythonie. Oto alternatywne rozwiązanie z prostszymi iteratorami i bez potencjalnie drogich tymczasowych wycinków:

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)

Oto wariant, który akceptuje zarówno zmaterializowane, jak i niezmaterializowane sekwencje. Automatycznie określa, czy to jest monotonic, a jeśli tak, to jego kierunek (tj. increasingLub decreasing) i czy strict. Aby pomóc czytelnikowi, zamieszczono komentarze w tekście. Podobnie w przypadku przypadków testowych dostarczonych na końcu.

    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)

Przypuszczam, że to może być więcej Pythonic, ale jest to trudne, ponieważ zapobiega tworzeniu kolekcji pośrednich (np list, genexpsitp); a także stosuje podejście a fall/trickle-throughi short-circuitdo filtrowania różnych przypadków: Np. sekwencje krawędzi (takie jak sekwencje puste lub jednoelementowe; lub sekwencje ze wszystkimi identycznymi elementami); Rozpoznawanie rosnącej lub malejącej monotoniczności, ścisłości i tak dalej. Mam nadzieję, że to pomoże.