python - 为什么 sorted(set(A)) 比 set(sorted(A)) 快？

Question

我有一个数字数组。我想对它们进行排序并删除重复项。 This答案建议使用 set 和 sort 进行此类操作。操作顺序不应改变结果，因此我测量了计算时间。

from numpy.random import randint
from time import clock

n = 1000000

A=randint(0,n,n)

t1=clock()
B=sorted(set(A))
t2=clock()
C=set(sorted(A))
t3=clock()

print t2-t1, t3-t2

>>> 0.48011 1.339263

sorted(set(A)) 大约比 set(sorted(A)) 快三倍。

是什么让一个比另一个更快？另外，有没有更快的方法呢？

Answer 1

这是因为当你打电话时:

设置(排序(A))

您正在对原始完整列表进行排序，然后过滤掉重复值。但是，当您调用时:

排序(集合(A))

您首先通过使用 set 删除重复值来缩短列表，然后对更小的列表进行排序，因此时间更短。

希望这是有道理的。

例如

>>> A = [1,2,3,1,2,3,1,2,3,1,2,3]
>>> A = sorted(A)
[1,1,1,1,2,2,2,2,3,3,3,3]

>>> set(A)
{1, 2, 3}

On the other hand:

>>> A = [3,2,1,3,2,1,3,2,1,3,2,1]
>>> A = set(A)
{3, 2, 1}

>>> sorted(A)
{1, 2, 3}

正如@Barmar 所说，排序比删除重复项慢得多，因此当您必须对一个小得多的列表(我上面示例中列表的 1/4)进行排序时，会有实时增益

时间基准

a = [1,2,3] * 10000

set(sorted(a)) --> 0.1890001297
sorted(set(a)) --> 0.0079998970