Python: 加速多个列表中的匹配

Question

我有四个这样的列表：

L = [ (1,2), (3,5), (6,10), (7,8) ]
M = [ (1,3), (8,9), (12,13) ]
N = [ (6,10), (3,4), (5,6), (10,11), (12,13) ]
T = [ (6,10) , (1,4) ]

我想检查 L、M 和 N 中 T 的每个元组的 presence/absence：

[[True, False, True], [False, False, False]]

下面的方法可行，但当 T、L、M 和 N 的大小增长时，它的效率极低。

[[ y in x for x in [L, M, N] ] for y in T ]

对于大型列表，加速此操作的最有效方法是什么？

Answer 1

搜索 list 时间与列表长度成正比。所以对于长列表来说它很高。有针对搜索优化的特殊数据结构。 python 中最简单的是 set。它计算每个元素的哈希值（因此元素必须是可哈希的，并且整数元组是可以的）。然后你做同样的检查。所以你只需要添加

L = set(L)
M = set(M)
N = set(N)

作为副作用，您将失去列表中元素的顺序。如果有非唯一值，它们将合并为一个。

关于加速的更新：

如果搜索值位于最开始，list 中的搜索时间可能较长。但如果不是这种情况，set 应该快得多，因为搜索时间与 log(len(data)) 成正比。 list 的最坏情况是 list 中没有搜索到的项目，因此它需要检查每个项目。在这种情况下，在 1M list 中搜索比在 set 中搜索慢 200K（刚刚在 python3 中检查）

Answer 2

您也可以考虑使用 Numpy 数组来代替普通的 python 列表和元组。看here 由于您必须检查列表中的每个元素，总速度将始终成线性比例，因此您必须使用像 numpy 这样的更快的实现，或者使用像 Rust、C、C++ 这样更快的语言扩展您的代码。

使用np.asarray(listname)函数进行转换

Answer 3

改用字典并比较这些值。

LMNT = {'L':[(1,2),(3,5),(6,10),(7,8)],
'M':[(1,3),(8,9),(12,13)],
'N':[ (6,10), (3,4), (5,6), (10,11), (12,13) ],
'T':[ (6,10) , (1,4) ]}

那你就可以对照字典了。 LMNT['M'][0][1] 值为 2

或

LMNT['N'][4] 值为 (12,13)

Answer 4

如果您可以处理不同的输出格式，您也可以设置交集。

>>> L = set([ (1,2), (3,5), (6,10), (7,8) ])
>>> M = set([ (1,3), (8,9), (12,13) ])
>>> N = set([ (6,10), (3,4), (5,6), (10,11), (12,13) ])
>>> T = set([ (6,10) , (1,4) ])
>>> [T & x for x in (L,M,N)]
[{(6, 10)}, set(), {(6, 10)}]

这将为您提供一组元组的列表，这些元组分别出现在两组中。这应该比使用嵌套循环更快。

Python: 加速多个列表中的匹配

Python: Speed up matching in multiple lists

python

performance

tuples

list

matching