0

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

例如

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 进行比较），但我不知道如何更改它以使程序运行得更快。

4

1 回答 1

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]}在你的情况下。

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

据我了解，代码的最大复杂性来自对 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)
于 2019-01-06T18:08:03.537 回答