python-3.x - 如何在一组二进制字符串中高效地求和所有无序对的乘积

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 循环中实现了这一点，并且对于少量的短二进制字符串，它运行良好。但是，我需要为150长度字符串计算这个10,000。

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 魔术的技巧可以帮助加快速度？

标签： python-3.xperformancebinarylinear-algebracombinatorics

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.]]