Вычислительные различия: ускорение операции со всеми комбинациями строк в матрице

Question

Я хочу вычислить количество так называемых отличий от заданной двоичной матрицы G. Предполагая, что строки G соответствуют некоторым индивидуумам, а его столбцы - некоторым тестовым случаям, различия, сделанные тестом, определяются как количество пар.индивидуумов это дифференцирует.

Я придумал очень простую реализацию:

distinctions = np.zeros(G.shape[1])
for p in itertools.combinations(np.arange(G.shape[0]), 2):
    distinctions += G[p[0], :] != G[p[1], :]

Но она медленная для моих нужд.Буду очень признателен, если вы поможете мне ускорить этот код.

Answer 1

Вам не нужно знать фактическое расположение единиц и нулей, вам просто нужно знать, сколько их.Например, в массиве

array([[1, 1, 0, 1],
       [1, 1, 1, 0],
       [1, 0, 0, 1]])

мы видим, что тест 0 не различает никого (0), тест 1 может отличить № 0 и № 1 от № 2, для (2) * (1) общего различия, тест2 может отличить № 1 от № 0 и № 2, для (1) * (2) общего различия, а тест 3 может отличить № 0 и № 2 от № 1, для (2) * (1) общего различия, что даетus

[0, 2, 2, 2]

Итак, нам просто нужно посчитать число 1 в столбце и умножить его на количество 0 в этом столбце, потому что каждый 1 приводит к различиям (num_zeroes).IOW:

def slow(G):
    distinctions = np.zeros(G.shape[1])
    for p in itertools.combinations(np.arange(G.shape[0]), 2):
        distinctions += G[p[0], :] != G[p[1], :]
    return distinctions

def fast(G):
    ones = np.count_nonzero(G, axis=0)
    return ones * (G.shape[0] - ones)

, что дает мне

In [125]: G
Out[125]: 
array([[0, 1, 0, 0, 1, 1, 0],
       [1, 0, 0, 0, 0, 0, 1],
       [1, 0, 1, 1, 1, 0, 0],
       [1, 1, 0, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 1]])

In [126]: slow(G)
Out[126]: array([6., 6., 4., 6., 6., 4., 6.])

In [127]: fast(G)
Out[127]: array([6, 6, 4, 6, 6, 4, 6])

и

In [130]: G = np.random.randint(0, 2, (1000, 1000))

In [131]: %timeit fast(G)
7.87 ms ± 344 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)