Обратный поиск с неуникальными значениями

Что я пытаюсь сделать

У меня есть массив чисел:

>> 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 имеет 10M элементов с уникальными значениями 100k), даже этот глупый цикл for в 100 раз быстрее:

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

Но я чувствую, что это не может быть лучшим способом сделать это.

Мы можем предположить, что A содержит только целые числа от 1 до максимума (потому что, если это не так, я всегда могу передать его через unique сделать так)

Источник

2 ответа

Решение

Это простая задача для 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 функция), так что вы можете посмотреть здесь стабильную версию accumarray, если это проблема.

Выше решение также предполагает 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 предпочитает работать с отсортированными массивами.

Источник

Это решение должно работать в режиме O(N*log(N)) из-за сортировки, но требует большого объема памяти (требует 3-кратного объема входной памяти):

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

Мне любопытно, хотя производительность.

Источник
Другие вопросы по тегам