高效的词典搜索？

我有一个关于通过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秒内超过35万行代码。

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

来源

2013-09-30 Brumdog22

一般来说，你不想捕获_all_异常，但只有你期望的异常，并在发现它时处理。在这里，例如，使用：'除了KeyError：...' – askewchan

你的示例代码很混乱。在第一个代码片段中，你正在检查'data_dict'中的'key'，但在第二个中，只有'key'不在'input_data'中才会导致'KeyError'异常。这使得很难提供完整的答案... – martineau

问题在于，对于每次测试，您都会使用.keys()生成一个新的密钥列表。随着密钥列表变长，所需时间会增加。还有as noted by dckrooney，对密钥的搜索变成线性的，而不是利用字典的哈希表结构。

替换：

if key in data_dict:

来源

2013-09-30 21:08:45

Hooray也为此添加了最合适的方法！ –

啊，好吧。我知道。keys（）重新生成了密钥列表，所以我认为这是问题所在，但我不知道你可以做“如果键入字典：”。谢谢您的帮助。 – Brumdog22

*'对于每次测试，您使用.keys（）生成一个新的密钥列表* *因此，每次调用key（）函数** ** –

这并不回答这个问题，而是避免了这个问题。尝试使用collections.defaultdict。您将不需要0或try/except。

from collections import defaultdict 

data_dict = defaultdict(list) 
for keyStr, load_val in data: 
    data_dict[keyStr].append(load_val)

来源

2013-09-30 21:08:17 wflynny

或者'data_dict [keyStr] = input_data.get（keyStr，[load_val]）' –

这是因为data_dict.keys()返回一个列表包含在字典中（至少在Python 2.x的）的键。其中，为了找到一个密钥是否在列表中，需要线性搜索。

而试图访问字典的元素直接利用了字典的真棒属性，因此访问几乎是瞬间的。

来源

2013-09-30 21:08:37

在python3中'data_dict.keys（）'返回迭代器。 – defuz

@defuz不知道，我仍然主要使用Python 2.7。更新了答案，谢谢！ –

有一个类似于在try功能应该可以帮助您： dict.get(key, default)

data_dict[keyStr] = data_dict.get(keyStr, '') + load_val

来源

2013-09-30 21:09:50 SQLesion

data_dict.keys()返回字典中键的无序名单。因此，每次检查字典中是否存在给定密钥时，都会对整个密钥列表进行线性搜索（O（n）操作）。列表越长，搜索给定密钥所用的时间越长。

将此对比为data_dict[keyStr]。这将执行一个哈希查找，这是一个O（1）操作。它不直接依赖字典中的键的数量;即使添加更多的键，检查字典中给定键是否保持不变的时间也是如此。

来源

2013-09-30 21:11:41 dckrooney

你也可以简单地使用

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

来源

2013-09-30 21:11:44

早在过去，我们使用setdefault：

data_dict.setdefault(keyStr, []).append(load_val)

来源

2013-09-30 21:26:06

正如一些人所指出的，问题在于，key in data_dict.keys()使用无序list从keys()方法返回的事实（在Python 2.x中），这需要linear timeO（n）来搜索thr尽管如此，这意味着运行时间随字典大小线性增加，并且随着大小的增加，生成密钥列表本身将需要更长和更长的时间。

在另一方面，key in data_dict只需要恒定的时间O（1）的平均值，以执行字典的大小的一个搜索无论因为内部它确实hash table查找。另外，这个散列表已经存在，因为它是字典内部表示的一部分，因此在使用它之前不必生成。

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

但是，在这种情况下，通过将数据存储在内置的collections模块中找到的称为defaultdict的字典的专用版本中，可以完全避免搜索速度问题。下面是如果你使用一个你的代码的外观：

from collections import defaultdict 

input_data = defaultdict(float) # (guessing factory type) 
... 
data_dict[keyStr] = input_data[keyStr] + load_val

当有对input_data[keyStr]一个的预先存在的条目将自动使用默认值（0.0在这个例子中float）产生。正如你所看到的，代码更短，速度更快，所有这些都不需要任何if测试或异常处理。

来源

2013-09-30 23:31:40 martineau

高效的词典搜索？

回答

相关问题