用于检查列表是否已排序的Pythonic方法

Question

是否有pythonic方法来检查列表是否已经排序ASC或DESC

listtimestamps = [1, 2, 3, 5, 6, 7]

类似的东西isttimestamps.isSorted()返回True或False.

我想输入一些消息的时间戳列表,并检查事务是否以正确的顺序出现.

Answer 1

实际上我们没有给出anijhaw正在寻找的答案.这是一个班轮:

all(l[i] <= l[i+1] for i in xrange(len(l)-1))

对于Python 3:

all(l[i] <= l[i+1] for i in range(len(l)-1))

Answer 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)(并且for在那个循环中为O(n)!)所以,除非你期望它在大多数时间没有排序(并且相当随机),我会,再次,只需对列表进行排序.

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

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

这种实现很快,适用于任何迭代.

Answer 5

我运行了一个基准测试,并且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)上运行.

更新:我修改了脚本,以便您可以直接在自己的系统上运行它.以前的版本有bug.另外,我添加了已排序和未排序的输入.

• 最适合短排序列表: 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))

所以在大多数情况下都有明显的赢家.

更新: 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

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

一件好事:你不必为系列实现第二个迭代(与列表切片不同).

Answer 7

从 开始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)]

Answer 8

我使用这个基于 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()

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