我有一些数据看起来像这样:
ID1 ID2 ID3
ID1 ID4 ID5
ID3 ID5 ID7 ID6
...
...
其中每一行都是一个组。
我的目标是为每个 ID 建立一个字典,然后是与其共享 >= 1 个组的一组其他 ID。
例如,此数据将返回 {ID1: [ID2, ID3, ID4, ID5], ID2:[ID1, ID3] ... }
我可以想到 3 个选项,我想知道哪个(通常)最好:
- 添加之前检查 ID 是否已在列表中
- 创建集合而不是列表,并将每个 ID 添加到集合中
- 将所有 ID 添加到列表中,然后在最后将所有列表转换为集。
TL;DR:选择选项 2。从一开始就使用集合。
在Python中,集合是哈希集,列表是动态数组。插入的是O(1)
对于两者,但检查元素是否存在是O(n)
对于列表和O(1)
对于集合。
所以选项1立刻就被淘汰了。如果您正在插入n
项目并且每次都需要检查列表,那么整体复杂度就变成了O(n^2)
.
选项 2 和 3 都是最优的O(n)
全面的。选项 2 在微基准测试中可能会更快,因为您不需要在集合之间移动对象。在实践中,请选择在您的具体情况下更易于阅读和维护的选项。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)