如何在一组二进制字符串中高性能地求和无序对的所有乘积

Question

给定一组二进制字符串S，其中每个二进制字符串的长度L，我想找到这些字符串中每个唯一无序对的无序元素对的所有乘积的总和。然后，我想将它们放置在矩阵中，以便位置i,j是所有二进制字符串上i,j的无序索引对的乘积之和。

例如：

让S = {101, 110, 111}

第一个二进制字符串s∈S = 101有无序对{10, 11, 01}，其索引{12, 13, 23}。每个无序对的乘积{0, 1, 0}。

第二个二进制字符串s∈S = 110有无序对{11, 10, 10}，其索引{12, 13, 23}。每个无序对的乘积{1, 0, 0}。

第三个二进制字符串s∈S = 111有无序对{11, 11, 11}，其索引{12, 13, 23}。每个无序对的乘积{1, 1, 1}。

总结产品，我们有{0, 1, 0} + {1, 0, 0} + {1, 1, 1} = {2, 2, 1}。

现在我想根据无序对的指示将它们放置在数组中{12, 13, 23}，其顺序在上面保持不变。因此：

0, 2, 2
2, 0, 1
2, 1, 0

我编写了一些 Python 代码，可以在嵌套的 for 循环中实现这一点，对于少量的短二进制字符串，它运行良好。但是，我需要为长度为10,000150字符串计算这个。

import numpy as np
n_strings = 3
len_strings = 3
ordered_sum_matrix = np.zeros((len_strings,len_strings))
for s in range(0, int(n_strings)):
binary_string = np.random.binomial(1, 0.5, len_strings)
for i in range(0, len(binary_string)):
for j in range(0, len(binary_string)):
if i == j:
continue
ordered_sum_matrix[i,j] = ordered_sum_matrix[i,j] + (binary_string[i] * binary_string[j])

是否有一些线性代数、二进制字符串或 Python 魔法的技巧可以帮助加快速度？

Answer 1

感谢一位提供以下解决方案的 numpy-maestro 朋友：

import numpy as np
def sum_of_prods_of_pairs(M):
# note: this function performs slightly better if given booleans
# e.g. M = np.random.choice([True, False], (len_strings, n_strings))
n_strings, len_strings = M.shape
MT = M.T
M_sum = np.zeros((len_strings, len_strings))
for i in range(len_strings):
M_sum[i, i+1:len_strings] = np.sum(np.multiply(MT[i], MT[i+1:len_strings]), axis=1)
M_sum += M_sum.T
return M_sum
# n_strings = 150
# len_strings = 10000
# np.random.seed(91)
# C = np.random.choice([True, False], (n_strings, len_strings))
# C = np.random.binomial(1, 0.1, (n_strings, len_strings))
C = np.array([[1,0,1], [1,1,0], [1,1,1]])
ordered_sum_matrix = sum_of_prods_of_pairs(C)
print(ordered_sum_matrix)

哪些打印

[[0. 2. 2.]
[2. 0. 1.]
[2. 1. 0.]]