为什么排序(设置(A))比设置(排序(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

sorted(set(A))大约比set(排序(A))快三倍.

是什么让一个比另一个更快？此外,还有更快的方法吗？

Answer 1

这是因为当你打电话时:

set(sorted(A))

您正在排序原始完整列表,然后过滤掉重复的值.但是,当你打电话:

sorted(set(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