24

我有一个关于在 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]？为什么 Pythontry在字典中搜索键时不使用该语句？

4

9 回答 9

36

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

用。。。来代替：

if key in data_dict:
于 2013-09-30T21:08:45.713 回答
9

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

将此与data_dict[keyStr]. 这将执行哈希查找，这是一个 O(1) 操作。它不（直接）取决于字典中的键数；即使您添加更多键，检查给定键是否在字典中的时间也保持不变。

于 2013-09-30T21:11:41.977 回答
7

您也可以简单地使用

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-30T21:11:44.057 回答
5

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

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

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

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

from collections import defaultdict

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

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

于 2013-09-30T23:31:40.790 回答
4

这并没有回答问题，而是避免了它。尝试使用collections.defaultdict. 你不需要if/elseor try/except。

from collections import defaultdict

data_dict = defaultdict(list)
for keyStr, load_val in data:
    data_dict[keyStr].append(load_val)
于 2013-09-30T21:08:17.457 回答
3

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

然而，尝试直接访问字典的元素会利用字典的强大属性，因此访问几乎是即时的。

于 2013-09-30T21:08:37.783 回答
2

回到过去，我们使用setdefault：

data_dict.setdefault(keyStr, []).append(load_val)
于 2013-09-30T21:26:06.423 回答
1

有一些类似于 try 函数的东西可以帮助你： dict.get(key, default)

data_dict[keyStr] = data_dict.get(keyStr, '') + load_val
于 2013-09-30T21:09:50.313 回答
1

作为额外的分析，我做了一个简单的性能测试，看看问题中提到的 try/except 方法与使用“if key in data_dict”而不是“if key in data_dict.keys()”的建议解决方案相比如何（我是使用 Python 3.7）：

    import timeit

    k = '84782005' # this keys exists in the dictionary
    def t1():
        if k in data_dict:
            pass
    def t2():
        if k in data_dict.keys():
            pass
    def t3():
        try:
            a = data_dict[k]
        except:
            pass

    print(timeit.timeit(t1,number= 100000))
    print(timeit.timeit(t2,number= 100000))
    print(timeit.timeit(t3,number= 100000))

    >> 0.01741484600097465
    >> 0.025949209000827977
    >> 0.017266065000512754

对于字典中已经存在的键，try/except 和提供的解决方案的搜索时间似乎相同。但是，如果密钥不存在：

    k = '8' # this keys does NOT exist in the dictionary
    def t1():
        if k in data_dict:
            pass
    def t2():
        if k in data_dict.keys():
            pass
    def t3():
        try:
            a = data_dict[k]
        except:
            pass

    print(timeit.timeit(t1,number= 100000))
    print(timeit.timeit(t2,number= 100000))
    print(timeit.timeit(t3,number= 100000))

    >> 0.014406295998924179
    >> 0.0236777299996902
    >> 0.035819852999338764

这个异常似乎比使用 '.keys()' 需要更多的时间！所以，我支持马克提出的解决方案。

于 2019-07-16T18:27:41.377 回答