快速Python外部列表的差异

Question

我想计算等长列表的Python列表中每个元素之间的差，并将其放入Numpy数组中。

当我说两个列表之间的差异时，我指的是两个列表中相应元素之间的差异数量。下面是一个使用列表理解的差异函数示例：

def list_difference(list_a, list_b):
len_lists = len(list_a)
assert len_lists == len(list_b), "Lists must be the same length."
return sum([list_a[i] != list_b[i] for i in range(len_lists)])

然后，我对列表列表中的每一对调用difference函数，并将其放入numpy数组中。您可以称之为列表列表的外部差异，就像外部乘积一样。我做它在天真的循环：

import numpy as np
import time
sequences = [
["A", "A", "A", "B", "C"],
["B", "A", "B", "A", "B"],
["B", "A", "C", "C", "B"],
["B", "A", "C", "C", "C"],
]
start = time.time()
n_seq = len(sequences)
dists = np.zeros((n_seq, n_seq))
for row in range(n_seq):
for col in range(n_seq):
if row >= col:
continue
dists[row, col] = list_difference(sequences[row], sequences[col])
dists += dists.T
print(dists)
print(f"Time: {time.time() - start} seconds")

结果是

[[0. 4. 4. 3.]
[4. 0. 2. 3.]
[4. 2. 0. 1.]
[3. 3. 1. 0.]]
Time: 0.0003669261932373047 seconds

这个例子在我的电脑上已经足够快了(上面三个例子中最好的一个(。然而，在64个长度为1008的列表(序列(上运行它需要293.572190秒，这是一段时间。有更快的方法吗

尝试次数：

1我尝试在列表理解中放入内部for循环：

dists = np.zeros((n_seq, n_seq))
for row in range(n_seq):
dist_row = [list_difference(sequences[row], sequences[col]) for col in range(n_seq) if row >= col]
dists[row, n_seq-row-1:] = dist_row
dists += dists.T

但它实际上让它变慢了，用了0.000523秒(快了0.70倍(。在我较大的数据集上，它需要319.2168769秒(快0.92倍(。

2我想知道在原生Python中执行for循环，然后在最后复制到Numpy是否会有所帮助。

_dists = [ [0]*n_seq for i in range(n_seq)]
for row in range(n_seq):
for col in range(n_seq):
if col <= row:
continue
_dists[row][col] = list_difference(sequences[row], sequences[col])
dists = np.array(_dists)
dists += dists.T

这需要0.0001862秒，大约是原始代码的两倍。在我更大的数据集上，加速没有229.945951秒那么显著(快1.28倍(，但仍然有一些。

3只是想一想，可能有一种方法可以直接在Numpy中完成两个外部for循环。

Answer 1

一种更干净、更简单、更快的方法是使用numpy广播：

sequences = np.array(sequences)
dists = (sequences[:, None] != sequences).sum(axis=2)

输出：

>>> dists
array([[0, 4, 4, 3],
[4, 0, 2, 3],
[4, 2, 0, 1],
[3, 3, 1, 0]])