python - 在 Python 中高效创建(播种)大型字典

Question

我有一个很长(500K+ 行)的两列电子表格，如下所示:

Name    Code
1234    A
1234    B
1456    C
4556    A
4556    B
4556    C
...

因此，有一个元素(带有名称)可以有多个代码。但我想要一个每个元素出现的所有代码的列表，而不是每个代码一行。我想要的是这样的字典:

{"1234":["A","B"],"1456":["C"],"4556":["A","B","C"] ...]}

我尝试过的是这个(并且我不包括文件读取语法)。

    codelist = {}
    for row in rows:
        name,code = well.split()
        if name in codelist.keys():
            codelist[name].append(code)
        else:
            codelist[name] = [code]

这会创建正确的输出，但进度变得异常缓慢。所以我尝试用键启动我的字典:

allnames = [.... list of all the names ...]
codelist = dict.fromkeys(allnames)

for row in rows:

    name,code = well.split()
    if codelist[name]:
        codelist[name].append(code)
    else:
        codelist[name] = [code]

这要快得多，我的问题是为什么？程序不是每次都要搜索dict中的所有key吗？是否有另一种方法可以加速字典搜索而不包括遍历树？

有趣的是，在启动我的字典后，当我使用与之前相同的条件检查(if name in codelist.keys():)时，会出现错误。

Traceback (most recent call last):
  File .... 
    codelist[name].append(code)
AttributeError: 'NoneType' object has no attribute 'append'

现在，有一个键，但没有要附加的列表。所以我使用 codelist[name] ，它也是 <NoneType> 并且似乎可以工作。当 mydict["primed key"] 为 <NoneType> 时，这意味着什么？ ojit_代码

Answer 1

前一个速度较慢，因为 .keys() 必须首先在内存中创建所有键的列表，然后 in 运算符对其执行搜索。所以，它是一个O(N)从文本文件中搜索每一行，因此速度很慢。

另一方面，一个简单的key in dict搜索需要 O(1) 时间。

dict.fromkeys(allnames)

dict.fromkeys 分配的默认值为 None，因此您不能对其使用 append。

>>> d = dict.fromkeys('abc')
>>> d
{'a': None, 'c': None, 'b': None}

<小时/>

更好的解决方案是在此处使用 collections.defaultdict ，如果这不是一个选项，则使用普通的 dict 以及简单的 if-else 检查或dict.setdefault.

<小时/>

在 Python3 中 .keys() 返回一个 View 对象，因此时间复杂度可能有所不同。但是，它仍然比正常的 key in dict 搜索稍微慢一些。