более быстрый способ добиться того, что дает мне intersect ()? - PullRequest
Новая
       7

более быстрый способ добиться того, что дает мне intersect ()?

7 голосов
/ 17 ноября 2011

Я обнаружил, что лот времени, проведенного в моей функции matlab, находится в этом коде: 

intersect(freq_bins, our_bins);

Оба могут быть довольно большими векторами и состоять только из целых чисел. Мне просто нужно знать, какие целые числа в обоих. Это действительно примитивная цель intersect (), поэтому я подозреваю, что ответ таков: лучше не становится. Но, может быть, у кого-то есть предложения.

Ответы [ 2 ]

10 голосов
/ 17 ноября 2011

intersect звонки ismember. В вашем случае вам не нужны все сложные проверки, которые выполняет intersect, поэтому вы можете сэкономить некоторые накладные расходы и напрямую вызвать ismember (примечание: я удостоверился, что вы вызвали обе функции перед синхронизацией их): 

a = randi(1000,100,1);
b = randi(1000,100,1);

>> tic,intersect(a,b),toc
ans =
    76
   338
   490
   548
   550
   801
   914
   930
Elapsed time is 0.027104 seconds.

>> tic,a(ismember(a,b)),toc
ans =
   914
   801
   490
   548
   930
   550
    76
   338
Elapsed time is 0.000613 seconds.

Вы можете сделать это еще быстрее, вызвав ismembc, функцию, которая непосредственно выполняет тестирование. Обратите внимание, что ismembc требует отсортированных массивов (так что вы можете отбросить сортировку, если ваш вход уже отсортирован!) 

tic,a=sort(a);b=sort(b);a(ismembc(a,b)),toc
ans =
    76
   338
   490
   548
   550
   801
   914
   930
Elapsed time is 0.000473 seconds.
0 голосов
/ 19 апреля 2012

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

function c = intersect_sorted(a,b)
  ia = 1;
  na = length(a);
  ib = 1;
  nb = length(b);
  ic = 0;
  cn = min(na,nb);
  c = zeros(1,cn);

  while (ia <= na && ib <= nb)
    if (a(ia) > b(ib))
      ib = ib + 1;
    elseif a(ia) < b(ib)
      ia = ia + 1;
    else % a(ia) == b(ib)
      ic = ic + 1;
      c(ic) = a(ia);
      ib = ib + 1;
      ia = ia + 1;
    end
  end
  c = c(1:ic);
end

Максимальное время выполнения для списков длины n и m будет O (n + m). 

>>a = unique(randi(1000,100,1));
>>b = unique(randi(1000,100,1));
>>tic;for i = 1:10000, intersect(a,b); end,toc
Elapsed time is 1.224514 seconds.
>> tic;for i = 1:10000, intersect_sorted(a,b); end,toc
Elapsed time is 0.289075 seconds.
...