dou*_*oug 10 python performance memory-management numpy
几年前,有人发布了Active State Recipes用于比较目的,三个python/NumPy函数; 每个都接受相同的参数并返回相同的结果,即距离矩阵.
其中两个来自公开来源; 它们都是 - 或者它们在我看来是 - 惯用的numpy代码.创建距离矩阵所需的重复计算由numpy优雅的索引语法驱动.这是其中之一:
from numpy.matlib import repmat, repeat
def calcDistanceMatrixFastEuclidean(points):
numPoints = len(points)
distMat = sqrt(sum((repmat(points, numPoints, 1) -
repeat(points, numPoints, axis=0))**2, axis=1))
return distMat.reshape((numPoints,numPoints))
第三个使用单个循环创建了距离矩阵(显然,由于只有1,000个2D点的距离矩阵,有一百万个条目,因此很多循环).乍一看这个函数看起来像我在学习NumPy时编写的代码,我会编写NumPy代码,首先编写Python代码,然后逐行翻译.
在Active State帖子发布几个月之后,在NumPy邮件列表的一个帖子中发布并讨论了比较三者的性能测试结果.
事实上,循环函数明显优于其他两个函数:
from numpy import mat, zeros, newaxis
def calcDistanceMatrixFastEuclidean2(nDimPoints):
nDimPoints = array(nDimPoints)
n,m = nDimPoints.shape
delta = zeros((n,n),'d')
for d in xrange(m):
data = nDimPoints[:,d]
delta += (data - data[:,newaxis])**2
return sqrt(delta)
线程中的一位参与者(Keir Mierle)提供了为什么这可能是真的:
我怀疑它会更快的原因是它具有更好的局部性,在移动到下一个工作集之前完全完成对相对较小的工作集的计算.一个衬垫必须重复地将潜在的大MxN阵列拉入处理器.
通过这张海报自己的说法,他的评论只是一种怀疑,而且似乎没有进一步讨论过.
关于如何解释这些结果的任何其他想法？
特别是,是否有一个有用的规则 - 关于何时循环以及何时索引 - 可以从此示例中提取作为编写numpy代码的指导？
对于那些不熟悉NumPy,或者没有看过代码的人来说,这种比较不是基于一个边缘情况 - 如果是这样的话,对我来说肯定不会那么有趣.相反,这种比较涉及一种在矩阵计算中执行常见任务的函数(即,给定两个前因创建结果数组); 而且,每个函数又由最常见的numpy内置函数组成.
Jus*_*eel 11
TL; DR上面的第二个代码仅循环遍历点的维数(对于3D点,通过for循环3次),因此循环不是很多.上面第二个代码中的实际加速是它更好地利用Numpy的功能,以避免在找到点之间的差异时创建一些额外的矩阵.这减少了使用的内存和计算工作量.
更长的解释
我认为这个calcDistanceMatrixFastEuclidean2函数可能会欺骗你的循环.它只是循环遍历点的维数.对于1D点,循环仅执行一次,对于2D,两次,对于3D,执行三次.这根本没有多少循环.
让我们分析一下代码,看看为什么一个比另一个快.calcDistanceMatrixFastEuclidean我会打电话,fast1而且calcDistanceMatrixFastEuclidean2会fast2.
fast1基于Matlab的做事方式,正如repmap函数所证明的那样.repmap在这种情况下,该函数创建一个数组,它只是一遍又一遍地重复的原始数据.但是,如果查看函数的代码,效率非常低.它使用许多Numpy函数(3 reshape秒和2 repeat秒)来完成此操作.该repeat函数还用于创建一个包含原始数据的数组,每个数据项重复多次.如果我们的输入数据[1,2,3],然后我们减去[1,2,3,1,2,3,1,2,3]从[1,1,1,2,2,2,3,3,3].Numpy必须在运行Numpy的C代码之间创建许多额外的矩阵,而这些代码本来是可以避免的.
fast2使用更多Numpy的繁重工作而不会在Numpy调用之间创建尽可能多的矩阵.fast2循环遍历点的每个维度,进行减法并保持每个维度之间的平方差异的运行总和.只有在最后才是平方根.到目前为止,这可能听起来不那么有效fast1,但fast2避免repmat使用Numpy的索引来做这些事情.让我们看一下1D的简单情况.fast2生成数据的一维数组,并从数据的2D(N x 1)数组中减去它.这会在每个点和所有其他点之间创建差异矩阵,而不必使用repmat和repeat绕过创建大量额外数组.这是真正的速度差异在我看来的地方.fast1在矩阵之间创建了许多额外的(并且它们在计算上昂贵地创建)以找到点之间的差异,同时fast2更好地利用Numpy的力量来避免这些.
顺便说一句,这里是一个更快一点的版本fast2:
def calcDistanceMatrixFastEuclidean3(nDimPoints):
nDimPoints = array(nDimPoints)
n,m = nDimPoints.shape
data = nDimPoints[:,0]
delta = (data - data[:,newaxis])**2
for d in xrange(1,m):
data = nDimPoints[:,d]
delta += (data - data[:,newaxis])**2
return sqrt(delta)
不同之处在于我们不再将delta创建为零矩阵.