检查清单单调性-IT科技

摘要：问题描述：如何有效地检查列表的单调性？即，它是一组非递减或非递增的有序值？例子：[0, 1, 2, 3, 3, 4] # This is a monotonically increasing list [4.3, 4.2, 4.2, -2] # This is a monotonically decre...

问题描述：

如何有效地检查列表的单调性？即，它是一组非递减或非递增的有序值？

例子：

[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

解决方案 1：

重复值（例如[1, 1, 2]）是否单调？

如果是：

def non_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 monotonic(L):
    return non_decreasing(L) or non_increasing(L)

如果没有：

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 strictly_monotonic(L):
    return strictly_increasing(L) or strictly_decreasing(L)

解决方案 2：

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

import numpy as np

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

应该可以解决问题。

解决方案 3：

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)与列表的长度有关。

解决方案 4：

最佳答案只适用于序列（列表），这里有一个更通用的解决方案，适用于Python 3.10+的任何可迭代对象（列表和生成器）：

from itertools import pairwise

def monotonic(iterable, strict=False):
    up = False
    down = False
    for first, second in pairwise(iterable):
        if first < second:
            if down:
                return False
            up = True
        elif first > second:
            if up:
                return False
            down = True
        elif strict:
            # first and second are equal.
            return False
    return True

传递strict=True您想要返回False的重复元素，例如[1, 1]：

请注意，该功能itertools.pairwise仅在 Python 3.10+ 上可用，在Python 3.9 及更早版本上，您需要重新实现它：

from itertools import tee

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

解决方案 5：

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

解决方案 6：

我对这些非 numpy/pandas 答案进行了基准测试：

@6502 的接受/最佳答案
@Michael J. Barber 的itertools.starmap 回答
@Jochen Ritzel 的itertools.pairwise 回答
@akira 的operator 回答
@chqrlie 的range(len()) 回答
@Asterisk 和 @Senthil Kumaran 的幼稚sorted() 回答和答案

在具有 8GB RAM 的 M1 Macbook Air 上运行 Python 3.11，使用perfplot对单调输入进行分析[0, 1, 2, ... n]（越低越好）：

时间图

几乎单调的输入，除了最后一个元素[0, 1, 2, ... n, 0]：

另一条时间线图

以及一个随机打乱的列表：

第三张时序图

并发现

如果列表是单调的，排序速度会比次优方法快 4 倍；如果列表不是单调的，或者乱序元素的数量大于 1，排序速度会比次优方法慢 10 倍（或更多）。列表的乱序程度越高，排序结果越慢。
对于随机列表来说，提前停止的两个答案要快得多，因为你很可能从前几个元素中看到它不是单调的

代码如下：

import itertools
from itertools import pairwise
import operator

import random
import perfplot
import matplotlib
matplotlib.rc('font', family="monospace")

fns = []

def non_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 zip_monotonic(L):
    return non_decreasing(L) or non_increasing(L)
fns.append([zip_monotonic, '1. zip(l, l[1:])'])

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 starmap_monotone(lst):
    return monotone_increasing(lst) or monotone_decreasing(lst)
fns.append([starmap_monotone, '2. starmap(zip(l, l[1:]))'])

# def _monotone_increasing(lst):
#     return all(itertools.starmap(operator.le, itertools.pairwise(lst)))
# def _monotone_decreasing(lst):
#     return all(itertools.starmap(operator.ge, itertools.pairwise(lst)))
# def starmap_pairwise_monotone(lst):
#     return _monotone_increasing(lst) or _monotone_decreasing(lst)
# fns.append([starmap_pairwise_monotone, 'starmap(pairwise)'])

def pairwise_monotonic(iterable):
    up = True
    down = True
    for prev, current in pairwise(iterable):
        if prev < current:
            if not up:
                return False
            down = False
        elif prev > current:
            if not down:
                return False
            up = False
    return True
fns.append([pairwise_monotonic, '3. pairwise()'])

def operator_first_last_monotonic(lst):
    op = operator.le
    if lst and not op(lst[0], lst[-1]):
        op = operator.ge
    return all(op(x, y) for x, y in zip(lst, lst[1:]))
fns.append([operator_first_last_monotonic, '4. operator(zip(l, 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 range_monotonic(L):
    return __non_increasing(L) or __non_decreasing(L)
fns.append([pairwise_monotonic, '5. range(len(l))'])

# def monotonic_iter_once(iterable):
#     up, down = True, True
#     for i in range(1, len(iterable)):
#         if iterable[i] < iterable[i-1]: up = False
#         if iterable[i] > iterable[i-1]: down = False
#     return up or down
# fns.append([monotonic_iter_once, 'range(len(l)) once'])

def sorted_monotonic(seq):
    return seq == sorted(seq) or seq == sorted(seq, reverse=True)
fns.append([sorted_monotonic, '6. l == sorted(l)'])


def random_list(n):
    l = list(range(n))
    random.Random(4).shuffle(l)
    return l


setups = [
    (29, lambda n: list(range(n)), 'monotonic.png'),
    (29, lambda n: list(range(n)) + [0], 'non-monotonic.png'),
    (26, random_list, 'random.png'),
]
kernels, labels = zip(*fns)

for (size, setup, filename) in setups:
    out = perfplot.bench(
        setup=setup,
        kernels=kernels,
        labels=labels,
        n_range=[2**k for k in range(size)],
        xlabel="n",
    )
    out.show(
        logx=True,  # set to True or False to force scaling
        logy=True,
        # relative_to=5,  # plot the timings relative to one of the measurements
    )
    out.save(filename, transparent=True, bbox_inches="tight")

解决方案 7：

这是一个类似于@6502 的答案的解决方案，它具有更简单的迭代器并且没有潜在的昂贵的临时切片：

def non_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 monotonic(L):
    return non_decreasing(L) or non_increasing(L)

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 strictly_monotonic(L):
    return strictly_increasing(L) or strictly_decreasing(L)

解决方案 8：

这是一个使用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 的答案测试了它的性能，它的速度更快。

真实情况：[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

从第二个元素开始判断为假[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

解决方案 9：

import operator

def is_monotonic(lst):
    op = operator.le
    if lst and not op(lst[0], lst[-1]):
        op = operator.ge
    return all(op(x, y) for x, y in zip(lst, lst[1:]))

解决方案 10：

这是一个同时接受物化和非物化序列的变体。它会自动判断它是否为monotonic，如果是，则自动判断其方向（即increasing或decreasing）和strict性。内联注释有助于读者理解。末尾提供的测试用例也类似。

    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)

我认为这可能更多Pythonic，但这很棘手，因为它避免创建中间集合（例如list，genexps等等）；并且采用了fall/trickle-throughandshort-circuit方法来筛选各种情况：例如，边缘序列（如空序列或单项序列；或所有项都相同的序列）；识别递增或递减的单调性、严格性等等。希望对您有所帮助。

解决方案 11：

以下实现既通用（支持任何输入可迭代对象，包括迭代器，而不仅仅是序列），又高效（所需空间是恒定的，没有执行输入的临时浅拷贝的切片）：

import itertools

def is_increasing(iterable, strict=False):
    x_it, y_it = itertools.tee(iterable)
    next(y_it, None)
    if strict:
        return all(x < y for x, y in zip(x_it, y_it))
    return all(x <= y for x, y in zip(x_it, y_it))

def is_decreasing(iterable, strict=False):
    x_it, y_it = itertools.tee(iterable)
    next(y_it, None)
    if strict:
        return all(x > y for x, y in zip(x_it, y_it))
    return all(x >= y for x, y in zip(x_it, y_it))

def is_monotonic(iterable, strict=False):
    x_it, y_it = itertools.tee(iterable)
    return is_increasing(x_it, strict) or is_decreasing(y_it, strict)

一些测试用例：

assert is_monotonic([]) is True
assert is_monotonic(iter([])) is True
assert is_monotonic([1, 2, 3]) is True
assert is_monotonic(iter([1, 2, 3])) is True
assert is_monotonic([3, 2, 1]) is True
assert is_monotonic(iter([3, 2, 1])) is True
assert is_monotonic([1, 3, 2]) is False
assert is_monotonic(iter([1, 3, 2])) is False
assert is_monotonic([1, 1, 1]) is True
assert is_monotonic(iter([1, 1, 1])) is True

assert is_monotonic([], strict=True) is True
assert is_monotonic(iter([]), strict=True) is True
assert is_monotonic([1, 2, 3], strict=True) is True
assert is_monotonic(iter([1, 2, 3]), strict=True) is True
assert is_monotonic([3, 2, 1], strict=True) is True
assert is_monotonic(iter([3, 2, 1]), strict=True) is True
assert is_monotonic([1, 3, 2], strict=True) is False
assert is_monotonic(iter([1, 3, 2]), strict=True) is False
assert is_monotonic([1, 1, 1], strict=True) is False
assert is_monotonic(iter([1, 1, 1]), strict=True) is False

解决方案 12：

解决方案 1：基本循环

在我自己的测试中非常有效（我会尝试更新马修的情节），并且也适用于其他可迭代对象：

def monotonic(iterable):
    it = iter(iterable)
    for first in it:
        for x in it:
            if first != x:
                if first < x:
                    for y in it:
                        if x > y:
                            return False
                        x = y
                else:
                    for y in it:
                        if x < y:
                            return False
                        x = y
    return True

它找到一个与第一个值不同的值，然后根据它是更大还是更小，进入一个简单的循环来检查其余值是否非减少，或者进入一个简单的循环来检查其余值是否非增加。

解决方案 2：`sorted`重叠块

这将速度sorted与短路相结合。它读取并检查 1000 个元素的块，这些块相互重叠，使得一个块的最后一个元素也包含在下一个块的第一个元素中。

def monotonic(a):
    reverse = a[-1:] < a[:1]
    for i in range(0, len(a), 999):
        b = a[i : i+1000]
        if b != sorted(b, reverse=reverse):
            return False
    return True

解决方案 13：

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

L == sorted(L, reverse=True)

解决方案 14：

def IsMonotonic(data):
    ''' Returns true if data is monotonic.'''
    data = np.array(data)
    # Greater-Equal
    if (data[-1] > data[0]):
        return np.all(data[1:] >= data[:-1])
    # Less-Equal
    else:
        return np.all(data[1:] <= data[:-1])

我的建议（使用 numpy）是这里几个想法的总结。用途

为每个列表比较创建np.array布尔值，
np.all检查所有结果是否True
检查第一个元素和最后一个元素之间的差异以选择比较运算符，
使用直接比较>=, <=而不是计算np.diff，

解决方案 15：

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

解决方案 16：

在检查列表是减少还是增加时，我们只能迭代列表一次：

def is_monotonic(iterable):
    up = down = True
    for i in range(1, len(iterable)):
        if iterable[i] < iterable[i-1]: up = False
        if iterable[i] > iterable[i-1]: down = False
    return up or down