使用 'rows' 比 INTERSECT 更快的替代方法 - 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 列转换为一列，方法是将每一列视为单个数字的重要 "digit"。因此，您最终会得到一个只有列的数组，然后您可以使用 intersect 或 ismember 而不使用 'rows'，这必须大大加快代码速度！

以下是承诺的实现，作为函数代码以便于使用 -

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 和基于 'rows' 的方法的三个输出中的任何一个或两个，那么建议的方法都可以进一步缩短以获得更好的运行时性能！

使用 'rows' 比 INTERSECT 更快的替代方法 - MATLAB

Faster alternative to INTERSECT with 'rows' - MATLAB

performance

matlab

matrix

intersect

讨论和解决代码

快速测试和结论