arrays - 查找 Array 中所有重复元素的所有索引

Question

给定一个整数数组，找出其中所有重复元素的所有索引。

例如，考虑A = [4, 12, 9, 8, 9, 12, 7, 1]. 由于 12 和 9 有重复，它们的所有索引都将被返回，即d = [2, 3, 5, 6]. 的长度A小于 200，整数元素在 1 到 5000 之间。

目前我正在使用以下功能。但是为了满足我的要求，这个功能让我慢了下来。是否有任何可能的性能改进？

function d = fincDuplicates(A)
    U = unique(A);
    [co,ce] = hist(A,U);
    an = ce(co>1);
    d=[];
    for i=1:numel(an)
        d=[d,find(A==an(i))];
    end
end

标签： arraysperformancematlab

Answer 1

编辑：

1：针对注释中突出显示的边缘情况更正了代码，更新了基准。

2：在基准测试中添加了“扩展”解决方案（必须将最大 N 元素减少到 20000）。

3：添加accumarray了基准测试方法（高 N 的获胜者）和sparse方法。

---

这是另一种获得结果的方法，无需使用函数unique或hist. 它确实依赖于函数sort。

以扩展形式（如果您想查看中间步骤的结果）：

A = [4, 12, 9, 8, 9, 12, 7, 1] ;

[B,I] = sort(A) ;    % this will put duplicate elements side by side
df = diff(B) ;       % the duplicates will return '0' when substracted
dx = find(df==0) ;   % find their indices

% Since each duplicate concerns 2 elemts of the array, we add the next
% index for each "flagged" index, taking care not to duplicate the indices
% of sucessive duplicates.
if ~isempty(dx)
    dd = [diff(dx)~=1 , true] ;
    dx = [dx dx(dd)+1] ;
    d = I(dx)   % get the original position of the duplicates in original array
else
    d=[] ;
end

您可以压缩到：

[B,I] = sort(A) ;
dx = find(diff(B)==0) ;
if ~isempty(dx)
    d = I([dx dx([diff(dx)~=1,true])+1]) ;
else
    d = [] ;
end

给出：

d =
     3     2     5     6

我个人也会sort返回索引，但如果没有必要并且您担心性能，您可以接受未排序的结果。

---

这是另一个基准（测试从 10 到 20000 的元素数量）：

在 MATLAB R2016a 上运行

以及它的代码：

function ExecTimes = benchmark_findDuplicates

nOrder = (1:9).' * 10.^(1:3) ; nOrder = [nOrder(:) ; 10000 ; 20000 ] ;
npt = numel(nOrder) ;

ExecTimes = zeros(npt,6) ;

for k = 1:npt
    % Sample data
    N = nOrder(k) ;
    A = randi(5000,[1,N]) ;

    % Benchmark
    f1 = @() findDuplicates_histMethod(A) ;
    f2 = @() findDuplicates_histcountMethod(A) ;
    f3 = @() findDuplicates_sortMethod(A) ;
    f4 = @() findDuplicates_expansionMethod(A) ;
    f5 = @() findDuplicates_accumarrayMethod(A) ;
    f6 = @() findDuplicates_sparseMethod(A) ;
    ExecTimes(k,1) = timeit( f1 ) ;
    ExecTimes(k,2) = timeit( f2 ) ;
    ExecTimes(k,3) = timeit( f3 ) ;
    ExecTimes(k,4) = timeit( f4 ) ;
    ExecTimes(k,5) = timeit( f5 ) ;
    ExecTimes(k,6) = timeit( f6 ) ;

    clear A
    disp(N)
end

function d = findDuplicates_histMethod(A)
    U = unique(A);
    [co,ce] = hist(A,U);
    an = ce(co>1);
    d=[];
    for i=1:numel(an)
        d=[d,find(A==an(i))];
    end
end

function d = findDuplicates_histcountMethod(A)
    [~,idxu,idxc] = unique(A);
    [count, ~, idxcount] = histcounts(idxc,numel(idxu));
    idxkeep = count(idxcount)>1;
    idx_A = 1:length(A);
    d = idx_A(idxkeep);
end

function d = findDuplicates_sortMethod(A)
    [B,I] = sort(A) ;
    dx = find(diff(B)==0) ;
    if ~isempty(dx)
        d = I([dx dx([diff(dx)~=1,true])+1]) ;
    else
        d=[];
    end
end

function d = findDuplicates_expansionMethod(A)
    Ae = ones(numel(A),1) * A ;
    d = find(sum(Ae==Ae.')>1) ;
end

function d = findDuplicates_accumarrayMethod(A)
    d = find(ismember(A, find(accumarray(A(:), 1)>1))) ;
end

function d = findDuplicates_sparseMethod(A)
    d = find(ismember(A, find(sparse(A, 1, 1)>1)));
end

end