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

Question

我有一些数据是这样的：

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

其中每行是一个组。在

我的目标是为每个ID创建一个字典，后面是一组其他ID，它们共享>；=1个组。在

例如，此数据将返回{ID1:[ID2，ID3，ID4，ID5]，ID2:[ID1，ID3]。。。}在

我可以想出三种选择，我想知道哪一种（通常）最好：

1. 添加之前，请检查列表中是否已存在某个ID
2. 创建集合而不是列表，并将每个ID添加到集合中
3. 将所有id添加到列表中，然后将所有列表转换为末尾的集合。在

Answer 1

于2019年10月26日更新

作为一般建议，使用选项2。从一开始就使用集合。在

在Python中，集合是散列集，列表是动态数组。对于两者，插入新元素是O(1)。但是检查集合中是否已经存在元素对于列表是O(n)，对于集合是O(1)。在

所以方案1马上就出来了。每次插入时检查该列表会使整个算法O(n^2)。在

选项2和3的复杂性相同，O(n)。选项3的问题是，您使用两个数据结构，因此在它们之间移动对象的开销很大。所以在微观基准测试中，选择2将获胜。在

因为选项2和选项3的复杂性相同，所以确定哪个更快的唯一方法就是对程序进行基准测试。缓存位置、内存使用量和迭代次数等因素可能会产生明显的差异，并使其中一个优于另一个。但不要过早地优化。代码的可读性和可维护性更为重要，而选项2可能更具可读性。在

Answer 2

选项2在我看来是最符合逻辑的，尤其是对于defaultdict，它应该很容易做到：）

^{1}$

结果：

^{pr2}$

Answer 3

我同意前面的分析，即方案B是最好的，但在这些情况下，微观基准通常是有启发性的：

^{1}$

结果令我吃惊：

^{pr2}$

我估计至少有2倍的速度差。在