考虑一下一些整数列表：
#--------------------------------------
0 [0,1,3]
1 [1,0,3,4,5,10,...]
2 [2,8]
3 [3,1,0,...]
...
n []
#--------------------------------------
问题是合并具有至少一个公共元素的列表。因此，仅给定部分的结果如下：
#--------------------------------------
0 [0,1,3,4,5,10,...]
2 [2,8]
#--------------------------------------
在大数据上执行此操作的最有效方法是什么（元素只是数字）？ 是否tree需要考虑结构？我现在通过将列表转换sets为交叉点并对其进行迭代来完成这项工作，但这很慢！此外，我有一种非常基本的感觉！此外，该实现缺少某些内容（未知），因为某些列表有时仍未合并！话虽如此，如果您提议自我实现，请大方并提供一个简单的示例代码[显然Python是我的最爱:)]或伪代码。
更新1： 这是我使用的代码：
#--------------------------------------
lsts = [[0,1,3],
[1,0,3,4,5,10,11],
[2,8],
[3,1,0,16]];
#--------------------------------------
该函数是（越野车!!）：
#--------------------------------------
def merge(lsts):
sts = [set(l) for l in lsts]
i = 0
while i < len(sts):
j = i+1
while j < len(sts):
if len(sts[i].intersection(sts[j])) > 0:
sts[i] = sts[i].union(sts[j])
sts.pop(j)
else: j += 1 #---corrected
i += 1
lst = [list(s) for s in sts]
return lst
#--------------------------------------
结果是：
#--------------------------------------
>>> merge(lsts)
>>> [0, 1, 3, 4, 5, 10, 11, 16], [8, 2]]
#--------------------------------------
更新2： 以我的经验，下面的Niklas Baumstark给出的代码对于简单的情况显示更快一些。尚未测试“ Hooked”给出的方法，因为它是完全不同的方法（看起来很有趣）。所有这些的测试过程可能很难或无法保证结果。我将使用的真实数据集非常大而复杂，因此仅通过重复就不可能跟踪任何错误。也就是说，我需要100％满足该方法的可靠性，然后才能将其推入模块中的大型代码中。就目前而言，Niklas的方法速度更快，简单设置的答案当然是正确的。
但是，如何确定它对于真正的大数据集是否有效？ 由于我将无法直观地跟踪错误！
更新3： 请注意，此方法的可靠性比速度重要得多。希望我最终能够将Python代码转换为Fortran，以获得最佳性能。
更新4：
这篇文章中有许多有趣的观点，并慷慨地给出了答案和建设性的意见。我建议您仔细阅读所有内容。请接受我对问题的发展，令人惊奇的答案以及建设性的评论和讨论的赞赏。
相关分类