计算差异：加速对矩阵中所有行组合的操作

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

你不需要知道1和0的实际位置，你只需要知道它们有多少。例如，在数组中

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）完全区别，这给了我们

[0, 2, 2, 2]

实际上，我们只需要计算一列中1的数量，然后乘以该列中0的数量，因为每个1都会产生（num_零）区别。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)