python - 如何加速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']
    ...
]

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

>>> intersections
{ (0, 0): 0, (0, 1): 0, (0, 2): 1, (1, 0): 0, (1, 1): 0, (2, 1): 0,
  (2, 0): 1, (2, 1): 0, (2, 2): 0 }

('Canis Latrans' 出现在第一个列表中的元素 0 中，第二个列表中的元素 2 中。)

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

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

首先， Python set s 擅长寻找交集(他们使用散列)，但您的代码构造相同的 set一遍又一遍。例如。如果两个list s 每个包含 2000 个元素 [你是指外部还是内部 list有那么长？]，只有 4000 种不同的 set s 来计算，但您的代码计算 2000 x 2000 x 2 = 800 万 set

所以计算这 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)

python list s 是不可散列的，因此它们不能用于 dict键，所以我将名称列表更改为名称元组列表。

(此代码假定您使用的是 Python 3，其中 zip() 返回一个迭代器。如果您使用的是 Python 2，则调用 itertools.izip() 以获得配对元素的迭代器。)

其次考虑重组overlap作为dict的 dict s 而不是 dict由元组索引。

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):
    d = overlap.setdefault(l1, {})
    for l2, s2 in zip(list_of_name_tuples_2, name_sets_2):
        d[l2] = len(s1 & s2)

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