具有非唯一值的反向查找

Question

我想做什么

我有一个数字数组：

>> A = [2 2 2 2 1 3 4 4];

我想找到可以找到每个数字的数组索引：

>> B = arrayfun(@(x) {find(A==x)}, 1:4);

换句话说，这个B应该告诉我：

>> for ii=1:4, fprintf('Item %d in location %s\n',ii,num2str(B{ii})); end
Item 1 in location 5
Item 2 in location 1  2  3  4
Item 3 in location 6
Item 4 in location 7  8

这就像 unique 的第二个输出参数，但我想要所有次出现，而不是第一次（或最后一次）出现。我认为这就是所谓的反向查找（其中原始键是数组索引），但如果我错了请指正。

我怎样才能做得更快？

我上面给出的答案是正确的，但它与唯一值的数量成正比。对于一个真正的问题（其中 A 有 1000 万个元素和 100k 个唯一值），即使是这个愚蠢的 for 循环也快了 100 倍：

>> B = cell(max(A),1);
>> for ii=1:numel(A), B{A(ii)}(end+1)=ii; end

但我觉得这不可能是最好的方法。

我们可以假设 A 只包含从 1 到最大值的整数（因为如果它不包含，我总是可以通过 unique 来传递它）。

Answer 1

这对 accumarray 来说是一项简单的任务：

out = accumarray(A(:),(1:numel(A)).',[],@(x) {x})  %'

out{1} = 5
out{2} = 3 4 2 1
out{3} = 6
out{4} = 8 7

然而 accumarray 的问题是 不稳定 （在 unique 的功能意义上），所以你可能想看看，如果这是一个问题。

上述解决方案还假设 A 填充为整数，最好之间没有间隙。如果不是这种情况，则无法提前调用 unique：

A = [2.1 2.1 2.1 2.1 1.1 3.1 4.1 4.1];

[~,~,subs] = unique(A)
out = accumarray(subs(:),(1:numel(A)).',[],@(x) {x})

总而言之，使用浮点数并返回排序输出的最通用解决方案可能是：

[~,~,subs] = unique(A)
[subs(:,end:-1:1), I] = sortrows(subs(:,end:-1:1));  %// optional
vals = 1:numel(A);                                   
vals = vals(I);                                      %// optional
out = accumarray(subs, vals , [],@(x) {x});

out{1} = 5
out{2} = 1 2 3 4
out{3} = 6
out{4} = 7 8

基准

function [t] = bench()
    %// data
    a = rand(100);
    b = repmat(a,100);
    A = b(randperm(10000));

    %// functions to compare
    fcns = {
        @() thewaywewalk(A(:).');
        @() cst(A(:).');
    }; 

    % timeit
    t = zeros(2,1);
    for ii = 1:100;
        t = t + cellfun(@timeit, fcns);
    end
    format long
end

function out = thewaywewalk(A) 
    [~,~,subs] = unique(A);
    [subs(:,end:-1:1), I] = sortrows(subs(:,end:-1:1));
    idx = 1:numel(A);
    out = accumarray(subs, idx(I), [],@(x) {x});
end
function out = cst(A) 
    [B, IX] = sort(A);
    out  = mat2cell(IX, 1, diff(find(diff([-Inf,B,Inf])~=0)));
end

0.444075509687511  %// thewaywewalk
0.221888202987325  %// CST-Link

令人惊讶的是，稳定版 accumarray 比不稳定版更快，因为 Matlab 更喜欢处理排序数组。

Answer 2

由于排序，这个解决方案应该在 O(N*log(N)) 内工作，但是内存非常密集（需要 3 倍的输入内存量）：

[U, X] = sort(A);
    B  = mat2cell(X, 1, diff(find(diff([Inf,U,-Inf])~=0)));

虽然我对性能很好奇。

具有非唯一值的反向查找

Reverse lookup with non-unique values

arrays

matlab

vectorization

reverse-lookup

我想做什么

我怎样才能做得更快？

基准