高效的字典搜索？

Question

我有一个关于在Python 中搜索大型词典的效率的快速问题.我正在读取一个以逗号分隔的大文件,并从每一行获取一个键和值.如果我的密钥已经在字典中,我将值添加到字典中列出的值,如果字典中不存在该键,我只需添加该值.以前我用过这个:

if key in data_dict.keys():
    add values
else:
    data_dict[key] = value

这开始很快,但随着字典的增长,它变得越来越慢,到了我根本无法使用它的程度.我改变了我在字典中搜索键的方式:

try:
    # This will fail if key not present
    data_dict[keyStr] = input_data[keyStr] + load_val
except:
    data_dict[keyStr] = load_val

这是无限快的,并且可以在3秒内读/写超过350,000行代码.

我的问题是为什么if key in data_dict.keys():命令比调用时间要长得多try: data_dict[keyStr]？为什么Python try在字典中搜索密钥时不会使用该语句？

Answer 1

问题是,对于每个测试,您都要生成一个新的密钥列表.keys().随着密钥列表变长,所需时间也会增加.同样如dckrooney所述,对密钥的搜索变为线性,而不是利用字典的哈希表结构.

用...来代替:

if key in data_dict:

Answer 2

data_dict.keys()返回字典中未排序的键列表.因此,每次检查给定键是否在字典中时,您都在对键列表进行线性搜索(O(n)操作).列表越长,搜索给定密钥所需的时间越长.

对比这个data_dict[keyStr].这执行散列查找,这是O(1)操作.它(直接)不依赖于字典中的键数; 即使添加更多键,检查给定键是否在字典中的时间也保持不变.

Answer 3

你也可以简单地使用

if key in data_dict:

代替

 if key in data_dict.keys():

如上所述,第一个是直接散列查找 - 直接计算预期的偏移量,然后检查 - 它大致为O(1),而密钥检查是线性搜索,即O(n).

In [258]: data_dict = dict([(x, x) for x in range(100000)])

In [259]: %timeit 999999 in data_dict.keys()
100 loops, best of 3: 3.47 ms per loop

In [260]: %timeit 999999 in data_dict
10000000 loops, best of 3: 49.3 ns per loop

Answer 4

正如其他几个人所指出的，问题在于使用从方法返回的key in data_dict.keys()无序（在 Python 2.x 中），这需要线性时间O(n)来搜索，这意味着运行时间随着字典线性增加\ 的大小，加上生成键列表本身将随着大小的增加而花费越来越长的时间。listkeys()

\n

另一方面，无论字典的大小如何，平均key in data_dict只需要恒定时间O(1)来执行搜索，因为它在内部执行hash\xc2\xa0table查找。此外，这个哈希表已经存在，因为它是字典内部表示的一部分，因此在使用它之前不必生成。

\n

Python 不会自动执行此操作，因为in运算符只知道其两个操作数的类型，而不知道它们的源，因此它无法自动优化第一种情况，即它看到的只是键和列表。

\n

defaultdict然而，在这种情况下，通过将数据存储在内置模块中称为“find”的专门版本的字典中，可能可以完全避免搜索速度的问题collections。如果您使用了这样的代码，您的代码可能如下所示：

\n

from collections import defaultdict\n\ninput_data = defaultdict(float)  # (guessing factory type)\n...\ndata_dict[keyStr] = input_data[keyStr] + load_val\n

\n

当没有预先存在的条目时，input_data[keyStr]将自动生成一个默认值（0.0在float本例中）。正如您所看到的，代码更短并且很可能更快，所有这些都不需要任何if测试或异常处理。

\n