最好将项目添加到集合中,还是将最终列表转换为集合？

Question

我有一些看起来像这样的数据:

ID1 ID2 ID3  
ID1 ID4 ID5  
ID3 ID5 ID7 ID6  
...  
...  

每行是一个组.

我的目标是为每个ID创建一个字典,然后是一组与其共享> = 1组的其他ID.

例如,此数据将返回{ID1:[ID2,ID3,ID4,ID5],ID2:[ID1,ID3] ...}

我可以想到3个选项,我想知道哪个(通常)最好:

1. 在添加ID之前检查ID是否已在列表中
2. 创建集而不是列表,并将每个ID添加到集合中
3. 将所有ID添加到列表中,然后将所有列表转换为最后的集.

Answer 1

选项2对我来说听起来最合乎逻辑,特别是对于defaultdict它应该相当容易:)

import pprint
import collections

data = '''ID1 ID2 ID3
ID1 ID4 ID5
ID3 ID5 ID7 ID6'''

groups = collections.defaultdict(set)

for row in data.split('\n'):
    cols = row.split()
    for groupcol in cols:
        for col in cols:
            if col is not groupcol:
                groups[groupcol].add(col)

pprint.pprint(dict(groups))

结果:

{'ID1': set(['ID2', 'ID3', 'ID4', 'ID5']),
 'ID2': set(['ID1', 'ID3']),
 'ID3': set(['ID1', 'ID2', 'ID5', 'ID6', 'ID7']),
 'ID4': set(['ID1', 'ID5']),
 'ID5': set(['ID1', 'ID3', 'ID4', 'ID6', 'ID7']),
 'ID6': set(['ID3', 'ID5', 'ID7']),
 'ID7': set(['ID3', 'ID5', 'ID6'])}

Answer 2

更新于2019-10-26

作为一般建议，选择选项2。只需从一开始就使用集。

在Python中，集合是哈希集，而列表是动态数组。对于两者，插入一个新元素都是O(1)。但是检查列表中是否存在元素是O(n)针对列表还是O(1)针对集合。

因此，选项1立即退出。每次插入时都要检查列表，以构成整体算法O(n^2)。

选项2和3具有相同的复杂度O(n)。选项3的问题在于，您正在使用两个数据结构，因此在两个对象之间移动对象会产生开销。因此，在微基准测试中，选项2将获胜。

因为选项2和3具有相同的复杂度，所以确定哪种更快的唯一方法是对程序进行基准测试。诸如缓存局部性，内存使用情况以及迭代次数之类的事情可能会产生明显的差异，并在另一个方面占据优势。但是不要过早优化。可读性和可维护性对代码来说更重要，而选项2可能更具可读性。