python 如何检查列表是否排序?[duplicate]

vktxenjb  于 2023-03-06  发布在  Python
关注(0)|答案(5)|浏览(105)
    • 此问题在此处已有答案**:

Pythonic way to check if a list is sorted or not(27个答案)
8小时前关门了。
在python中,如何测试一个数字列表是否已经排序?

s4n0splo

s4n0splo1#

这只能通过迭代列表(隐式或显式)来实现:

all(b >= a for a, b in zip(the_list, the_list[1:])

但是如果你需要排序的话,为什么不直接排序呢?Python的排序算法在已经排序的列表上非常便宜--可能比上面的测试便宜。
编辑:因为这变成了一个关于性能的讨论,这里有一个使用懒惰迭代器的版本:

it = iter(the_list)
it.next()
all(b >= a for a, b in itertools.izip(the_list, it))

对于具有一百万个条目的随机排序列表,这比the_list == sorted(the_list)快10000倍以上。

rta7y2nd

rta7y2nd2#

some_list == sorted(some_list)
py49o6xq

py49o6xq3#

通常,您应该已经知道列表是否经过排序(因为输入就是这样定义的,或者您之前已经对它进行了排序)。
如果你需要验证一个列表是否排序了,如果没有,你想对它排序,那就对它排序吧。如果列表已经排序了,这是一个很便宜的操作,而且不比显式验证顺序贵多少。
换句话说:

mylist.sort()

现在你知道事情已经解决了。

wbgh16ku

wbgh16ku4#

更多的是对其他答案的评论,而不是答案,但这个网站使适当的评论是不可能的。
如果列表已经部分或完全排序,则排序解决方案会更快;如果列表可能是随机顺序,或者列表在早期就无序,则迭代解决方案会更快。
这有两个原因:第一,Python的排序方法在数据按照它理解的顺序(部分排序、反向排序等)给出时非常好,但如果数据是随机的或者是不可预测的,那么它就不会比任何其他排序方法做得更好;第二,如果它很早就发现列表是未排序的,那么迭代的解决方案可能会缩短几乎不做任何工作的时间。
这显示了相反的极端情况:

import timeit, random, itertools

def a(data):
    return all(b >= a for a, b in itertools.izip(data, itertools.islice(data, 1, None)))

def b(data):
    return data == sorted(data)

def main():
    data = range(1000000)
    print "Sorted, iterative:", timeit.timeit(lambda: a(data), number=10)
    print "Sorted, sort:", timeit.timeit(lambda: b(data), number=10)

    random.shuffle(data)
    print "Random, iterative:", timeit.timeit(lambda: a(data), number=10)
    print "Random, sort:", timeit.timeit(lambda: b(data), number=10)

在我的系统上产生了这些计时:

Sorted, iterative: 1.42838597298
Sorted, sort: 0.498414993286
Random, iterative: 0.000043
Random, sort: 10.5548219681

因此,在这些极端情况下,排序方法大约快3倍,而线性方法大约快...... 20万倍。
注意,这里的真实的差异是 not O(n)vs. O(nlogn);这两种复杂性之间的差别并没有那么大,主要的差别在于线性版本一旦发现两个值乱了序就可能短路,而排序版本总是要做所有的工作。
一个本地实现可以同时获得理想的性能,O(n)的复杂度,短路的能力,以及本地代码的低开销,这使得排序方法更快。如果(并且只有当!)性能真的很重要,这才是正确的解决方案。
(Note通常我不会推荐基于性能的解决方案,除非性能确实是一个问题,但这里值得注意的是,两种方法都没有比另一种简单得多,排序版本更容易理解,但迭代版本也一点都不复杂。)

50pmv0ei

50pmv0ei5#

if L == (lambda pp=[]: reduce(lambda p, i: pp.append(reduce(lambda t, i:
        (lambda t, i, j: (lambda l=[]: map(lambda x: (lambda xx=l.append(1):
        t[sum(l) - 1] if sum(l) not in map(1..__radd__, (i, j)) else (t[i] if
        sum(l) == j + 1 else t[j]))(), t))())(t, i, i + 1) if t[i] >= t[i + 1]
        else t, xrange(len(p) - 1), p)) or pp[-1], iter(lambda: len(pp) >= 2
        and list.__eq__(*pp[-2:]), True), L))():
    print "yeah, it's sorted"

相关问题