时间戳

首页 > 解决方案 > 查找向量 b 的唯一索引的最快方法，其中数组 A(i,j) == b

matlab - 查找向量 b 的唯一索引的最快方法，其中数组 A(i,j) == b

问题描述

我有 2 个大数组A和b：

A：10.000++ 行，4 列，非唯一整数
b：具有 500.000++ 个元素的向量，唯一整数

由于 的值的唯一性b，我需要找到 的唯一索引b，其中A(i,j) == b。

我开始的是

[rows,columns] = size(A);
B = zeros(rows,columns);
for i = 1 : rows
    for j = 1 : columns
        B(i,j) = find(A(i,j)==b,1);
    end
end

这需要大约5.5 秒来计算，这很长，因为A并且b可能会更大......记住我试图通过使用逻辑索引和减少 for 循环来加速代码

[rows,columns] = size(A);
B = zeros(rows,columns);
for idx = 1 : numel(b)
    B(A==b(idx)) = idx;
end

遗憾的是，这需要更长的时间：21 秒

我什至尝试使用bsxfun

for i = 1 : columns
   [I,J] = find(bsxfun(@eq,A(:,i),b))
    ... stitch B together ...
end

但是对于更大的数组，最大数组大小很快就会超过（102,9GB ...）。

你能帮我找到一个更快的解决方案吗？提前致谢！

编辑：我扩展了，这将算法速度提高了 2 倍！谢谢，但总体上还是太慢了... ;)find(A(i,j)==b,1)

标签： matlabperformancefind

解决方案

该功能ismember是解决此问题的正确工具：

[~,B] = ismember(A,b);

测试代码：

function so
  A = rand(1000,4);
  b = unique([A(:);rand(2000,1)]);

  B1 = op1(A,b);
  B2 = op2(A,b);
  isequal(B1,B2)

  tic;op1(A,b);op1(A,b);op1(A,b);op1(A,b);toc
  tic;op2(A,b);op2(A,b);op2(A,b);op2(A,b);toc
end

function B = op1(A,b)
  B = zeros(size(A));
  for i = 1:numel(A)
    B(i) = find(A(i)==b,1);
  end
end

function B = op2(A,b)
  [~,B] = ismember(A,b);
end

我在 Octave 上运行它，它的循环速度不如 MATLAB。它也没有这个timeit功能，因此使用tic/的时间很糟糕toc（对不起）。在 Octave 中，op2比op1. MATLAB 中的时序会有所不同，但ismember仍应是最快的选择。（注意我也用一个循环替换了你的双循环，这是一样的，但更简单，可能更快。）

如果要在 中反复进行搜索b，值得先排序b，然后实现自己的二分搜索。这将避免检查和排序ismember。请参阅另一个问题。

推荐阅读