如果不在数组中，则提高附加数组元素的速度

Question

我有一个数组S，它有一些独特的元素。我想从数组N中附加尚未在S.

一个语法简单的方法是：

S = union( S, N, 'stable' );

我发现手动附加可以更快，使用ismember或隐式扩展：

% ismember approach
S = [S; N(~ismember(N,S))];
% imp. expansion approach
S = [S; N(~any(S(:)==N(:).',1))];

但是，在循环内执行此操作仍然感觉很脏，并且隐式扩展对于大型输入而言可能会很昂贵。

有没有更高效的替代方案？

如果有帮助，我们可以假设S并N只包含整数。但是，我们不能假设它S是排序的，新元素从N可以是任何正整数。

最小的例子：

Ntest = [1 2 3 4
         2 5 3 6
         1 5 7 9];
S = [];
for ii = 1:3
    N = Ntest(ii,:).';
    S = union(S,N,'stable');
end
% S = [ 1; 2; 3; 4; 5; 6; 7; 9 ]

在实际情况中，我不知道预先的潜在价值，N就像我做的那样Ntest上面。

下面是 4 种方法的一些基准测试代码，结果如下。就我而言，我可能会对 的不同值有一个大循环N，并且每个N. 这对应于此汇总表中最右侧的列，您可以在其中看到隐式扩展方法要快得多。

range(Ntest): 1 to 1e4     1 to 1e4     1 to 1e4    1 to 1e4
size(Ntest):  [1e3,1e3]    [1e4,1e3]    [1e2,1e3]   [1e2,1e4]
union:        0.972 sec    1.217 sec    0.779 sec   9.341 sec
ismember:     0.763 sec    0.559 sec    0.492 sec   5.439 sec
implicit:     6.966 sec    too long!    0.295 sec   3.886 sec
setdiff:      0.599 sec    0.534 sec    0.477 sec   5.364 sec

rng(0);
Ntest = randi([1,1e4],1e3,1e3);

f = @()f_union( Ntest );
fprintf( 'union: \t%.3f sec\n', timeit( f ) );
f = @()f_ismember( Ntest );
fprintf( 'ismember: \t%.3f sec\n', timeit( f ) );
f = @()f_implicit( Ntest );
fprintf( 'implicit: \t%.3f sec\n', timeit( f ) );
f = @()f_setdiff( Ntest );
fprintf( 'setdiff: \t%.3f sec\n', timeit( f ) );

function f_union( Ntest )
    S = [];
    for ii = 1:size(Ntest,2)
        N = Ntest(:,ii);
        S = union(S,N,'stable');
    end
end
function f_ismember( Ntest )
    S = [];
    for ii = 1:size(Ntest,2)
        N = Ntest(:,ii);
        S = [S; N(~ismember(N,S))];
    end    
end
function f_implicit( Ntest )
    S = [];
    for ii = 1:size(Ntest,2)
        N = Ntest(:,ii);
        S = [S; N(~any(S(:)==N(:).',1))];
    end    
end
function f_setdiff( Ntest )    
    S = [];
    for ii = 1:size(Ntest,2)
        N = Ntest(:,ii);
        S = [S;setdiff(N,S)];
    end
end

Answer 1

由于假设数据类型为正整数，因此您可以使用逻辑矩阵来存储整数的位置：

function f_logical( Ntest )
    S = false;
    for ii = 1:size(Ntest,2)
        N = Ntest(:,ii);
        S(N) = true;
    end    
end

如果元素范围很大并且数据稀疏，那么使用稀疏矩阵可能会有所帮助：

function f_sparse( Ntest )
    S = sparse(false);
    for ii = 1:size(Ntest,2)
        N = Ntest(:,ii);
        S(N) = true;
    end    
end

ismember与Octave中的解决方案比较：

Elapsed time for <ismember> is 1.54181 seconds.
Elapsed time for <sparse>   is 0.266474 seconds.
Elapsed time for <logical>  is 0.0189412 seconds.