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

Question

我有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)

Answer 1

该函数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时间很糟糕（对此感到抱歉）。在 Octave 中，比 快 100 倍以上。MATLAB 中的计时会有所不同，但仍然应该是最快的选择。（注意，我还将双循环替换为单循环，这是相同的，但更简单，可能更快。）tictocop2op1ismember

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