Python - 如何检查列表单调性

Python - How to check list monotonicity

提问by Jonathan

What would be an efficient and pythonicway to check list monotonicity?
i.e. that it has monotonically increasing or decreasing values?

什么是检查列表单调性的有效和 pythonic方法？
即它具有单调递增或递减的值？

Examples:

例子：

[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

采纳答案by 6502

It's better to avoid ambiguous terms like "increasing" or "decreasing" as it's not clear if equality is acceptable or not. You should always use either for example "non-increasing" (clearly equality is accepted) or "strictly decreasing" (clearly equality is NOT accepted).

最好避免使用“增加”或“减少”等含糊不清的术语，因为不清楚是否可以接受平等。您应该始终使用例如“非增加”（显然接受相等）或“严格减少”（显然不接受相等）。

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)

回答by Asterisk

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

L == sorted(L, reverse=True)

回答by Senthil Kumaran

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

回答by Michael J. Barber

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)

This approach is O(N)in the length of the list.

这种方法是O(N)在列表的长度。

回答by Autoplectic

If you have large lists of numbers it might be best to use numpy, and if you are:

如果您有大量数字列表，最好使用 numpy，如果您是：

import numpy as np

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

should do the trick.

应该做的伎俩。

回答by akira

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

回答by Jochen Ritzel

@6502 has the perfect code for lists, I just want to add a general version that works for all sequences:

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

回答by bigOther

Here is a functional solution using reduceof complexity O(n):

这是使用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

Replace 9999with the top limit of your values, and -9999with the bottom limit. For example, if you are testing a list of digits, you can use 10and -1.

替换9999为您的值的上限和-9999下限。例如，如果您正在测试数字列表，则可以使用10和-1。

---

---

I tested its performance against @6502's answerand its faster.

我根据@6502 的答案测试了它的性能，并且速度更快。

Case True: [1,2,3,4,5,6,7,8,9]

案例真： [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 from the 2nd element: [4,2,3,4,5,6,7,8,7]:

来自第二个元素的 Case False[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

回答by Matthew Moisen

I timed all of the answers in this question under different conditions, and found that:

我在不同条件下对这个问题中的所有答案进行了计时，发现：

• Sorting was the fastest by a long shot IF the list was already monotonically increasing
• Sorting was the slowest by a long shot IF the list was shuffled/random or if the number of elements out of order was greater than ~1. The more out of order the list of course corresponds to a slower result.
• Michael J. Barbers method was the fastest IF the list was mostly monotonically increasing, or completely random.

• 如果列表已经单调递增，则排序是最快的
• 如果列表被打乱/随机，或者如果乱序的元素数量大于~1，则排序是最慢的。当然，列表越乱，结果就越慢。
• 如果列表主要是单调递增或完全随机，Michael J. Barbers 方法是最快的。

Here is the code to try it out:

这是尝试的代码：

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)

If the list was already monotonically increasing (list_method == 1), the fastest to slowest was:

如果列表已经单调递增 ( list_method == 1)，则从最快到最慢是：

1. sorted
2. starmap
3. normal
4. zip

1. 排序
2. 星图
3. 普通的
4. 压缩

If the list was mostly monotonically increasing (list_method == 2), the fastest to slowest was:

如果列表主要是单调递增 ( list_method == 2)，则从最快到最慢是：

1. starmap
2. zip
3. normal
4. sorted

1. 星图
2. 压缩
3. 普通的
4. 排序

(Whether or not the starmap or zip was fastest depended on the execution and I couldn't identify a pattern. Starmap appeared to be usually faster)

（星图或 zip 是否最快取决于执行，我无法识别模式。星图似乎通常更快）

If the list was completely random (list_method == 3), the fastest to slowest was:

如果列表是完全随机的 ( list_method == 3)，则从最快到最慢是：

1. starmap
2. zip
3. normal
4. sorted (extremely bad)

1. 星图
2. 压缩
3. 普通的
4. 排序（非常糟糕）

回答by Acumenus

This is possible using Pandaswhich you can install via pip install pandas.

这可以使用Pandas 来实现，您可以通过pip install pandas.

import pandas as pd

The following commands work with a list of integers or floats.

以下命令处理整数或浮点数列表。

Monotonically increasing(≥):

单调递增（≥）：

pd.Series(mylist).is_monotonic_increasing

Strictly monotonically increasing (>):

严格单调递增 (>)：

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

Alternative using an undocumented private method:

使用未记录的私有方法的替代方法：

pd.Index(mylist)._is_strictly_monotonic_increasing

Monotonically decreasing(≤):

单调递减（≤）：

pd.Series(mylist).is_monotonic_decreasing

Strictly monotonically decreasing (<):

严格单调递减 (<)：

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

Alternative using an undocumented private method:

使用未记录的私有方法的替代方法：

pd.Index(mylist)._is_strictly_monotonic_decreasing