降低复杂性:在列表中查找常见元素

Question

简单设置：我有一个列表(大约40000个条目)，其中包含字符串列表(每个字符串有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

您可以创建一个dictword_occurs_in，它将存储数据，哪个单词出现在哪个列表中，对于您的示例，它将是：

｛'dam'：[0]，'aam'：[2]，'adm'：[0]、'ada':[0]、'adam'：[0]和'va'：[1，2]，"ea"：[1]，"ev"：[1]、"eva"：[1]；"aa"：[2]，"av"：[2]；"ava"：[2] }

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

现在，要从word_occurs_in中获取result，您应该遍历word_occurs_in的值，看看列表中是否有多个元素。如果是，那么您只需要添加除result中当前观察到的键的值之外的所有其他值。例如，当检查值[1, 2](对于键'va')时，您将"将1添加到resultdict中对应于2的值，并将2添加到对应于键1的值。我希望这能有所帮助。

据我所知，代码的最大复杂性来自于对40K条目的列表进行两次迭代，因此这种方法只对列表进行一次迭代，但会占用更多的空间。

也许我没有充分解释自己，所以下面是代码：

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)