5

我知道 matlab 有一个内置的 pdist 函数，可以计算成对距离。但是，我的矩阵太大了，它的 60000 x 300 和 matlab 内存不足。

这个问题是对Matlab euclidean pairwise square distance function的跟进。

这种计算效率低下是否有任何解决方法。我尝试手动编码成对距离计算，通常需要一整天才能运行（有时需要 6 到 7 小时）。

任何帮助是极大的赞赏！

4

3 回答 3

6

好吧，我忍不住到处玩。我创建了一个名为的 Matlab mex C 文件pdistc，该文件实现了单精度和双精度的成对欧几里得距离。在我使用 Matlab R2012b 和 R2015a 的机器上，对于大输入（例如 60,000×300），它比pdist（以及底层辅助函数）快 20-25%。pdistmex

正如已经指出的那样，这个问题从根本上是受内存限制的，你需要很多内存。我的 mex C 代码使用了超出输出所需的最少内存。在将其内存使用情况与 的进行比较时pdist，看起来两者几乎相同。换句话说，pdist没有使用大量的额外内存。您的内存问题可能在于调用之前已用完的内存pdist（您可以clear用来删除任何大型数组吗？）或者仅仅是因为您试图在微型硬件上解决一个大的计算问题。

因此，我的pdistc函数可能无法整体节省您的内存，但您可以使用我内置的另一个功能。您可以计算整体成对距离向量的块。像这样的东西：

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

这要慢得多（10 倍左右），而且我的这部分 C 代码没有得到很好的优化，但它可以减少内存使用量——假设您一次不需要整个数组。pdist请注意，您可以使用(or )更有效地执行相同的操作，方法pdistc是创建一个循环，在该循环中X直接传入 的子集，而不是全部。

如果你有一个 64 位的 Intel Mac，你不需要编译，因为我已经包含了.mexmaci64二进制文件，否则你需要弄清楚如何为你的机器编译代码。我帮不了你。您可能无法编译它，或者您需要通过自己编辑代码来解决兼容性问题。也有可能有bug，代码会导致matlab崩溃。另外，请注意，相对于机器 epsilon ( )pdist范围内的两者之间的差异，您可能会得到稍微不同的输出。可能会或可能不会做一些花哨的事情来避免大​​输入和其他数字问题的溢出，但请注意我的代码没有。epspdist

此外，我创建了一个简单的纯 Matlab 实现。它比 mex 代码慢很多，但仍然比简单的实现或pdist.

所有文件都可以在这里找到。ZIP 存档包含所有文件。它是 BSD 许可的。随意优化（我在 C 代码中尝试了 BLAS 调用和 OpenMP 无济于事——也许一些指针魔术或 GPU/OpenCL 可以进一步加快它）。我希望它可以对您或其他人有所帮助。

于 2013-07-23T00:20:37.280 回答
5

在我的系统上，以下是最快的（甚至比pdistc@horchler 的 C 代码还要快）：

function [ mD ] = CalcDistMtx ( mX )    
  vSsqX = sum(mX .^ 2);
  mD = sqrt(bsxfun(@plus, vSsqX.', vSsqX) - (2 * (mX.' * mX)));       
end

我认为，您需要一个经过良好调整的 C 代码来解决这个问题。

更新
由于MATLAB R2016b MATLAB 支持隐式广播而不使用bsxfun().

因此代码可以写成：

function [ mD ] = CalcDistMtx ( mX )    
  vSsqX = sum(mX .^ 2, 1);
  mD = sqrt(vSsqX.'+ vSsqX - (2 * (mX.' * mX)));       
end

在我的计算距离矩阵项目中给出了概括。

PS
使用 MATLABpdist进行比较：squareform(pdist(mX.'))相当于CalcDistMtx(mX).
即输入应该被转置。

于 2016-08-25T10:31:09.863 回答
0

计算机不是无限大，也不是无限快。人们认为他们有很多内存，一个快速的 CPU，所以他们只会制造越来越大的问题，然后最终想知道为什么他们的问题运行缓慢。事实是，这不是计算效率低下。它只是一个过载的 CPU。

正如 Oli 在评论中指出的那样，即使假设您只计算距离矩阵的上半部分或下半部分，也需要计算类似 2e9 的值。（6e4^2/2 大约是 2e9。）这将需要大约 16 GB 的 RAM 来存储，假设在内存中只创建了一个数组副本。如果您的代码草率，您可能很容易将其翻倍或翻倍。一旦你进入虚拟内存，事情就会变得慢得多。

想要一个大问题快速运行是不够的。为了真正帮助您，我们需要知道有多少 RAM 可用。这是虚拟内存问题吗？您是否在可以处理所有需要的 RAM 的 CPU 上使用 64 位 MATLAB？

于 2013-07-21T22:13:02.970 回答