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

Question

我最近询问了 , and it turned out that the fastest way is actually a bit of a ，您首先创建所有可能的值，然后在需要时简单地查找它们。

在解决方案中，list被用作查找-table，但是，我刚刚了解到dicts should be much faster when it comes to lookup operations (see e.g. also here ).但是当我尝试 dict 作为查找 table 时， 过程实际上更慢 :

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] 对于 list 和 dict 都是 O(1)。不同的是 key_or_value in collection.

的表现

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

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

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

这里概述了如何在列表和字典中进行等效操作：

	List	Dictionary
Indexing	`lst[i]`	`dct[key]`
Checking for presence of key/index	`-len(lst) <= i < len(lst)`	`key in dct`
Checking for presence of value	`value in lst`	`value in dct.values()`
Looping over values	`for value in lst`	`for value in dct.values()`
Looping over keys/indexes	`for i in range(len(lst))`	`for key in dct`
Looping over both	`for i, value in enumerate(lst)`	`for key, value in dct.items()`

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

Why is the dictionary lookup not faster in this case?

python

list

dictionary

lookup