检查列表是否排序的 Python 方式
- 2025-01-08 08:50:00
- admin 原创
- 116
问题描述：
有没有一种 Python 式的方法来检查列表是否已经排序ASC或DESC
listtimestamps = [1, 2, 3, 5, 6, 7]
类似isttimestamps.isSorted()这样的返回True或False。
我想输入一些消息的时间戳列表并检查交易是否以正确的顺序出现。
解决方案 1：
以下是一行代码：
all(l[i] <= l[i+1] for i in range(len(l) - 1))
如果使用 Python 2，请使用xrange而不是range。
对于reverse=True，使用>=而不是<=。
解决方案 2：
我只会用
if sorted(lst) == lst:
# code here
除非它是一个非常大的列表，在这种情况下您可能需要创建一个自定义函数。
如果您只是在尚未排序的情况下对其进行排序，那么请忘记检查并对其进行排序。
lst.sort()
不要想太多。
如果你想要一个自定义函数，你可以这样做
def is_sorted(lst, key=lambda x: x):
for i, el in enumerate(lst[1:]):
if key(el) < key(lst[i]): # i is the index of the previous element
return False
return True
如果列表已经排序，则它将是 O（n）（并且在循环中是 O（n）for！）所以，除非你预计它大多数时候都是无序的（并且相当随机），否则我会再次对列表进行排序。
解决方案 3：
这种迭代器形式比使用整数索引快 10-15％：
# python2 only
if str is bytes:
from itertools import izip as zip
def is_sorted(l):
return all(a <= b for a, b in zip(l, l[1:]))
解决方案 4：
实现这一点的一个漂亮方法是使用imap以下函数itertools：
from itertools import imap, tee
import operator
def is_sorted(iterable, compare=operator.le):
a, b = tee(iterable)
next(b, None)
return all(imap(compare, a, b))
此实现速度很快并且适用于任何可迭代对象。
解决方案 5：
从开始Python 3.10，新pairwise函数提供了一种遍历连续元素对的方法，从而确定所有这些对是否满足相同的排序谓词：
from itertools import pairwise
all(x <= y for x, y in pairwise([1, 2, 3, 5, 6, 7]))
# True
中间结果pairwise：
pairwise([1, 2, 3, 5, 6, 7])
# [(1, 2), (2, 3), (3, 5), (5, 6), (6, 7)]
解决方案 6：
我会这样做（从这里的很多答案中窃取[Aaron Sterling，Wai Yip Tung，Paul McGuire 的类似答案]以及大部分Armin Ronacher）：
from itertools import tee, izip
def pairwise(iterable):
a, b = tee(iterable)
next(b, None)
return izip(a, b)
def is_sorted(iterable, key=lambda a, b: a <= b):
return all(key(a, b) for a, b in pairwise(iterable))
一件好事：您不必实现该系列的第二个可迭代（与列表切片不同）。
解决方案 7：
我运行了一个基准测试，sorted(lst, reverse=True) == lst对于长列表，它是最快的，all(l[i] >= l[i+1] for i in xrange(len(l)-1))对于短列表，它是最快的。这些基准测试是在 MacBook Pro 2010 13"（Core2 Duo 2.66GHz、4GB 1067MHz DDR3 RAM、Mac OS X 10.6.5）上运行的。
更新：我修改了脚本，以便您可以直接在自己的系统上运行它。以前的版本有错误。此外，我还添加了已排序和未排序的输入。
最适合短排序列表：
all(l[i] >= l[i+1] for i in xrange(len(l)-1))最适合长排序列表：
sorted(l, reverse=True) == l最适合简短的未分类列表：
all(l[i] >= l[i+1] for i in xrange(len(l)-1))最适合较长的未分类列表：
all(l[i] >= l[i+1] for i in xrange(len(l)-1))
因此大多数情况下都会有一个明显的赢家。
更新： aaronasterling 的答案（#6 和 #7）实际上是所有情况下最快的。#7 是最快的，因为它没有间接层来查找密钥。
#!/usr/bin/env python
import itertools
import time
def benchmark(f, *args):
t1 = time.time()
for i in xrange(1000000):
f(*args)
t2 = time.time()
return t2-t1
L1 = range(4, 0, -1)
L2 = range(100, 0, -1)
L3 = range(0, 4)
L4 = range(0, 100)
# 1.
def isNonIncreasing(l, key=lambda x,y: x >= y):
return all(key(l[i],l[i+1]) for i in xrange(len(l)-1))
print benchmark(isNonIncreasing, L1) # 2.47253704071
print benchmark(isNonIncreasing, L2) # 34.5398209095
print benchmark(isNonIncreasing, L3) # 2.1916718483
print benchmark(isNonIncreasing, L4) # 2.19576501846
# 2.
def isNonIncreasing(l):
return all(l[i] >= l[i+1] for i in xrange(len(l)-1))
print benchmark(isNonIncreasing, L1) # 1.86919999123
print benchmark(isNonIncreasing, L2) # 21.8603689671
print benchmark(isNonIncreasing, L3) # 1.95684289932
print benchmark(isNonIncreasing, L4) # 1.95272517204
# 3.
def isNonIncreasing(l, key=lambda x,y: x >= y):
return all(key(a,b) for (a,b) in itertools.izip(l[:-1],l[1:]))
print benchmark(isNonIncreasing, L1) # 2.65468883514
print benchmark(isNonIncreasing, L2) # 29.7504849434
print benchmark(isNonIncreasing, L3) # 2.78062295914
print benchmark(isNonIncreasing, L4) # 3.73436689377
# 4.
def isNonIncreasing(l):
return all(a >= b for (a,b) in itertools.izip(l[:-1],l[1:]))
print benchmark(isNonIncreasing, L1) # 2.06947803497
print benchmark(isNonIncreasing, L2) # 15.6351969242
print benchmark(isNonIncreasing, L3) # 2.45671010017
print benchmark(isNonIncreasing, L4) # 3.48461818695
# 5.
def isNonIncreasing(l):
return sorted(l, reverse=True) == l
print benchmark(isNonIncreasing, L1) # 2.01579380035
print benchmark(isNonIncreasing, L2) # 5.44593787193
print benchmark(isNonIncreasing, L3) # 2.01813793182
print benchmark(isNonIncreasing, L4) # 4.97615599632
# 6.
def isNonIncreasing(l, key=lambda x, y: x >= y):
for i, el in enumerate(l[1:]):
if key(el, l[i-1]):
return False
return True
print benchmark(isNonIncreasing, L1) # 1.06842684746
print benchmark(isNonIncreasing, L2) # 1.67291283607
print benchmark(isNonIncreasing, L3) # 1.39491200447
print benchmark(isNonIncreasing, L4) # 1.80557894707
# 7.
def isNonIncreasing(l):
for i, el in enumerate(l[1:]):
if el >= l[i-1]:
return False
return True
print benchmark(isNonIncreasing, L1) # 0.883186101913
print benchmark(isNonIncreasing, L2) # 1.42852401733
print benchmark(isNonIncreasing, L3) # 1.09229516983
print benchmark(isNonIncreasing, L4) # 1.59502696991
解决方案 8：
第三方包方法more_itertools.is_sorted还没提到：
import more_itertools
ls = [1, 4, 2]
print(more_itertools.is_sorted(ls))
ls2 = ["ab", "c", "def"]
print(more_itertools.is_sorted(ls2, key=len))
解决方案 9：
由于我上面没有看到此选项，因此我将把它添加到所有答案中。 让 表示列表l，然后：
import numpy as np
# Trasform the list to a numpy array
x = np.array(l)
# check if ascendent sorted:
all(x[:-1] <= x[1:])
# check if descendent sorted:
all(x[:-1] >= x[1:])
解决方案 10：
我使用基于numpy.diff（）的这一行代码：
def issorted(x):
"""Check if x is sorted"""
return (numpy.diff(x) >= 0).all() # is diff between all consecutive entries >= 0?
我还没有真正将它与任何其他方法进行比较，但我认为它比任何纯 Python 方法都快，尤其是对于较大的 n，因为 numpy.diff 中的循环（可能）直接在 C 中运行（n-1 次减法，然后是 n-1 次比较）。
但是，如果 x 是无符号整数，则需要小心，这可能会导致 numpy.diff() 中的静默整数下溢，从而导致误报。以下是修改后的版本：
def issorted(x):
"""Check if x is sorted"""
try:
if x.dtype.kind == 'u':
# x is unsigned int array, risk of int underflow in np.diff
x = numpy.int64(x)
except AttributeError:
pass # no dtype, not an array
return (numpy.diff(x) >= 0).all()
解决方案 11：
这与最佳答案类似，但我更喜欢它，因为它避免了显式索引。假设您的列表名为lst，您可以
(item, next_item)使用 从列表中生成元组zip：
all(x <= y for x,y in zip(lst, lst[1:]))
在 Python 3 中，zip已经返回了一个生成器，在 Python 2 中可以使用它itertools.izip来获得更好的内存效率。
小演示：
>>> lst = [1, 2, 3, 4]
>>> zip(lst, lst[1:])
[(1, 2), (2, 3), (3, 4)]
>>> all(x <= y for x,y in zip(lst, lst[1:]))
True
>>>
>>> lst = [1, 2, 3, 2]
>>> zip(lst, lst[1:])
[(1, 2), (2, 3), (3, 2)]
>>> all(x <= y for x,y in zip(lst, lst[1:]))
False
(3, 2)当评估元组时，最后一个失败。
奖励：检查无法索引的有限（！）生成器：
>>> def gen1():
... yield 1
... yield 2
... yield 3
... yield 4
...
>>> def gen2():
... yield 1
... yield 2
... yield 4
... yield 3
...
>>> g1_1 = gen1()
>>> g1_2 = gen1()
>>> next(g1_2)
1
>>> all(x <= y for x,y in zip(g1_1, g1_2))
True
>>>
>>> g2_1 = gen2()
>>> g2_2 = gen2()
>>> next(g2_2)
1
>>> all(x <= y for x,y in zip(g2_1, g2_2))
False
如果您使用的是 Python 2，请确保在此处使用itertools.izip，否则您将无法实现不必从生成器创建列表的目的。
解决方案 12：
懒惰的
from itertools import tee
def is_sorted(l):
l1, l2 = tee(l)
next(l2, None)
return all(a <= b for a, b in zip(l1, l2))
解决方案 13：
尽管我认为不能保证sorted内置函数会用 调用其 cmp 函数i+1, i，但对于 CPython 来说它似乎确实这样做了。
因此你可以做类似的事情：
def my_cmp(x, y):
cmpval = cmp(x, y)
if cmpval < 0:
raise ValueError
return cmpval
def is_sorted(lst):
try:
sorted(lst, cmp=my_cmp)
return True
except ValueError:
return False
print is_sorted([1,2,3,5,6,7])
print is_sorted([1,2,5,3,6,7])
或者这样（没有 if 语句 -> EAFP 出错了？;-) ）：
def my_cmp(x, y):
assert(x >= y)
return -1
def is_sorted(lst):
try:
sorted(lst, cmp=my_cmp)
return True
except AssertionError:
return False
解决方案 14：
正如@aaronsterling 所指出的，以下解决方案是最短的，并且在数组排序且不太小的情况下似乎最快：def is_sorted(lst): return (sorted(lst) == lst)
如果大多数情况下数组未排序，则最好使用一种不扫描整个数组并在发现未排序前缀时立即返回 False 的解决方案。以下是我能找到的最快的解决方案，但它并不是特别优雅：
def is_sorted(lst):
it = iter(lst)
try:
prev = next(it)
except StopIteration:
return True
for x in it:
if prev > x: # For reverse, use <
return False
prev = x
return True
使用 Nathan Farrington 的基准，除了在大型排序列表上运行时，在所有情况下都比使用 sorted(lst) 实现更好的运行时间。
以下是我的电脑上的基准测试结果。
sorted(lst)==lst 解决方案
L1：1.23838591576
L2：4.19063091278
L3：1.17996287346
L4：4.68399500847
第二种解决方案：
L1：0.81095790863
L2：0.802397012711
L3：1.06135106087
L4：8.82761001587
解决方案 15：
只需添加另一种方法（即使它需要额外的模块）iteration_utilities.all_monotone：：
>>> from iteration_utilities import all_monotone
>>> listtimestamps = [1, 2, 3, 5, 6, 7]
>>> all_monotone(listtimestamps)
True
>>> all_monotone([1,2,1])
False
检查 DESC 顺序：
>>> all_monotone(listtimestamps, decreasing=True)
False
>>> all_monotone([3,2,1], decreasing=True)
True
strict如果您需要检查严格（如果连续元素不应该相等）单调序列，那么还有一个参数。
在您的情况下这不是问题，但如果您的序列包含nan值，那么某些方法将失败，例如已排序：
def is_sorted_using_sorted(iterable):
return sorted(iterable) == iterable
>>> is_sorted_using_sorted([3, float('nan'), 1]) # definitely False, right?
True
>>> all_monotone([3, float('nan'), 1])
False
请注意，iteration_utilities.all_monotone与这里提到的其他解决方案相比，其执行速度更快，特别是对于未排序的输入（参见基准）。
解决方案 16：
根本不太符合 Python 风格，但我们至少需要一个reduce()答案，对吧？
def is_sorted(iterable):
prev_or_inf = lambda prev, i: i if prev <= i else float('inf')
return reduce(prev_or_inf, iterable, float('-inf')) < float('inf')
累加器变量仅存储最后检查的值，并且如果任何值小于先前的值，则累加器设置为无穷大（并且因此最后仍然是无穷大，因为“先前的值”将始终大于当前值）。
解决方案 17：
这种使用 Pandas 的方法非常慢，但它以完整性而著称。
from typing import Sequence
import pandas as pd
def is_sorted(seq: Sequence, reverse: bool = False) -> bool:
index = pd.Index(seq)
if reverse:
return index.is_monotonic_decreasing
return index.is_monotonic_increasing
解决方案 18：
SapphireSun说得很对。你可以直接使用lst.sort()。Python 的排序实现 (TimSort) 检查列表是否已排序。如果是，sort() 将在线性时间内完成。听起来像是一种确保列表已排序的 Pythonic 方法 ;)
解决方案 19：
Python 3.6.8
from more_itertools import pairwise
class AssertionHelper:
@classmethod
def is_ascending(cls, data: iter) -> bool:
for a, b in pairwise(data):
if a > b:
return False
return True
@classmethod
def is_descending(cls, data: iter) -> bool:
for a, b in pairwise(data):
if a < b:
return False
return True
@classmethod
def is_sorted(cls, data: iter) -> bool:
return cls.is_ascending(data) or cls.is_descending(data)
>>> AssertionHelper.is_descending((1, 2, 3, 4))
False
>>> AssertionHelper.is_ascending((1, 2, 3, 4))
True
>>> AssertionHelper.is_sorted((1, 2, 3, 4))
True
解决方案 20：
使用赋值表达式的解决方案（在 Python 3.8 中添加）：
def is_sorted(seq):
seq_iter = iter(seq)
cur = next(seq_iter, None)
return all((prev := cur) <= (cur := nxt) for nxt in seq_iter)
z = list(range(10))
print(z)
print(is_sorted(z))
import random
random.shuffle(z)
print(z)
print(is_sorted(z))
z = []
print(z)
print(is_sorted(z))
给出：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
True
[1, 7, 5, 9, 4, 0, 8, 3, 2, 6]
False
[]
True
解决方案 21：
如果你想要以最快的方式使用 numpy 数组，请使用numba，如果你使用 conda ，它应该已经安装好了
代码会很快，因为它将由 numba 编译
import numba
@numba.jit
def issorted(vec, ascending=True):
if len(vec) < 2:
return True
if ascending:
for i in range(1, len(vec)):
if vec[i-1] > vec[i]:
return False
return True
else:
for i in range(1, len(vec)):
if vec[i-1] < vec[i]:
return False
return True
进而：
>>> issorted(array([4,9,100]))
>>> True
解决方案 22：
这使用递归：
def is_sorted(lst):
if len(lst) == 1:
return True
return lst[0] <= lst[1] and is_sorted(lst[1:])
some_list = [1,2,3,4]
print(is_sorted(some_list))
请注意，对于长序列来说，这将会引发问题RuntimeError: maximum recursion depth exceeded。
解决方案 23：
尝试一下：
def is_sorted(arr) -> bool:
for i in range(1, len(arr)):
if arr[i] < arr[i - 1]:
return False
return True
解决方案 24：
from functools import reduce
# myiterable can be of any iterable type (including list)
isSorted = reduce(lambda r, e: (r[0] and (r[1] or r[2] <= e), False, e), myiterable, (True, True, None))[0]
派生的缩减值是一个由 3 部分组成的元组 ( sortedSoFarFlag , firstTimeFlag , lastElementValue )。它最初以 ( True, True, None) 开头，也用作空列表的结果（由于没有无序元素，因此被视为已排序）。在处理每个元素时，它会计算元组的新值（使用上一个元组值和下一个元素值）：
[0] (sortedSoFarFlag) evaluates true if: prev_0 is true and (prev_1 is true or prev_2 <= elementValue)
[1] (firstTimeFlag): False
[2] (lastElementValue): elementValue
归约的最终结果是一个元组：
[0]: True/False depending on whether the entire list was in sorted order
[1]: True/False depending on whether the list was empty
[2]: the last element value
第一个值是我们感兴趣的，因此我们用[0]它来从 Reduce 结果中获取它。
此解决方案适用于任何包含可相互比较的元素类型的可迭代对象。其中包括布尔值列表（检查 False 值是否先于 True 值出现）、数字列表、字符串列表（按字母顺序排列）、集合列表（子集先于超集出现）等。
解决方案 25：
这个怎么样？简单又直接。
def is_list_sorted(al):
llength =len(al)
for i in range (llength):
if (al[i-1] > al[i]):
print(al[i])
print(al[i+1])
print('Not sorted')
return -1
else :
print('sorted')
return true
解决方案 26：
最简单的方法：
def isSorted(arr):
i = 1
while i < len(arr):
if(result[i] < result[i - 1]):
return False
i += 1
return True
解决方案 27：
对于整数或字符串，在 Python 3 及更高版本中绝对有效：
def tail(t):
return t[:]
letters = ['a', 'b', 'c', 'd', 'e']
rest = tail(letters)
rest.sort()
if letters == rest:
print ('Given list is SORTED.')
else:
print ('List NOT Sorted.')
=================================================== ===================
另一种判断给定列表是否排序的方法
trees1 = list ([1, 4, 5, 3, 2])
trees2 = list (trees1)
trees2.sort()
if trees1 == trees2:
print ('trees1 is SORTED')
else:
print ('Not sorted')
