比较集合交集并返回包含最大交集集合的字典键的最快方法

Question

我有一个创建最大团覆盖的算法，但是它太慢了。在每个步骤中，我需要比较一个主集合和从该主集合的字典键获取的集合之间的交集。

现在，我有一个包含集合的字典：

edges = { 1:{2,3},
        2:{1,3},
        3:{1,2}}

主要的集合：{1,2}（每个步骤长度都增加）

intersection_C = {1,2}

下一次迭代的过程是：选择词典键（从主集合中的元素）使您获得最大交集。

换句话说：比较集合edges[1]与交集_C相交的交集，以及集合edges[2]与交集_C相交的交集。然后选择提供最大（最长长度）交集的键。我需要保留最终结果的交集和提供最大交集的键。

键添加到列表C中，最终交集将成为新的主集合。

如何尽快地完成这项任务？

解决子问题的当前算法为：

best = 0  #longest found length param
for node in intersection_C: #looping through elements of main set
    new = intersection_C.intersection(edges[node])   #new intersection'
    if len(new) >= best:          #comparing  
        candidate = node          #saving key
        best = len(new)          #updating best length
        best_intersection = new     #Saving best found intersection
    del new

- Gunnar

Answer 1

我无法想象有比这更快的算法，但我们可以缩短您当前算法的符号表示：

candidate = max(intersection_C, key = lambda node: len(intersection_C & edges[node]))
best_intersection = intersection_C & edges[candidate]

- Armali

---

你可能是对的，你认为使用像C++这样的另一种语言能更快地找到交集吗？或者已经写得很快了吗？ - Gunnar

可能C++的实现会更快，但这当然取决于数据量是否值得移植。但由于这只是一个子问题，有必要对超问题进行更广泛的研究，使用更具代表性的数据进行基准测试和优化测试。 - Armali