python - 优化 Python Dictionary 中的交集过程

Question

您好，我已经编写了一个代码，用于为每个键查找 5 个或更多相同的元素。

dictionary = {'Mary': [7, 0, 19, 19, 9, 18, 8, 11, 6, 1], 'John': [0, 6, 7, 9, 18, 2, 4, 5, 13, 17], 'Paul': [17, 12, 18, 16, 9, 5, 6, 7, 0, 3], 'Joe': [4, 15, 2, 8, 3, 0, 6, 7, 9, 18], 'Peter': [5, 3, 10, 2, 4, 16, 7, 6, 15, 13], 'Maggie': [13, 6, 5, 4, 8, 9, 7, 18, 11, 10], 'Ken': [2, 18, 16, 6, 0, 17, 4, 15, 11, 7], 'Roger': [3, 1, 16, 4, 13, 14, 19, 11, 8, 0]}
clusterDict = {}
for key, value in dictionary.items():
    for searchKey, searchValue in dictionary.items():
        if key != searchKey:
            intersectionList = list(set(value).intersection(searchValue))
            intersectionList.sort()
            if len(intersectionList) >= 5:
                if str(intersectionList) not in clusterDict:
                    clusterDict[str(intersectionList)] = [key,searchKey]
                else:    
                    clusterDict[str(intersectionList)].append(key)
                    clusterDict[str(intersectionList)].append(searchKey)

for key, value in clusterDict.items():
    clusterDict[key] = list(set(value))

print(clusterDict)

如果我在字典中添加更多的键值对。处理速度会减慢很多。我想知道是否有任何方法可以更快或优化的方式找到交集/共同项目。提前谢谢你

Answer 1

您可以通过预先将所有列表转换为集合来节省大量时间，并且不进行冗余检查(从某种意义上说，对于列表 [A, B, C] 您当前的代码将有效地检查 A intersect B 和 B intersect A)。
您可以利用 itertools.combinations 生成所有可能的组合。

from itertools import combinations
dictionary = {'Mary': [7, 0, 19, 19, 9, 18, 8, 11, 6, 1], 'John': [0, 6, 7, 9, 18, 2, 4, 5, 13, 17], 'Paul': [17, 12, 18, 16, 9, 5, 6, 7, 0, 3], 'Joe': [4, 15, 2, 8, 3, 0, 6, 7, 9, 18], 'Peter': [5, 3, 10, 2, 4, 16, 7, 6, 15, 13], 'Maggie': [13, 6, 5, 4, 8, 9, 7, 18, 11, 10], 'Ken': [2, 18, 16, 6, 0, 17, 4, 15, 11, 7], 'Roger': [3, 1, 16, 4, 13, 14, 19, 11, 8, 0]}
dict_of_sets = {k:set(v) for k,v in dictionary.items()}
clusterDict = {}

for (key1, value1), (key2, value2) in combinations(dict_of_sets.items(),2):
    intersect = value1.intersection(value2)
    if len(intersect) >= 5:
        #change keyword tuple to str if you wish to. 
        clusterDict.setdefault(tuple(sorted(intersect)),[]).extend([key1, key2])

请注意，您还可以将元组用于字典键，在我看来，这至少比将列表类型转换为字符串更清晰。但是，您可以随意更改该部分。

这应该会更快，但不幸的是，随着这些事情的发展，这仍然是一个 O(N^2) 复杂度的解决方案。我不知道有什么方法可以进一步降低复杂性。