降低复杂性：查找列表中的共同元素

Question

设置简单：我有一个列表（大约 40,000 个条目），其中包含字符串列表（每个字符串有 2-15 个元素）。我想比较所有子列表以检查它们是否具有共同元素（它们最多共享一个）。最后，我想创建一个字典（如果你愿意的话可以画图），其中每个子列表的索引用作键，它的值是与它共享公共元素的其他子列表的索引。

例如

lst = [['dam', 'aam','adm', 'ada', 'adam'], ['va','ea','ev','eva'], ['va','aa','av','ava']]

应该给出以下内容：

dic = {0: [], 1: [2], 2: [1]}

我的问题是我找到了解决方案，但计算量很大。首先，我写了一个函数来计算两个列表的交集：

def intersection(lst1, lst2): 

    temp = set(lst2) 
    lst3 = [value for value in lst1 if value in temp] 
    return lst3

然后我将遍历所有列表以检查交叉点：

dic = {}
iter_range = range(len(lst))

#loop over all lists where k != i
for i in iter_range:

    #create range that doesn't contain i
    new_range = list(iter_range)
    new_range.remove(i)

    lst = []

    for k in new_range:
        #check if the lists at position i and k intersect
        if len(intersection(mod_names[i], mod_names[k])) > 0:
            lst.append(k)

    # fill dictionary 
    dic[i] = lst

我知道 for 循环很慢，而且我经常不必要地遍历列表（在上面的例子中，我比较 1 和 2，然后比较 2 和 1），但我不知道如何更改它以使程序运行更快。

Answer 1

您可以创建一个字典 word_occurs_in 来存储哪些单词出现在哪些列表中的数据，对于您的示例来说，这将是：

{'dam': [0], 'aam': [0], 'adm': [0], 'ada': [0], 'adam': [0], 'va': [1, 2], 'ea': [1], 'ev': [1], 'eva': [1], 'aa': [2], 'av': [2], 'ava': [2]}

然后你可以创建一个新的字典，我们称之为result，你应该在其中存储最终结果，例如{0: [], 1: [2], 2: [1]} 你的情况。

现在，要从 word_occurs_in 得到 result，您应该遍历 word_occurs_in 的值并查看列表是否有不止一个元素。如果是，那么您只需要添加除 result 中当前观察到的键的值之外的所有其他值。例如，当检查值 [1, 2]（对于键 'va'）时，您将添加 1 到 result 字典中对应于 2 的值，并且将 2 添加到键 1 对应的值。希望对您有所帮助。

据我了解，您的代码最大的复杂性来自于对 40K 条目的列表进行两次迭代，因此此方法仅对列表进行一次迭代，但使用了更多 space.

可能是我解释的不够充分，代码如下：

from collections import defaultdict

lst = [['dam', 'aam', 'adm', 'ada', 'adam'], ['va', 'ea', 'ev', 'eva'], ['va', 'aa', 'av', 'ava']]

word_occurs_in = defaultdict(list)

for idx, l in enumerate(lst):
    for i in l:
        word_occurs_in[i].append(idx)

print(word_occurs_in)

result = defaultdict(list)
for v in word_occurs_in.values():
    if len(v) > 1:
        for j in v:
            result[j].extend([k for k in v if k != j])

print(result)

降低复杂性：查找列表中的共同元素

Complexity reduction: Find common elements in lists

python

arrays

compare

list

hashable