Numpy:当某些向量元素等于零时,矩阵向量乘法不会跳过计算吗?
Numpy: does matrix-vector multiplication not skip computation when some vector elements are equal to zero?
我最近一直在做一个项目,我的大部分时间都花在乘以密集矩阵 A
和稀疏向量 v
(请参阅 here)。在我减少计算的尝试中,我注意到 A.dot(v)
的运行时间不受 v
的零条目数的影响。
为了解释为什么我期望在这种情况下运行时间会有所改善,让 result = A.dot.v
使得 result[j] = sum_i(A[i,j]*v[j]) for j = 1...v.shape[0]
。如果 v[j] = 0
那么显然 result[j] = 0
不管值 A[::,j]
。在这种情况下,我因此希望 numpy 只设置 result[j] = 0
但它似乎继续计算 sum_i(A[i,j]*v[j])
无论如何。
我继续写了一个简短的示例脚本来确认下面的这种行为。
import time
import numpy as np
np.__config__.show() #make sure BLAS/LAPACK is being used
np.random.seed(seed = 0)
n_rows, n_cols = 1e5, 1e3
#initialize matrix and vector
A = np.random.rand(n_rows, n_cols)
u = np.random.rand(n_cols)
u = np.require(u, dtype=A.dtype, requirements = ['C'])
#time
start_time = time.time()
A.dot(u)
print "time with %d non-zero entries: %1.5f seconds" % (sum(u==0.0), (time.time() - start_time))
#set all but one entry of u to zero
v = u
set_to_zero = np.random.choice(np.array(range(0, u.shape[0])), size = (u.shape[0]-2), replace=False)
v[set_to_zero] = 0.0
start_time = time.time()
A.dot(v)
print "time with %d non-zero entries: %1.5f seconds" % (sum(v==0.0), (time.time() - start_time))
#what I would really expect it to take
non_zero_index = np.squeeze(v != 0.0)
A_effective = A[::,non_zero_index]
v_effective = v[non_zero_index]
start_time = time.time()
A_effective.dot(v_effective)
print "expected time with %d non-zero entries: %1.5f seconds" % (sum(v==0.0), (time.time() - start_time))
运行 这个,我知道无论我使用密集矩阵 u
还是稀疏矩阵 v
:[=28=,矩阵向量乘法的运行时间都是相同的]
time with 0 non-zero entries: 0.04279 seconds
time with 999 non-zero entries: 0.04050 seconds
expected time with 999 non-zero entries: 0.00466 seconds
我想知道这是否是设计使然?还是我在 运行 矩阵向量乘法中遗漏了一些东西。 就像健全性检查一样:我确保 numpy
链接到 BLAS 库我的机器和两个数组都是 C_CONTIGUOUS
(因为这显然是 numpy 调用 BLAS 所必需的)。
对于简单的数组,Numpy 不会执行此类优化,但如果您需要,您可以使用稀疏矩阵,这可能会在这种情况下改进点积时序。
有关该主题的更多信息,请参阅:http://docs.scipy.org/doc/scipy/reference/sparse.html
试试像这样的简单函数如何?
def dot2(A,v):
ind = np.where(v)[0]
return np.dot(A[:,ind],v[ind])
In [352]: A=np.ones((100,100))
In [360]: timeit v=np.zeros((100,));v[::60]=1;dot2(A,v)
10000 loops, best of 3: 35.4 us per loop
In [362]: timeit v=np.zeros((100,));v[::40]=1;dot2(A,v)
10000 loops, best of 3: 40.1 us per loop
In [364]: timeit v=np.zeros((100,));v[::20]=1;dot2(A,v)
10000 loops, best of 3: 46.5 us per loop
In [365]: timeit v=np.zeros((100,));v[::60]=1;np.dot(A,v)
10000 loops, best of 3: 29.2 us per loop
In [366]: timeit v=np.zeros((100,));v[::20]=1;np.dot(A,v)
10000 loops, best of 3: 28.7 us per loop
完全迭代的 Python 实现将是:
def dotit(A,v, test=False):
n,m = A.shape
res = np.zeros(n)
if test:
for i in range(n):
for j in range(m):
if v[j]:
res[i] += A[i,j]*v[j]
else:
for i in range(n):
for j in range(m):
res[i] += A[i,j]*v[j]
return res
显然这不会像编译的那样快 dot
,但我希望测试的相对优势仍然适用。为了进一步测试,您可以在 cython
.
中实现它
请注意 v[j]
测试发生在迭代的深处。
对于稀疏 v
(100 个元素中的 3 个)测试节省时间:
In [374]: timeit dotit(A,v,True)
100 loops, best of 3: 3.81 ms per loop
In [375]: timeit dotit(A,v,False)
10 loops, best of 3: 21.1 ms per loop
但是如果v
是密集的,它会花费时间:
In [376]: timeit dotit(A,np.arange(100),False)
10 loops, best of 3: 22.7 ms per loop
In [377]: timeit dotit(A,np.arange(100),True)
10 loops, best of 3: 25.6 ms per loop
我最近一直在做一个项目,我的大部分时间都花在乘以密集矩阵 A
和稀疏向量 v
(请参阅 here)。在我减少计算的尝试中,我注意到 A.dot(v)
的运行时间不受 v
的零条目数的影响。
为了解释为什么我期望在这种情况下运行时间会有所改善,让 result = A.dot.v
使得 result[j] = sum_i(A[i,j]*v[j]) for j = 1...v.shape[0]
。如果 v[j] = 0
那么显然 result[j] = 0
不管值 A[::,j]
。在这种情况下,我因此希望 numpy 只设置 result[j] = 0
但它似乎继续计算 sum_i(A[i,j]*v[j])
无论如何。
我继续写了一个简短的示例脚本来确认下面的这种行为。
import time
import numpy as np
np.__config__.show() #make sure BLAS/LAPACK is being used
np.random.seed(seed = 0)
n_rows, n_cols = 1e5, 1e3
#initialize matrix and vector
A = np.random.rand(n_rows, n_cols)
u = np.random.rand(n_cols)
u = np.require(u, dtype=A.dtype, requirements = ['C'])
#time
start_time = time.time()
A.dot(u)
print "time with %d non-zero entries: %1.5f seconds" % (sum(u==0.0), (time.time() - start_time))
#set all but one entry of u to zero
v = u
set_to_zero = np.random.choice(np.array(range(0, u.shape[0])), size = (u.shape[0]-2), replace=False)
v[set_to_zero] = 0.0
start_time = time.time()
A.dot(v)
print "time with %d non-zero entries: %1.5f seconds" % (sum(v==0.0), (time.time() - start_time))
#what I would really expect it to take
non_zero_index = np.squeeze(v != 0.0)
A_effective = A[::,non_zero_index]
v_effective = v[non_zero_index]
start_time = time.time()
A_effective.dot(v_effective)
print "expected time with %d non-zero entries: %1.5f seconds" % (sum(v==0.0), (time.time() - start_time))
运行 这个,我知道无论我使用密集矩阵 u
还是稀疏矩阵 v
:[=28=,矩阵向量乘法的运行时间都是相同的]
time with 0 non-zero entries: 0.04279 seconds
time with 999 non-zero entries: 0.04050 seconds
expected time with 999 non-zero entries: 0.00466 seconds
我想知道这是否是设计使然?还是我在 运行 矩阵向量乘法中遗漏了一些东西。 就像健全性检查一样:我确保 numpy
链接到 BLAS 库我的机器和两个数组都是 C_CONTIGUOUS
(因为这显然是 numpy 调用 BLAS 所必需的)。
对于简单的数组,Numpy 不会执行此类优化,但如果您需要,您可以使用稀疏矩阵,这可能会在这种情况下改进点积时序。 有关该主题的更多信息,请参阅:http://docs.scipy.org/doc/scipy/reference/sparse.html
试试像这样的简单函数如何?
def dot2(A,v):
ind = np.where(v)[0]
return np.dot(A[:,ind],v[ind])
In [352]: A=np.ones((100,100))
In [360]: timeit v=np.zeros((100,));v[::60]=1;dot2(A,v)
10000 loops, best of 3: 35.4 us per loop
In [362]: timeit v=np.zeros((100,));v[::40]=1;dot2(A,v)
10000 loops, best of 3: 40.1 us per loop
In [364]: timeit v=np.zeros((100,));v[::20]=1;dot2(A,v)
10000 loops, best of 3: 46.5 us per loop
In [365]: timeit v=np.zeros((100,));v[::60]=1;np.dot(A,v)
10000 loops, best of 3: 29.2 us per loop
In [366]: timeit v=np.zeros((100,));v[::20]=1;np.dot(A,v)
10000 loops, best of 3: 28.7 us per loop
完全迭代的 Python 实现将是:
def dotit(A,v, test=False):
n,m = A.shape
res = np.zeros(n)
if test:
for i in range(n):
for j in range(m):
if v[j]:
res[i] += A[i,j]*v[j]
else:
for i in range(n):
for j in range(m):
res[i] += A[i,j]*v[j]
return res
显然这不会像编译的那样快 dot
,但我希望测试的相对优势仍然适用。为了进一步测试,您可以在 cython
.
请注意 v[j]
测试发生在迭代的深处。
对于稀疏 v
(100 个元素中的 3 个)测试节省时间:
In [374]: timeit dotit(A,v,True)
100 loops, best of 3: 3.81 ms per loop
In [375]: timeit dotit(A,v,False)
10 loops, best of 3: 21.1 ms per loop
但是如果v
是密集的,它会花费时间:
In [376]: timeit dotit(A,np.arange(100),False)
10 loops, best of 3: 22.7 ms per loop
In [377]: timeit dotit(A,np.arange(100),True)
10 loops, best of 3: 25.6 ms per loop