在 Python 中对集合进行排序与​​对列表进行排序在时间上存在巨大差异

我想知道我是否应该将数据结构作为集合或列表。大多数情况下我会进行集合运算，但最终我需要对其进行排序。

我想知道是否应该先将集合设为列表，然后使用sorted(list(my_set))，或者立即对集合进行排序sorted(my_set)。可以说，我可能会考虑一个通用的“列出”阶段，因为在那个时间点拥有一个有序的迭代可能无论如何都是有意义的。

所以我决定测试一下，希望列表能更快。

基准测试：

import time
def sorter(x):
    t1 = time.time()
    for i in range(1000000):
        sorted(x)
    return time.time() - t1

Data:

one = range(1000)
a1 = list(one)
b1 = set(one)
sorter(a1)
# time: 16.5 s 
sorter(b1)
# time: 20.7 s

然后我意识到这可能与元素已经就位有关，并记住了这个令人惊奇的问题和答案 https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array/11227902#11227902.

然后，我尝试了一些随机数据：

two = numpy.random.randint(1, 1000, 1000)
a2 = list(two)
b2 = set(two)

结果：

sorter(a2)
# time: 4min 49s
sorter(b2)
# time: 18.9 s

差别这么大，到底是怎么回事？

奖励：它甚至在一分钟的时间出现，sorted(set(a_list))令人印象深刻地快于sorted(a_list).

事实上，在第二种情况下，可能存在重复项，这些重复项将被过滤，从而加快排序速度。

我对您的代码进行了一些扩展，希望这能让您深入了解正在发生的事情：

import numpy
import uuid
import random
import time

def sorter(x):
    t1 = time.time()
    for i in range(10000):
        sorted(x)
    return time.time() - t1

def pr(name, x):
    print('sorter {:<12s} {:<11} (length {:>4})'.format(
        name, '{:.8}'.format(sorter(x)), len(x)))

a2sizes = []
b2sizes = []

for x in range(1000):
    two = numpy.random.randint(1, 1000, 1000)
    a2 = list(two)
    b2 = set(two)
    a2sizes.append(len(a2))
    b2sizes.append(len(b2))

print 'average number of elements in a2', sum(a2sizes)/len(a2sizes)
n = sum(b2sizes)/len(b2sizes)
print 'average number of elements in b2', n

这打印出：

average number of elements in a2 1000
average number of elements in b2 632

这是因为随机数范围内发生冲突

print
pr('a2', a2)
# making a list of set gives you already sorted elements
y = list(b2)
pr('y', y)
random.shuffle(y)
pr('shuffled y ', y)
pr('b2', b2)

给出输出：

sorter a2           2.492537    (length 1000)
sorter b2           0.25028086  (length  633)
sorter y            0.19689608  (length  633)
sorter shuffled y   1.4935901   (length  633)

That b2会更快，因为元素更少是合乎逻辑的，但是如果您首先创建集合的列表，那么这会更快，这一定有某种原因。如果您重新整理该列表，它会再次变慢，这也是合乎逻辑的，并且在补偿列表长度时，整理后的结果相当接近 a2 的结果。

因此，让我们尝试在列表中添加其他内容：

b3 = set()
for x in range(1000):
    b3.add(uuid.uuid4())

print '\nuuid elements', len(b3)

a3 = list(b3)
pr('a3', a3)
random.shuffle(a3)
pr('shuffled a3', a3)
pr('b3', b3)

给出（如果元素少于 1000 个，我会感到相当惊讶）：

uuid elements 1000
sorter a3           32.437758   (length 1000)
sorter shuffled a3  32.178433   (length 1000)
sorter b3           32.163802   (length 1000)

所以它一定与集合中的数字有关：

previous = -1
ordered = True
for popped in b2:
    if popped < previous:
        print 'popped', popped, previous
        ordered = False
    previous = popped

print '\nOrdered', ordered

给你：

Ordered True

不是迭代，而是set https://docs.python.org/2/library/stdtypes.html#set has a pop()您可以尝试使用的功能：

pop()

从集合中删除并返回任意元素。如果集合为空，则引发 KeyError。

So lets 任意地从集合中检索元素b2看看是否有什么特别的：

previous = -1
ordered = True
while(b2):
    popped = b2.pop()
    if popped < previous:
        print 'popped', popped, previous
        ordered = False
    previous = popped

print '\nOrdered', ordered

给出相同的结果：

Ordered True

因此，任意检索数字集合的元素会按顺序检索这些数字，独立于这些数字的输入顺序。 由于迭代是列表制作一次检索一个元素以附加到列表的方式，因此结果是list(b2)是一个有序列表，使用以下命令可以快速排序Timsort http://en.wikipedia.org/wiki/TimsortPython 中使用的算法。