在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中的所有键？还有另一种方法来加速不包括遍历树的字典搜索吗？

有趣的是我在使用相同的条件检查时得到的错误(如果在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>什么意思？enter code here

Answer 1

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

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

dict.fromkeys(allnames)

由dict.fromkeysis 分配的默认值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搜索略慢.