400万套交叉口如何提速？

Question

我是一个没有经验的程序员，正在用Python完成许多生物信息学练习。在

一个问题是对名称组之间的集合交集中的元素进行计数，并将这些元素存储在字典中。共有两个2000个名称组的列表；名称组中的名称是拉丁物种名称。例如：

list__of_name_groups_1 = [
    ['Canis Lupus', 'Canis Latrans'],
    ['Euarctos Americanus', 'Lynx Rufus'],
    ...
]
list__of_name_groups_2 = [
    ['Nasua Narica', 'Odocoileus Hemionus'],
    ['Felis Concolor', 'Peromyscus Eremicus'],
    ['Canis Latrans', 'Cervus Canadensis']
    ...
]

我需要一个字典，它包含所有名字组之间的交集大小

^{pr2}$

（'Canis Latrans'出现在第一个列表的元素0中，元素{}出现在第二个列表中。）

我有一个算法的实现，但它运行得太慢了。在

overlap = {}
    for i in list_of_lists_of_names_1:            
        for j in list_of_lists_of_names_2:
            overlap[(i,j)] = len(set(i) & set(j))

有没有一种更快的方法来计算集合交叉点中元素的数量？在

（主持人您好。。。尼克，这篇修改后的帖子实际上提出了一个与我正在研究的问题稍有不同的问题。虽然你的回答很好地回答了这个问题，但恐怕你所建议的方法对我所要做的实际上是没有用的。我非常感谢您为您的回答和编辑这篇文章付出的时间和精力，但我要求将帖子还原为原文。）

Answer 1

根据数据的具体情况，另一种选择是，对于每个可能的数据项，记录它所包含的列表。在

使用这样的数据结构，对于每个数据项，您可以快速确定哪些对列表包含它，并增加overlap的相应条目。在

Answer 2

事实上，你可以用一个long来表示每个列表整数。For例如，用第一个元素设置，第二个元素，但是没有第三个元素可以表示为（0<；<；3）+（1＜2）＋（1＜1）＝6

然后，您可以通过计算整数运算来计算集合交集。在

Answer 3

首先，Pythonset很擅长寻找交集（它们使用散列），但是您的代码一次又一次地构造相同的set。E、 如果两个list各包含2000个元素[你的意思是外部的还是内部的list有那么长吗？]，只有4000个不同的set要计算，但是您的代码要计算2000×2000×2=800万sets

所以一次计算这4000组：

list_of_name_tuples_1 = [("a", "aa"), ("b", "bbb"), ("c", "cc", "ccc")]
list_of_name_tuples_2 = [("a", "AA"), ("b", "BBB"), ("c", "cc", "CCC")]
name_sets_1 = [set(i) for i in list_of_name_tuples_1]
name_sets_2 = [set(i) for i in list_of_name_tuples_2]

overlap = {}
for l1, s1 in zip(list_of_name_tuples_1, name_sets_1):
    for l2, s2 in zip(list_of_name_tuples_2, name_sets_2):
        overlap[(l1, l2)] = len(s1 & s2)

Pythonlist是不可损坏的，因此它们不能用于dict键，因此我将名称列表列表更改为名称元组列表。在

（这段代码假设您使用的是python3，其中zip()返回一个迭代器。如果您使用的是python2，那么调用itertools.izip()在成对的元素上获得一个迭代器。）

其次，考虑将overlap重组为dict的dict，而不是由元组索引的dict。在

^{pr2}$

这可以节省后续代码中的大量工作，这些代码将通过overlap[l1][l2]而不是overlap[(l1, l2)]（没有元组构造或哈希生成），嵌套循环可以在外循环中获取{}，然后在内循环中访问{}。在