查找成对欧几里得距离(距离矩阵)的快速算法

2024-03-12

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

这个问题是后续问题Matlab 欧氏成对平方距离函数 https://stackoverflow.com/questions/17756265/matlab-euclidean-pairwise-square-distance-function/17756481?noredirect=1#comment25925503_17756481.

对于这种计算效率低下的情况,有什么解决方法吗?我尝试手动编码成对距离计算,通常需要一整天的时间才能运行(有时需要 6 到 7 小时)。

任何帮助是极大的赞赏!


嗯,我实在忍不住要玩一玩。我创建了一个Matlab.mex C 文件 http://www.mathworks.com/help/matlab/programming-interfaces-for-c-c-fortran-com.html called pdistc http://biorobots.cwru.edu/personnel/adh/stackoverflow/01/pdistc.c它实现了单精度和双精度的成对欧几里得距离。在我使用 Matlab R2012b 和 R2015a 的机器上,速度比pdist http://www.mathworks.com/help/stats/pdist.html(以及底层的pdistmex辅助函数)用于大型输入(例如 60,000×300)。

正如已经指出的,这个问题从根本上来说是受内存限制的,而且你需要很多内存。我的 mex C 代码使用的内存超出了输出所需的内存。将其内存使用情况与pdist,看起来两者几乎是一样的。换句话说,pdist没有使用大量额外内存。你的内存问题很可能是在调用前内存用完pdist(你能用clear删除任何大型数组?)或者只是因为您试图在小型硬件上解决大型计算问题。

So, my 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二进制文件,但否则您需要弄清楚如何为您的机器编译代码。我无法帮助你。您可能无法编译它,或者存在兼容性问题,您需要自己编辑代码来解决。也有可能存在错误并且代码会导致 Matlab 崩溃。另请注意,您可能会得到与以下内容略有不同的输出:pdist两者之间的差异在于机器 epsilon 的范围(eps http://www.mathworks.com/help/matlab/ref/eps.html). pdist可能会或可能不会做一些花哨的事情来避免大​​输入和其他数字问题的溢出,但请注意我的代码没有。

另外,我创建了一个简单的纯Matlab实现 http://biorobots.cwru.edu/personnel/adh/stackoverflow/01/pdistq.m。它比 mex 代码慢得多,但仍然比简单的实现或中找到的代码快pdist.

所有文件可以在这里找到 http://biorobots.cwru.edu/personnel/adh/stackoverflow/01/。 ZIP 存档包含所有文件。它是 BSD 许可的。请随意优化(我在 C 代码中尝试了 BLAS 调用和 OpenMP,但没有成功——也许一些指针魔法或 GPU/OpenCL 可以进一步加快速度)。我希望它对您或其他人有帮助。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

查找成对欧几里得距离(距离矩阵)的快速算法 的相关文章

  • 计算数组中接下来的 n 个元素的乘积

    我想计算下一个的乘积n矩阵的相邻元素 号码n要相乘的元素数应在函数的输入中给出 例如 对于此输入 我应该从第一个开始计算每 3 个连续元素的乘积 p ind max product 1 2 2 1 3 1 3 这给出了 1 2 2 2 2
  • MATLAB中如何画水平线和垂直线?

    我目前正在尝试在 MATLAB 中绘制简单的垂直线和水平线 例如 我想绘制线 y 245 我该怎么做呢 MATLAB 根据您提供的向量逐点进行绘图 因此 要创建一条水平线 您需要改变x同时保持y对于垂直线恒定 反之亦然 xh 0 10 yh
  • Matlab PARFOR 循环可以通过编程方式打开/关闭吗?

    有一个关于 MATLAB 中 parfor 的简单问题 我想在程序中设置一个标志 以便在 parfor 和常规 for 循环之间进行更改 基本上 我需要此功能 以便我的代码的某些部分可以在 调试 模式下更新图形 然后当关闭该标志时 使用 p
  • 按元素出现的频率对数组元素进行排序

    是否可以在 matlab octave 中使用sort函数根据元素的相对频率对数组进行排序 例如数组 m 4 4 4 10 10 10 4 4 5 应该产生这个数组 5 10 10 10 4 4 4 4 4 5是出现频率较低的元素 位于顶部
  • 在另一列中添加具有特定条件的一列,如 excel 的 sumif

    我有一个像这样的矩阵 A 1 2 2 3 3 4 4 5 5 6 6 8 7 9 8 5 9 4 现在我想添加第二列 条件是如果 limit 0 interval 3 且 limit limit interval 或者换句话说 当第 1 列
  • 如何在 Matlab 中使用谷歌翻译?

    我正在编写一个程序 使用 Matlab 列出电影字幕文件中的所有唯一单词 现在我有一个独特的单词列表 我想将其翻译成我的语言并在观看电影之前了解其含义 有谁知道如何在 Matlab 中使用 Google Translate 以便完成我的脚本
  • 使用mat2cell将MxN的矩阵划分为1xN大小的M矩阵

    我有一个大小为 MxN 的矩阵 比方说 1867x3 1867 行和 3 列 我想将其分成 1867 个大小为 1x3 的单元格 我使用了mat2cell X 1 1866 这里X是矩阵 1867x3 结果给出了两个单元格 一个单元格的大小
  • 在 MATLAB 中重命名文件

    我正在尝试以编程方式重命名工作目录中的文件a temp txt to b hello txt 您建议如何这样做 MATLAB中有一个简单的文件重命名函数吗 我认为您正在寻找 MOVEFILE
  • 两个向量之间的欧氏距离(单行矩阵)

    我有两个向量 单行矩阵 假设我们已经知道长度len A x1 x2 x3 x4 x5 B y1 y2 y3 y4 y5 计算它们之间的欧几里德距离最快的方法是什么 我的第一次尝试是 diff A B sum 0 for column 1 l
  • Matlab 和 Python 中的优化算法(dog-leg trust-region)

    我正在尝试使用 Matlab 和 Python 中的狗腿信赖域算法求解一组非线性方程 在Matlab中有fsolve https www mathworks com help optim ug fsolve html其中此算法是默认算法 而
  • Matlab:如何更改矩阵的存储方式?从 1x1x3 到 1x3?

    我目前有 val 1 0 7216 val 2 0 7216 val 3 0 7216 但我想要 0 7216 0 716 0 721 我可以做什么样的操作来做到这一点 The reshape函数将在这里解决问题 Arrange the e
  • 括号中的波形符字符

    在 MATLAB 中 以下代码执行什么操作 m func returning matrix 波浪号运算符 的作用是什么 在 Matlab 中 这意味着不要将函数中相应的输出参数分配到赋值的右侧 因此 如果func returning mat
  • 黑白随机着色的六角格子

    我正在尝试绘制一个 10 000 x 10 000 随机半黑半白的六边形格子 我不知道如何将该格子的六边形随机填充为黑色和白色 这是我真正想要从这段代码中得到的示例 但我无法做到 https i stack imgur com RkdCw
  • 检测植物图片中的所有分支

    我想知道有什么可以检测下图中的所有绿色树枝 目前我开始应用 Frangi 过滤器 options struct FrangiScaleRange 5 5 FrangiScaleRatio 1 FrangiBetaOne 1 FrangiBe
  • 如何使用 MATLAB 的 substruct 函数创建表示使用“end”的引用的结构?

    我想使用substruct http www mathworks com help matlab ref substruct html函数创建一个结构体以供使用subsref 目的是使用索引字符串subsref而不是通常的 符号 因为我正在
  • 如何更改Plotyy第二轴的颜色和字体大小?

    我使用 MATLAB 的plotyy 函数绘制了两条曲线 AX H1 H2 plotyy voltage span amplitude voltage span Ca SR The problem is that I cannot chan
  • Pandas:向量化局部范围操作([i:i+2] 行的最大值和总和)

    我希望在数据帧中的每一行的局部范围内进行计算 同时避免速度缓慢for环形 例如 对于下面数据中的每一行 我想找到未来 3 天内 包括当天 的最高气温以及未来 3 天内的总降雨量 Day Temperature Rain 0 30 4 1 3
  • MATLAB - 冲浪图数据结构

    我用两种不同的方法进行了计算 对于这些计算 我改变了 2 个参数 x 和 y 最后 我计算了每种变体的两种方法之间的 误差 现在我想根据结果创建 3D 曲面图 x gt on x axis y gt on y axis Error gt o
  • 有效地绘制大时间序列(matplotlib)

    我正在尝试使用 matplotlib 在同一轴上绘制三个时间序列 每个时间序列有 10 6 个数据点 虽然生成图形没有问题 但 PDF 输出很大 在查看器中打开速度非常慢 除了以栅格化格式工作或仅绘制时间序列的子集之外 还有其他方法可以获得
  • Matlab 的 imresize 函数中用于插值的算法是什么?

    我正在使用 Matlab Octaveimresize 对给定的二维数组重新采样的函数 我想了解如何使用特定的插值算法imresize works 我在Windows上使用八度 e g A 1 2 3 4 是一个二维数组 然后我使用命令 b

随机推荐