我知道Matlab有内置的pdist函数可以计算成对距离。但是,我的矩阵太大了,是60000乘以300,而且Matlab会用完内存。
这个问题是对Matlab欧几里得成对平方距离函数的后续提问。
有没有解决这种计算效率低下的方法?我试过手动编写成对距离计算的代码,通常需要一整天才能运行(有时需要6到7个小时)。
非常感谢任何帮助!
我知道Matlab有内置的pdist函数可以计算成对距离。但是,我的矩阵太大了,是60000乘以300,而且Matlab会用完内存。
这个问题是对Matlab欧几里得成对平方距离函数的后续提问。
有没有解决这种计算效率低下的方法?我试过手动编写成对距离计算的代码,通常需要一整天才能运行(有时需要6到7个小时)。
非常感谢任何帮助!
好吧,我忍不住玩了一下。我创建了一个名为pdistc
的Matlab mex C文件,用于实现单精度和双精度的成对欧几里德距离计算。在我的机器上,使用Matlab R2012b和R2015a,对于大输入量(例如60,000乘以300),它比pdist
(和底层的pdistmex
辅助函数)快20-25%。
m = 6e3;
n = 3e2;
X = rand(m,n);
sz = m*(m-1)/2;
for i = 1:m:sz-m
D = pdistc(X', i, i+m); % mex C function, X is transposed relative to pdist
... % Process chunk of pairwise distances
end
X
的子集,而不是全部传递到 pdist
(或pdistc
)中,以更高效地完成同样的事情。.mexmaci64
二进制文件,但如果你使用其他机器,你需要找出如何为你的机器编译代码。我无法帮助你解决这个问题。你可能无法编译它,或者你需要自己编辑代码来解决兼容性问题。还有可能存在漏洞,导致代码崩溃Matlab。此外,请注意,相对于pdist
,你可能会得到稍微不同的输出,两者之间的差异在机器epsilon范围内(eps
)。 pdist
可能会采取一些花哨的方法来避免大输入和其他数字问题的溢出,但请注意,我的代码不会这样做。pdist
中找到的代码快。
所有文件在这里可以找到。ZIP压缩包包含了所有文件。它是BSD许可证。欢迎进行优化(我尝试使用C代码中的BLAS调用和OpenMP,但没有成功-也许一些指针魔法或GPU / OpenCL可以进一步加速)。我希望它对您或他人有所帮助。
pdistc
更快):function [ mD ] = CalcDistMtx ( mX )
vSsqX = sum(mX .^ 2);
mD = sqrt(bsxfun(@plus, vSsqX.', vSsqX) - (2 * (mX.' * mX)));
end
bsxfun()
。function [ mD ] = CalcDistMtx ( mX )
vSsqX = sum(mX .^ 2, 1);
mD = sqrt(vSsqX.'+ vSsqX - (2 * (mX.' * mX)));
end
在我的计算距离矩阵项目中给出了一个概括。
附注:
使用MATLAB的pdist
进行比较:squareform(pdist(mX.'))
等价于CalcDistMtx(mX)
。
也就是说,输入应该被转置。
计算机并不是无限大或无限快的。人们认为它们有很多内存和快速的CPU,所以他们只是创造越来越大的问题,最终想知道为什么他们的问题运行缓慢。事实上,这不是计算效率低下,而只是CPU超载。
正如Oli在评论中指出的那样,即使假设您只计算距离矩阵的上半部分或下半部分,也有大约20亿个值需要计算。(6e4^2/2约为2e9。)这将需要大约16 GB的RAM来存储,假设内存中只创建了一个数组的副本。如果您的代码不够简洁,可能会轻易地将其加倍或加三倍。一旦进入虚拟内存,事情就会变得更加缓慢。
想要一个大问题快速运行是不够的。为了真正帮助您,我们需要知道可用的RAM有多少。这是虚拟内存问题吗?您是否在能处理所有所需RAM的CPU上使用64位MATLAB?
pdist
稍微快一点。 - horchler
d = pdist(rand(6e4,3e2));
。 - horchler