python - 为什么使列表唯一的 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)) 方法比字典方法快大约 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()多一些，而不仅仅是一组中的键。