Как оперативно суммировать все произведения неупорядоченных пар в наборе двоичных строк - PullRequest
Новая
       17

Как оперативно суммировать все произведения неупорядоченных пар в наборе двоичных строк

1 голос
/ 20 апреля 2019

Учитывая набор двоичных строк 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, которые могут помочь ускорить процесс?

1 Ответ

0 голосов
/ 22 апреля 2019

Спасибо другу-маэстро, который предоставил следующее решение: 

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