python - 在 python 中异或大量二进制数组的最快方法是什么？

Question

我的任务是计算两组一维二进制数组之间的汉明距离——一组 3000 个数组和一组 10000 个数组，每个数组的长度为 100 个项目(位)。这就是 100 位长对象的 3000x10000 HD 计算。所有这些必须在最多十几分钟内完成

这是我想出的最好的东西

#X - 3000 by 100 bool np.array 
#Y - 10000 by 100 bool np.array
hd = []
i=1
for x in X:
    print("object nr " + str(i) + "/" + str(len(X)))
    arr = np.array([x] * len(Y)) 
    C = Y^arr # just xor this array by all the arrays in the other group simultainously
    hd.append([sum(c) for c in C]) #add up all the bits to get the hamming distance
    i+=1

return np.array(hd)

它仍然需要 1-1.5 小时才能完成。我该如何着手让它更快？

Answer 1

您应该能够通过使用 numpy 来显着提高求和速度，而不是使用列表理解和内置的 sum 函数(需要没有 numpy 向量化操作的优势)。

只需替换:

hd.append([sum(c) for c in C])

与:

# Explicitly use uint16 to reduce memory cost; if array sizes might increase
# you can use uint32 to leave some wiggle room
hd.append(C.sum(1, dtype=np.uint16))

对于二维数组，它将返回一个新的一维数组，其中每个值都是相应行的总和(由于指定它应该在 axis 1 上运行).例如:

>>> arr = np.array([[True,False,True], [False,False,True], [True, True,True]], dtype=np.bool)
>>> arr.sum(1, np.uint16)
array([ 2, 1, 3], dtype=uint16)

因为它在一个没有类型转换的操作中执行了 C 层的所有工作(而不是你原来的方法需要一个 Python 级别的循环来对每一行进行操作，然后是一个隐式循环，在 C 层，仍然必须将每个 numpy 值从 np.bool 隐式转换为 Python 级别的 int 只是为了对它们求和)，这应该可以运行对于您所描述的阵列规模更快。

旁注:虽然不是性能问题的根源，但没有理由手动维护索引值； enumerate can do that更快速，更容易。只需替换:

i=1
for x in X:
    ... rest of loop ...
    i+=1

与:

for i, x in enumerate(X, 1):
    ... rest of loop ...

你会得到相同的行为，但总体上稍微更快、更简洁和更清晰。