为什么list+set方法使列表唯一比字典键方法快?

Question

下面是相同的timeit试验示例:

>>> import timeit
>>> setup = """
... from random import randint
... rand_list = [randint(0,10) for i in range(0,10000)]
... """
>>> timeit.Timer('list(set(rand_list))', setup=setup).repeat(5, 1000)
[0.17256593704223633, 0.17117094993591309, 0.17115998268127441, 0.17191100120544434, 0.17226791381835938]
>>> timeit.Timer('{ x:True for x in rand_list}.keys()', setup=setup).repeat(5, 1000)
[0.4490840435028076, 0.44455599784851074, 0.442918062210083, 0.4430229663848877, 0.44559407234191895]

可以看到，list(set(MY_LIST))方法大约比dictionary方法快2.5倍，对于较小的列表或较大的列表，结果是相似的。

谁能解释一下为什么会这样，也就是说，这两个步骤的执行在时间复杂度方面的功能差异?

Answer 1

在字典理解的第二个测试中运行一个包含10000个条目的Python循环;

你可以试试dict.fromkeys():

dict.fromkeys(rand_list).keys()

从rand_list的值创建一个字典，所有的值都设置为None。

这只是稍微慢了一点:

>>> import timeit
>>> from random import randint
>>> rand_list = [randint(0,10) for i in range(0,10000)]
>>> timeit.Timer('list(set(rand_list))', setup='from __main__ import rand_list').repeat(5, 1000)
[0.1437511444091797, 0.13837504386901855, 0.13841795921325684, 0.1395130157470703, 0.1474599838256836]
>>> timeit.Timer('dict.fromkeys(rand_list).keys()', setup='from __main__ import rand_list').repeat(5, 1000)
[0.18216991424560547, 0.17930316925048828, 0.18064308166503906, 0.17971301078796387, 0.17820501327514648]

这是意料之中的;一个dict()稍微更多的工作，因为你跟踪键和值，而不是仅仅在一个集合中的键。