在Python中排序集合与排序列表之间的时序差异很大

Question

我想知道我是否应该将我的数据结构作为集合或列表.大多数情况下我会设置操作,但最后我需要对其进行排序.

我想知道我是否应该首先将集合设置为列表,然后使用sorted(list(my_set)),或者立即对集合进行排序sorted(my_set).可以说,我可能会考虑一般的"列表"阶段,因为在那个时间点有一个有序的可迭代可能有意义.

所以我决定测试它,希望列表更快.

Benchmarker:

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

数据:

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

然后我意识到这可能与元素已经存在的事实有关,并且记住了这个惊人的问题和答案.

然后,我尝试了一些随机数据:

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

实际上,在第二种情况下,可以存在可以过滤的重复,从而加快排序.

Answer 1

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

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)

这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

集合有一个pop()可以尝试使用的函数，而不是迭代：

流行音乐（）

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

因此，让我们从集合中任意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

因此，任意检索数字集合的元素会按顺序检索这些数字，而与这些数字的放入顺序无关。由于迭代是列表制作一次检索一个元素以追加到列表的方式，因此结果是一个有序列表，并且使用 Python 中使用的Timsortlist(b2)算法可以快速排序。