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
Odpowiedzi:
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)
itertools.izipzamiast zipciebie można uzyskać wczesne wyjście (w Pythonie 3 zipjuż działa jak iterator)
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ę.
dx[0]być NaN? Jaka jest twoja tablica wejściowa?
np.diff()utworzył pierwszy element, NaNwięc kształt wyjścia pasował do danych wejściowych, ale w rzeczywistości był to inny fragment kodu, który tak mnie ugryzł. :)
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.
mapczy abstrakcja jest tutaj dokładnie potrzebna, więc po co ją odtwarzać za pomocą wyrażenia generatora?
O(N). Możesz zrobić pairs = itertools.izip(lst, itertools.islice(lst, 1, None)).
@ 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.
pd.Series(mylist).is_monotonic_increasing
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
pd.Series(mylist).is_monotonic_decreasing
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:
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:
Jeśli lista rosła głównie monotonicznie ( list_method == 2), od najszybszego do najwolniejszego było:
(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:
nlisty i mogą się znacznie różnić od 100000
L = [1,2,3]
L == sorted(L)
L == sorted(L, reverse=True)
sorted()gdyby to właściwie niczego nie posortowało, po prostu sprawdź. Źle nazwany - brzmi jak orzeczenie, gdy tak nie jest.
sorted(L)[0]zamiast min?
@ 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.