Python list.index() 与字典

Question

我有大约 50 个字符串的列表。我会反复（可能数万次）需要知道列表中项目的位置。是每次都使用 list.index() 更好，还是创建一个字典将每个项目映射到它的位置？（我的直觉是创建字典，但我不知道列表索引的基础是什么，它可能是多余的。）

Answer 1

使用字典映射而不是在列表中查找项目。字典映射在计算之前使用每个项目的哈希值。哈希比较要快得多，并且可以更快地找到（在恒定时间内），而不是通过列表查找并逐项评估（在线性时间内缩放）。

您可以像这样分析您的查询：

import timeit
setup = 'from __main__ import foo_dict, foo_list'

要将比较限制为仅 50 长的列表：

l = list(str(i) for i in range(50))
d = dict((str(i), i) for i in range(50))
def foo_dict(k):
    return d[k]

def foo_list(k):
    return l.index(k)

timeit.repeat('[foo_dict(str(i)) for i in range(50)]', setup)

returns 对我来说：

[20.89474606513977, 23.206938982009888, 22.23725199699402]

和

timeit.repeat('[foo_list(str(i)) for i in range(50)]', setup)

returns:

[47.33547496795654, 47.995683908462524, 46.79590392112732]

字符串的字典查找要快得多，因为它使用哈希 table，而索引的列表查找要慢得多，因为它必须根据要查找的字符串评估其中的每个字符串.

Answer 2

list.index() 将遍历列表，直到找到它要查找的项目，这是一个线性时间操作。相比之下，在字典中查找字符串是一个常量时间操作，因此字典方法可能具有更好的性能。

由于您的键是字符串并且您拥有的键相对较少，因此您可能想要探索的另一种数据结构是 trie。

Answer 3

字典会快很多，创建起来也很快：

indexer = dict((v, i) for i, v in enumerate(thelist))

enumerate 为 i in range(len(thelist)) 生成 (i, thelist[i])，从那里生成器表达式 "swapping" 元组（因为您需要将内容映射到索引，反之亦然）。

请注意，这仅在每个列表项都是可散列的情况下才有效，但既然你说这些项目是字符串，你应该没问题。

dict，除其他外，快速将 (key, value) 元组的可迭代转换为相应的字典。

Python list.index() 与字典

Python list.index() versus dictionary

python

dictionary

list