it-swarm-ru.tech

Python - Как проверить монотонность списка

Каков был бы эффективный и Pythonic способ проверить монотонность списка?
то есть что оно имеет монотонно увеличивающиеся или уменьшающиеся значения?

Примеры:

[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
53
Jonathan
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)
120
6502

Если у вас большой список чисел, лучше всего использовать numpy, и если вы:

import numpy as np

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

должен сделать свое дело.

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

Этот подход O(N) в длине списка. 

24
Michael J. Barber

@ 6502 имеет идеальный код для списков, я просто хочу добавить общую версию, которая работает для всех последовательностей:

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))
14
Jochen Ritzel
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:]))
4
akira

Вот функциональное решение, использующее reduce сложности 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

Замените 9999 верхним пределом ваших значений, а -9999 нижним пределом. Например, если вы тестируете список цифр, вы можете использовать 10 и -1.


Я проверил его производительность по отношению к @ 6502's answer и быстрее.

Case True: [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 из 2-го элемента: [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
2
BigOther

Я рассчитал все ответы на этот вопрос в разных условиях и обнаружил, что:

  • Сортировка была самой быстрой, если список уже монотонно увеличивался
  • Сортировка была самой медленной, если список был перетасован/случайным образом, или если количество элементов не в порядке было больше, чем ~ 1. Чем больше не в порядке список, конечно, соответствует более медленный результат.
  • Метод Майкла Дж. Барберса был самым быстрым, ЕСЛИ список в основном монотонно увеличивался или был совершенно случайным.

Вот код, чтобы попробовать это:

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)

Если список уже монотонно увеличивался (list_method == 1), самый быстрый к медленному был:

  1. отсортированный
  2. starmap
  3. нормальный
  4. Застежка-молния

Если список в основном монотонно увеличивается (list_method == 2), то самым быстрым и самым медленным является:

  1. starmap
  2. Застежка-молния
  3. нормальный
  4. отсортированный

(Будь то Starmap или Zip были самыми быстрыми, зависело от выполнения, и я не мог определить образец. Starmap, как правило, быстрее)

Если список был полностью случайным (list_method == 3), самый быстрый и медленный был:

  1. starmap
  2. Застежка-молния
  3. нормальный
  4. отсортировано (очень плохо)
1
Matthew Moisen

Это возможно с помощью Pandas , который вы можете установить через pip install pandas.

import pandas as pd

Следующие команды работают со списком целых или с плавающей точкой.

Монотонно возрастающий (≥):

pd.Series(mylist).is_monotonic_increasing

Строго монотонно возрастающий (>):

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

Альтернатива с использованием недокументированного частного метода:

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

Альтернатива с использованием недокументированного частного метода:

pd.Index(mylist)._is_strictly_monotonic_decreasing
0
A-B-B
L = [1,2,3]
L == sorted(L)

L == sorted(L, reverse=True)
0
Asterisk