按索引从列表中获取元素比按键从字典中获取元素更快。

Question

我有以下脚本需要测试哪个更快：

1.从列表中按索引获取元素，或者 2.从字典中按键获取元素。

import timeit
import random

lis1 = [random.randint(1,10000) for x in xrange(0,10001)]
dict1 = {x:random.randint(1,10000) for x in xrange(0,10001)}

def list_lookup():
    index = random.randint(0,10000)
    x = lis1[index]

def dict_lookup():
    index = random.randint(0,10000)
    x = dict1[index]


def main():
  print timeit.repeat("list_lookup()", "from __main__ import list_lookup",number=1000000)
  print timeit.repeat("dict_lookup()", "from __main__ import dict_lookup",number=1000000)

if __name__ == '__main__':
  main()

它正在输出以下内容。

[1.208083152770996, 1.1942389011383057, 1.1882140636444092]
[1.2461788654327393, 1.2427518367767334, 1.2414629459381104]

虽然差别似乎微不足道，但似乎字典查找需要稍微更长的时间。

这是因为在字典中获取元素涉及两个步骤——首先对键进行哈希，然后获取值（第二步），而在列表中，我们只是从列表的特定位置的内存地址获取值。

- Anurag Sharma

---

基本上答案是“是”的，但这个回答太短了，不能算是一个完整的回答。 - Steve Barnes

Answer 1

实际上有三个步骤，还需要比较 (==) 找到的键与给定键，以确保返回正确的值，而不是另一个被映射到同一桶的值。

此外，低效的哈希 / 冲突可能会导致进一步的缓慢（因此，字典查找的最坏情况为O(N)）。

- shx2

Answer 2

在列表中查找的时间复杂度为O(n)，在字典中查找的平均时间复杂度为O(1)，与数据结构中的项目数量有关。

欲了解更多信息，请参考此答案这里

- MONTYHS

---

从列表中按索引获取项目与“查找”不同。 - jepio