与"行"相交的更快替代方案 - MATLAB

Question

我有一个用Matlab编写的代码，它使用"intersect"来查找在两个大矩阵中相交的向量（及其索引）。我发现"intersect"是我的代码中最慢的一行（相差很大）。不幸的是，到目前为止，我找不到更快的替代方案。

举个例子，在我的电脑上运行下面的代码大约需要5秒：

profile on
for i = 1 : 500
    a = rand(10000,5);
    b = rand(10000,5);
    [intersectVectors, ind_a, ind_b] = intersect(a,b,'rows');
end
profile viewer

我想知道是否有更快的方法。注意，矩阵（a）和（b）具有5列。对于这两个矩阵，行数不必相同。

任何帮助都会很棒。感谢

Answer 1

讨论和解决方案代码

您可以使用一种方法，利用fast matrix multiplication in MATLAB将输入数组的5列转换为一列，方法是将每列视为单个数字的有效"数字"。因此，您最终会得到一个只有列的数组，然后，您可以在不使用'rows'的情况下使用intersect或ismember，这必须大大加快代码的速度！

以下是承诺的实现，作为易于使用的功能代码-

intersectrows_fast_v1.m:

function [intersectVectors, ind_a, ind_b] = intersectrows_fast_v1(a,b)
%// Calculate equivalent one-column versions of input arrays
mult = [10^ceil(log10( 1+max( [a(:);b(:)] ))).^(size(a,2)-1:-1:0)]'; %//'
acol1 = a*mult;
bcol1 = b*mult;
%// Use intersect without 'rows' option for a good speedup
[~, ind_a, ind_b] = intersect(acol1,bcol1);
intersectVectors = a(ind_a,:);
return;

intersectrows_fast_v2.m:

function [intersectVectors, ind_a, ind_b] = intersectrows_fast_v2(a,b)
%// Calculate equivalent one-column versions of input arrays
mult = [10^ceil(log10( 1+max( [a(:);b(:)] ))).^(size(a,2)-1:-1:0)]'; %//'
acol1 = a*mult;
bcol1 = b*mult;
%// Use ismember to get indices of the common elements
[match_a,idx_b] = ismember(acol1,bcol1);
%// Now, with ismember, duplicate items are not taken care of automatically as
%// are done with intersect. So, we need to find the duplicate items and
%// remove those from the outputs of ismember
[~,a_sorted_ind] = sort(acol1);
a_rm_ind =a_sorted_ind([false;diff(sort(acol1))==0]); %//indices to be removed
match_a(a_rm_ind)=0;
intersectVectors = a(match_a,:);
ind_a = find(match_a);
ind_b = idx_b(match_a);
return;

快速测试和结论

对于问题中列出的数据量，运行时为-

-------------------------- With original approach
Elapsed time is 3.885792 seconds.
-------------------------- With Proposed approach - Version - I
Elapsed time is 0.581123 seconds.
-------------------------- With Proposed approach - Version - II
Elapsed time is 0.963409 seconds.

结果似乎表明，两种提出的方法中的version - I有很大的优势，与原始方法相比，其惊人的加速速度约为6.7x！！

此外，请注意，如果您不需要基于"行"方法的原始intersect的三个输出中的任何一个或两个，那么这两种方法都可以进一步缩短，以获得更好的运行时性能！