數組比較的向量化

Question

我有通過將數組MatchesX.trainIdx中的一個元素與第二個數組MatchesX.queryIdx中的一個或多個元素進行匹配而創建的全部函數函數。

爲了獲得只說功能可按我運行相同的功能向前

Matches1=Matcher.match(Descriptors1,Descriptors2); 

，然後向後

Matches2=Matcher.match(Descriptors2,Descriptors1); 

然後查找在以下方式中的作用都存在的元素的雙射元素：

k=1; 
DoubleMatches=Matches1; 

for i=1:length(Matches1) 
    for j=1:length(Matches2) 
     if((Matches1(i).queryIdx==Matches2(j).trainIdx)&&(Matches1(i).trainIdx==Matches2(j).queryIdx)) 
      DoubleMatches(k)=Matches1(i); 
      k=k+1; 
     end 
    end 
end 

DoubleMatches(k:end)=[]; 

這當然做的工作，但它是老鼠她的不雅和似乎打擾了JIT加速器（計算時間與accel on和accel off是一樣的）。

你能想出一種將此表達式向量化的方法嗎？有沒有其他避免JIT「打擊」的方法？

非常感謝，對於奇怪的結構感到抱歉，我正在使用MEX功能。讓我知道如果重寫「正常」陣列代碼將有助於

Answer 1

訪問多維結構的數據是在MATLAB中出了名的慢，所以將您的數據到一個普通的數組有一定的幫助：

kk = 1; 
DoubleMatches = Matches1; 

%// transform to regular array 
Matches1queryIdx = [Matches1.queryIdx]; 
Matches1trainIdx = [Matches1.trainIdx]; 

Matches2queryIdx = [Matches2.queryIdx]; 
Matches2trainIdx = [Matches2.trainIdx]; 

%// loop through transformed data instead of structures 
for ii = 1:length(Matches1queryIdx) 
    for jj = 1:length(Matches1queryIdx) 
     if((Matches1queryIdx(ii)==Matches2trainIdx(jj)) && ... 
       (Matches1trainIdx(ii)==Matches2queryIdx(jj))) 
      DoubleMatches(kk) = Matches1(ii); 
      kk = kk+1; 
     end 
    end 
end 

DoubleMatches(kk:end)=[]; 

還有，其幾乎完全矢量化的解決方案：

matches = sum(... 
    bsxfun(@eq, [Matches1.queryIdx], [Matches2.trainIdx].') & ... 
    bsxfun(@eq, [Matches1.trainIdx], [Matches2.queryIdx].')); 

contents = arrayfun(@(x).. 
    repmat(Matches1(x),1,matches(x)), 1:numel(matches), ... 
    'Uniformoutput', false); 

DoubleMatches2 = [contents{:}]'; 

注意，這可能是很多更多的內存密集型（它有O（N²）峯值內存佔用，而不是O（N）爲其他，儘管峯值內存的數據類型爲logical，因此小於double ...）。最好事先檢查一下你應該使用哪一個。

稍微測試一下。我用下面的僞數據：

Matches1 = struct(... 
    'queryIdx', num2cell(randi(25,1000,1)),... 
    'trainIdx', num2cell(randi(25,1000,1))... 
); 

Matches2 = struct(... 
    'queryIdx', num2cell(randi(25,1000,1)),... 
    'trainIdx', num2cell(randi(25,1000,1))... 
); 

和以下測試：

%// Your original method 
tic  
    kk = 1; 
    DoubleMatches = Matches1; 

    for ii = 1:length(Matches1) 
     for jj = 1:length(Matches2) 
      if((Matches1(ii).queryIdx==Matches2(jj).trainIdx) && ... 
        (Matches1(ii).trainIdx==Matches2(jj).queryIdx)) 
       DoubleMatches(kk) = Matches1(ii); 
       kk = kk+1; 
      end 
     end 
    end 

    DoubleMatches(kk:end)=[]; 

toc 

DoubleMatches1 = DoubleMatches; 


%// Method with data transformed into regular array 
tic 

    kk = 1; 
    DoubleMatches = Matches1; 

    Matches1queryIdx = [Matches1.queryIdx]; 
    Matches1trainIdx = [Matches1.trainIdx]; 

    Matches2queryIdx = [Matches2.queryIdx]; 
    Matches2trainIdx = [Matches2.trainIdx]; 

    for ii = 1:length(Matches1queryIdx) 
     for jj = 1:length(Matches1queryIdx) 
      if((Matches1queryIdx(ii)==Matches2trainIdx(jj)) && ... 
        (Matches1trainIdx(ii)==Matches2queryIdx(jj))) 
       DoubleMatches(kk) = Matches1(ii); 
       kk = kk+1; 
      end 
     end 
    end 

    DoubleMatches(kk:end)=[]; 

toc 

DoubleMatches2 = DoubleMatches; 


% // Vectorized method 
tic 

    matches = sum(... 
     bsxfun(@eq, [Matches1.queryIdx], [Matches2.trainIdx].') & ... 
     bsxfun(@eq, [Matches1.trainIdx], [Matches2.queryIdx].')); 

    contents = arrayfun(@(x)repmat(Matches1(x),1,matches(x)), 1:numel(matches), 'Uniformoutput', false); 

    DoubleMatches3 = [contents{:}]'; 

toc 

%// Check if all are equal 
isequal(DoubleMatches1,DoubleMatches2, DoubleMatches3) 

結果：

Elapsed time is 6.350679 seconds. %// ( 1×) original method 
Elapsed time is 0.636479 seconds. %// (~10×) method with regular array 
Elapsed time is 0.165935 seconds. %// (~40×) vectorized 
ans = 
    1       %// indeed, outcomes are equal 

Answer 2

假設作爲傳遞給它Matcher.match返回相同對象數組你可以這樣解決這個問題的論點

% m1 are all d1s which have relation to d2 
m1 = Matcher.match(d1,d2); 
% m2 are all d2s, which have relation to m1 
% and all m1 already have backward relation 
m2 = Matcher.match(d2,m1);