Самый быстрый способ найти единственный индекс вектора 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,9 ГБ ...).

Можете ли вы помочь мне найти более быстрое решение для этого?Заранее спасибо!

РЕДАКТИРОВАТЬ: я расширил find(A(i,j)==b,1), что ускоряет алгоритм в 2 раза!Спасибо, но в целом все еще слишком медленно ...;)

Answer 1

Предполагая, что у вас есть положительные целые числа, вы можете использовать индексирование массива:

mm = max(max(A(:)),max(b(:)));
idxs = sparse(b,1,1:numel(b),mm,1);
result = full(idxs(A));

Если диапазон значений мал, вы можете использовать плотную матрицу вместо разреженной матрицы:

mm = max(max(A(:)),max(b(:)));
idx = zeros(mm,1);
idx(b)=1:numel(b);
result = idx(A);

Answer 2

Функция 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 (извините за это).В Октаве op2 более чем в 100 раз быстрее, чем op1.В MATLAB время будет другим, но самый быстрый вариант все равно должен быть ismember.(Обратите внимание, что я также заменил ваш двойной цикл одним циклом, это то же самое, но проще и, вероятно, быстрее.)

Если вы хотите многократно выполнять поиск в b, стоит отсортировать b сначала, и реализуйте свой собственный бинарный поиск.Это позволит избежать проверок и сортировки, которые ismember делает.См. этот другой вопрос .