检查列表是否已排序的 Pythonic 方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3755136/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Pythonic way to check if a list is sorted or not
提问by anijhaw
Is there a pythonic way to check if a list is already sorted in ASCor DESC
是否有一种pythonic方法来检查列表是否已经排序ASC或DESC
listtimestamps = [1, 2, 3, 5, 6, 7]
something like isttimestamps.isSorted()that returns Trueor False.
类似的东西isttimestamps.isSorted()返回True或False。
I want to input a list of timestamps for some messages and check if the the transactions appeared in the correct order.
我想输入一些消息的时间戳列表，并检查交易是否以正确的顺序出现。
采纳答案by Wai Yip Tung
Actually we are not giving the answer anijhaw is looking for. Here is the one liner:
实际上，我们并没有给出 anijhaw 正在寻找的答案。这是一个班轮：
all(l[i] <= l[i+1] for i in xrange(len(l)-1))
For Python 3:
对于 Python 3：
all(l[i] <= l[i+1] for i in range(len(l)-1))
回答by aaronasterling
I would just use
我只会用
if sorted(lst) == lst:
# code here
unless it's a very big list in which case you might want to create a custom function.
除非它是一个非常大的列表，在这种情况下您可能想要创建一个自定义函数。
if you are just going to sort it if it's not sorted, then forget the check and sort it.
如果您只是要对它进行排序，如果它没有排序，那么忘记检查并对其进行排序。
lst.sort()
and don't think about it too much.
不要想太多。
if you want a custom function, you can do something like
如果你想要一个自定义函数，你可以做类似的事情
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
This will be O(n) if the list is already sorted though (and O(n) in a forloop at that!) so, unless you expect it to be not sorted (and fairly random) most of the time, I would, again, just sort the list.
如果列表已经排序，这将是 O(n)（并且 O(n) 在for循环中！）再次，只需对列表进行排序。
回答by Wai Yip Tung
SapphireSunis quite right. You can just use lst.sort(). Python's sort implementation (TimSort) check if the list is already sorted. If so sort() will completed in linear time. Sounds like a Pythonic way to ensure a list is sorted ;)
SapphireSun 说得很对。你可以只使用lst.sort(). Python 的排序实现 (TimSort) 检查列表是否已经排序。如果是这样， sort() 将在线性时间内完成。听起来像是确保列表排序的 Pythonic 方式；)
回答by PaulMcG
This iterator form is 10-15% faster than using integer indexing:
这种迭代器形式比使用整数索引快 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:]))
回答by Nathan Farrington
I ran a benchmark and . These benchmarks were run on a MacBook Pro 2010 13" (Core2 Duo 2.66GHz, 4GB 1067MHz DDR3 RAM, Mac OS X 10.6.5).sorted(lst, reverse=True) == lstwas the fastest for long lists, and all(l[i] >= l[i+1] for i in xrange(len(l)-1))was the fastest for short lists
我运行了一个基准测试，。这些基准测试在 MacBook Pro 2010 13"（Core2 Duo 2.66GHz，4GB 1067MHz DDR3 RAM，Mac OS X 10.6.5）上运行。sorted(lst, reverse=True) == lst在长列表中all(l[i] >= l[i+1] for i in xrange(len(l)-1))是最快的，对于短列表是最快的
UPDATE:I revised the script so that you can run it directly on your own system. The previous version had bugs. Also, I have added both sorted and unsorted inputs.
更新：我修改了脚本，以便您可以直接在自己的系统上运行它。之前的版本有bug。此外，我添加了已排序和未排序的输入。
- Best for short sorted lists:
all(l[i] >= l[i+1] for i in xrange(len(l)-1)) - Best for long sorted lists:
sorted(l, reverse=True) == l - Best for short unsorted lists:
all(l[i] >= l[i+1] for i in xrange(len(l)-1)) - Best for long unsorted lists:
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)) - 最适合长排序列表：
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))
So in most cases there is a clear winner.
所以在大多数情况下，有一个明显的赢家。
UPDATE:aaronsterling's answers (#6 and #7) are actually the fastest in all cases. #7 is the fastest because it doesn't have a layer of indirection to lookup the key.
更新：aaronsterling 的答案（#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
回答by Amit Moscovich
As noted by @aaronsterling the following solution is the shortest and seems fastest when the array is sorted and not too small: def is_sorted(lst): return (sorted(lst) == lst)
正如@aaronsterling 所指出的，以下解决方案是最短的，并且在对数组进行排序且不太小时似乎最快： def is_sorted(lst): return (sorted(lst) == lst)
If most of the time the array is not sorted, it would be desirable to use a solution that does not scan the entire array and returns False as soon as an unsorted prefix is discovered. Following is the fastest solution I could find, it is not particularly elegant:
如果大部分时间数组未排序，则最好使用不扫描整个数组并在发现未排序前缀后立即返回 False 的解决方案。以下是我能找到的最快的解决方案，它不是特别优雅：
def is_sorted(lst):
it = iter(lst)
try:
prev = it.next()
except StopIteration:
return True
for x in it:
if prev > x:
return False
prev = x
return True
Using Nathan Farrington's benchmark, this achieves better runtime than using sorted(lst) in all cases except when running on the large sorted list.
使用 Nathan Farrington 的基准测试，除了在大型排序列表上运行时，在所有情况下都比使用 sorted(lst) 获得更好的运行时间。
Here are the benchmark results on my computer.
这是我电脑上的基准测试结果。
sorted(lst)==lst solution
排序（lst）==lst解决方案
- L1: 1.23838591576
- L2: 4.19063091278
- L3: 1.17996287346
- L4: 4.68399500847
- L1：1.23838591576
- L2：4.19063091278
- L3：1.17996287346
- L4：4.68399500847
Second solution:
第二种解决方案：
- L1: 0.81095790863
- L2: 0.802397012711
- L3: 1.06135106087
- L4: 8.82761001587
- L1：0.81095790863
- L2：0.802397012711
- L3：1.06135106087
- L4：8.82761001587
回答by Anthon
Although I don't think there is a guarantee for that the sortedbuilt-in calls its cmp function with i+1, i, it does seem to do so for CPython.
尽管我认为不能保证sorted内置函数使用 调用它的 cmp 函数i+1, i，但对于 CPython 来说似乎确实如此。
So you could do something like:
所以你可以这样做：
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])
Or this way (without if statements -> EAFP gone wrong? ;-) ):
或者这样（没有 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
回答by orlade
Not very Pythonic at all, but we need at least one reduce()answer, right?
一点都不 Pythonic，但我们至少需要一个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')
The accumulator variable simply stores that last-checked value, and if any value is smaller than the previous value, the accumulator is set to infinity (and thus will still be infinity at the end, since the 'previous value' will always be bigger than the current one).
累加器变量只是存储最后检查的值，如果任何值小于前一个值，则累加器设置为无穷大（因此最后仍然是无穷大，因为“前一个值”将始终大于当前的）。
回答by hughdbrown
I'd do this (stealing from a lot of answers here [Aaron Sterling, Wai Yip Tung, sorta from Paul McGuire] and mostly Armin Ronacher):
我会这样做（从这里的很多答案中窃取 [Aaron Sterling, Wai Yip Tung, sorta from 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))
One nice thing: you don't have to realize the second iterable for the series (unlike with a list slice).
一件好事：您不必实现该系列的第二个可迭代对象（与列表切片不同）。
回答by Martin Spacek
I use this one-liner based on numpy.diff():
我使用这个基于 numpy.diff() 的单线：
def issorted(x):
"""Check if x is sorted"""
return (numpy.diff(x) >= 0).all() # is diff between all consecutive entries >= 0?
I haven't really timed it against any other method, but I assume it's faster than any pure Python method, especially for large n, since the loop in numpy.diff (probably) runs directly in C (n-1 subtractions followed by n-1 comparisons).
我还没有真正将它与任何其他方法进行计时，但我认为它比任何纯 Python 方法都快，尤其是对于大 n，因为 numpy.diff 中的循环（可能）直接在 C 中运行（n-1 减法后跟 n -1 比较）。
However, you need to be careful if x is an unsigned int, which might cause silent integer underflow in numpy.diff(), resulting in a false positive. Here's a modified version:
但是，如果 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()
