为什么sorted（set(A)）比set（sorted(A)）快？

Question

我有一个数组。我想对它们进行排序并删除重复项。这个答案建议使用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

是什么使一个比另一个快？还有，有没有更快的办法呢？

Answer 1

这是因为当你打电话：

集（排序(A))

您正在对原始的完整列表进行排序，然后筛选出重复的值。然而，当您调用：

希望这有意义。

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