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

Question

我最近询问了创建 10 的幂的最快方法，结果发现最快的方法实际上是一种偷偷摸摸的解决方法，您首先创建所有可能的值，然后在需要时简单地查找它们。

在解决方案中，alist被用作查找表，但是，我刚刚了解到，在查找操作方面dicts 应该要快得多（另请参见此处）。但是当我尝试使用 adict作为查找表时，过程实际上更慢：

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

Answer 1

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

i这是“我的列表中的 10 的次方是多少？”之间的区别。与“x我的列表中有十的幂吗？”

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

造成混乱的原因是“查找”既可以指索引操作，也可以指检查是否存在，具体取决于上下文。

以下概述了如何在列表和字典中执行等效操作：

	列表	字典
索引	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()