高效计算NumPy数组的成对相等

Question

高效计算NumPy数组的成对相等

3

假设有两个NumPy数组：

import numpy as np
import numpy.random as rand

n = 1000
x = rand.binomial(n=1, p=.5, size=(n, 10))
y = rand.binomial(n=1, p=.5, size=(n, 10))

在以下计算中，是否有更有效的方法来计算 X：

X = np.zeros((n, n))
for i in range(n):
    for j in range(n):
        X[i, j] = 1 * np.all(x[i] == y[j])

- p-value

1

是的。请查看广播，然后尝试(x[:, None, :] == y).all(axis=-1)。但是，这种方法在时间上效率高，但空间效率不高（尽管在这种特定情况下，我们只需要大约10MB的空间）。您主要担心空间效率还是时间效率？实际上，n会有多大？ - Mark Dickinson

1

请注意：X = np.zeros((n, n)) 创建的默认数据类型是浮点型。您真的想让 X 成为一个浮点值数组吗？如果您只关心相等性，您可以将其设置为小整数数组（X = np.zeros((n, n), dtype=np.int8)）或布尔值数组（X = np.zeros((n, n), dtype=np.bool_)）。 - Warren Weckesser

@MarkDickinson 我认为在实践中 n 最多会是 10^6。 - p-value

嗯，那么如果你没有1TB或更多的内存，那么将X加载到内存中可能会有麻烦。创建了X后，你会怎么处理它？ - Mark Dickinson

这是一个很好的观点...我希望 X 是一个稀疏矩阵。之后，我需要使用 X 执行多个矩阵向量乘积。 - p-value

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Divakar · Accepted Answer

方法一：输入仅包含0和1的数组

对于仅包含0和1的输入数组，我们可以将它们的每一行缩减为标量，因此将输入数组转换为1D，并利用广播，如下所示 -

n = x.shape[1]        
s = 2**np.arange(n)
x1D = x.dot(s)
y1D = y.dot(s)
Xout = (x1D[:,None] == y1D).astype(float)

方案 #2：通用情况

对于通用情况，我们可以使用 views -

# https://dev59.com/tqPia4cB1Zd3GeqP3cEw#45313353/ @Divakar
def view1D(a, b): # a, b are arrays
    a = np.ascontiguousarray(a)
    b = np.ascontiguousarray(b)
    void_dt = np.dtype((np.void, a.dtype.itemsize * a.shape[1]))
    return a.view(void_dt).ravel(),  b.view(void_dt).ravel()

x1D, y1D = view1D(x, y)
Xout = (x1D[:,None] == y1D).astype(float)

运行时测试

# Setup
In [287]: np.random.seed(0)
     ...: n = 1000
     ...: x = rand.binomial(n=1, p=.5, size=(n, 10))
     ...: y = rand.binomial(n=1, p=.5, size=(n, 10))

# Original approach
In [288]: %%timeit
     ...: X = np.zeros((n, n))
     ...: for i in range(n):
     ...:     for j in range(n):
     ...:         X[i, j] = 1 * np.all(x[i] == y[j])
1 loop, best of 3: 4.69 s per loop

# Approach #1
In [290]: %%timeit
     ...: n = x.shape[1]        
     ...: s = 2**np.arange(n)
     ...: x1D = x.dot(s)
     ...: y1D = y.dot(s)
     ...: Xout = (x1D[:,None] == y1D).astype(float)
1000 loops, best of 3: 1.42 ms per loop

# Approach #2
In [291]: %%timeit
     ...: x1D, y1D = view1D(x, y)
     ...: Xout = (x1D[:,None] == y1D).astype(float)
100 loops, best of 3: 18.5 ms per loop