为什么在这种情况下词典查找速度不快？

问题描述

我最近询问了the fastest way to create powers of ten，结果发现最快的方法实际上有点像sneaky workaround，您首先创建所有可能的值，然后在需要的时候简单地查找它们。

在解决方案中，list被用作查找表，然而，我刚刚了解到dictsshould be much faster当涉及到查找操作时(另请参见here)。但当我尝试使用dict作为查找表时，过程实际上较慢：

n = 200
 18 ns   18 ns   18 ns  f[n]  # list
 22 ns   22 ns   22 ns  g[n]  # dict

n = -200
 18 ns   18 ns   18 ns  f[n]  # list
 29 ns   29 ns   29 ns  g[n]  # dict

为什么？这是否与keys是整数而不是字符串有关？(我猜sets在这种情况下不能使用？)

以下是我运行的代码：

from timeit import repeat


solutions = [
    'f[n]  # list',
    'g[n]  # dict',
]

for n in 200, -200:
    print(f'n = {n}')
    setup = f'''
n = {n}
f = [10.0 ** i for i in [*range(309), *range(-323, 0)]]
g = {{i: 10.0 ** i for i in range(-323, 309)}}
'''
    for solution in solutions:
        try:
            ts = sorted(repeat(solution, setup, repeat=50))[:3]
        except OverflowError:
            ts = [None] * 3
        print(
            *('%3d ns ' % (t * 1e3) if t else ' error ' for t in ts), solution
        )
    print()

---

解决方案

collection[key_or_index]对于list和dict都是O(1)。不同的是key_or_value in collection的性能。

我的列表中十的<[2-9]次方是多少？x列表中的x是10的次方吗？

列表的索引速度略快，因为字典需要计算其键的哈希，并检查冲突。

---

混淆是因为"；lookup"；既可以引用索引操作，也可以根据上下文检查是否存在。

---

这里概述了如何在列表和词典中执行相同的操作：

	列表	词典
索引	lst[i]	dct[key]
检查是否存在键/索引	-len(lst) <= i < len(lst)	key in dct
检查值是否存在	value in lst	value in dct.values()
循环遍历值	for value in lst	for value in dct.values()
循环遍历键/索引	for i in range(len(lst))	for key in dct
同时循环	for i, value in enumerate(lst)	for key, value in dct.items()