Python - 如何检查列表单调性

Question

检查列表单调性的有效和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

Answer 1

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)

Answer 2

如果你有大量的数字列表,最好使用numpy,如果你有:

import numpy as np

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

应该做的伎俩.

Answer 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)在列表的长度上.

Answer 4

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

Answer 5

该大熊猫封装使这个方便。

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

Answer 6

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

1. @6502 已接受/最佳答案
2. @Michael J. Barber 的itertools.starmap 回答
3. @Jochen Ritzel 的itertools.pairwise 回答
4. @akira的operator 回答
5. @chqrlie 的range(len()) 回答
6. @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")

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