python: 列表查找 vs 字典查找

Question

我写了一段代码，每次循环的时候列表的大小都会增加，循环次数可以达到将近10万次。

示例：

def do_something():
    Lst.append(k)

while N < 100000:
    if k not in Lst:
        do_something()

现在，我注意到这个方法运行得非常慢。请注意，我确实设置了setrecursionlimit()。其实挺尴尬的，这个程序一直运行了好几个小时。

后来，在尝试寻找优化代码的方法时，我把列表转换成了字典。所以代码看起来像这样：

def do_something():
    Dct[k] = True

while N < 100000:
    if Dct[k] == False:
        do_something()

结果代码运行得快了很多。在阅读了一些关于这个话题的讨论后，我意识到慢的并不是列表，而是处理大列表数据时内存的管理。这个网站 https://wiki.python.org/moin/TimeComplexity 解释了列表和字典的查找时间复杂度。对于列表来说是O(n)，而字典的查找是O(1)。这就是字典表现更好的原因吗？那么，列表和字典的查找到底是怎么进行的呢？

Answer 1

是的，字典查找的时间是固定的。你的 if k not in Lst 可能需要扫描整个列表，来检查这个数字是否还不在列表中，然后再添加。这种扫描过程让列表的包含测试需要 O(n) 的时间，这正是让你的算法变慢的原因。

而 Python 字典则使用一个叫做 哈希表 的东西来检查某个值是否存在。每个键都会被转换成一个数字，这个数字再用来作为哈希表中的索引。如果在这个位置找到的键和你要测试的键相同，那就说明找到了匹配的值。哈希过程可能会出现冲突（两个值被哈希到同一个位置），但 Python 字典的实现有一个算法，可以有效地寻找下一个空位。如果找到了空位，那么包含测试就失败了，说明这个键不存在。

所以，要测试 k 是否在你的字典里，大多数情况下只需要进行一次计算。对于某些情况，可能需要多做几次测试。但总体来说，查找的时间是固定的。

如果你感兴趣，并且对 C 语言有一定了解，可以看看这个 C 语言的实现，里面有很多详细的说明。你也可以观看这个 2010 年 Pycon 的演讲，由 Brandon Rhodes 讲解 CPython 中 dict 的工作原理，或者买一本 《美丽的代码》，其中有 Andrew Kuchling 写的关于实现的章节。

你可能还想看看 set() 类型；它和字典一样，是一个无序的集合，具有 O(1) 的成员测试，但只有值，没有键：

some_set = set()

def do_something():
    some_set.add(k)

while N < 100000:
    if k not in some_set:
        do_something()

在内部，set() 对象也使用哈希表。