时间戳

首页 > 解决方案 > 优化 Python Dictionary 中的交集过程

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

问题描述

嗨，我编写了一个代码，用于为每个键查找 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)

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

标签： pythonalgorithm

解决方案

您可以通过预先将所有列表转换为集合来节省大量时间，并且不进行冗余检查（从某种意义上说，对于列表，[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)遗憾的是，这仍然是一个复杂的解决方案。我不知道有什么方法可以进一步降低复杂性。

推荐阅读