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

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 中有少量元素。这对应于此摘要中最右侧的列 table，您可以在其中看到隐式扩展方法要快得多。

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

我猜你可以使用下面的代码来加速

X = setdiff(N,S);
S(end + (1:length(X))) = X;

备注 X = N(~ismember(N,S)) 和 X = setdiff(N,S) 都可以找到 N 而不是 S 中的元素，但是加快附加过程的关键步骤是以下方式

S(end + (1:length(X))) = X;

性能比较

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

f = @()f_union( Ntest );
fprintf( 'union: \t%.3f sec\n', timeit( f ) );
f = @()f_ismember_v1( Ntest );
fprintf( 'ismember_v1: \t%.3f sec\n', timeit( f ) );
f = @()f_ismember_v2( Ntest );
fprintf( 'ismember_v2: \t%.3f sec\n', timeit( f ) );
f = @()f_setdiff_v1( Ntest );
fprintf( 'setdiff_v1: \t%.3f sec\n', timeit( f ) );
f = @()f_setdiff_v2( Ntest );
fprintf( 'setdiff_v2: \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_v1( Ntest )
    S = [];
    for ii = 1:size(Ntest,2)
        N = Ntest(:,ii);
        S = [S; N(~ismember(N,S))];
    end    
end

function f_ismember_v2( Ntest )
    S = [];
    for ii = 1:size(Ntest,2)
        N = Ntest(:,ii);
        X = N(~ismember(N,S));
        S(end + (1:length(X))) = X;
    end    
end

function f_setdiff_v1( Ntest )    
    S = [];
    for ii = 1:size(Ntest,2)
        N = Ntest(:,ii);
        S = [S;setdiff(N,S)];
    end
end

function f_setdiff_v2( Ntest )    
    S = [];
    for ii = 1:size(Ntest,2)
        N = Ntest(:,ii);
        X = setdiff(N,S);
        S(end + (1:length(X))) = X;
    end
end

给予

union:  13.314 sec
ismember_v1:    5.836 sec
ismember_v2:    5.658 sec
setdiff_v1:     4.371 sec
setdiff_v2:     4.248 sec

Answer 2

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

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

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

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

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

Improve speed of appending array elements if not already in array

performance

union

matlab

vectorization