Форма массива классов, связанных с эквивалентностью

Question

У меня есть массив в Matlab. Я пронумеровал каждую запись в массиве с натуральным номером. Поэтому я сформировал отношение эквивалентности в массиве.

Например,

array   = [1 2 3 5 6 7]
classes = [1 2 1 1 3 3].

Я хочу получить массив ячеек: i-я позиция массива ячеек связана с i-ая запись исходного массива и показывает, какие элементы находятся в одном классе с этой записью. Для примера выше я бы получил:

{[1 3 5], [2], [1 3 5], [1 3 5], [6 7], [6 7]}

Это легко сделать с помощью for-loop, но есть ли другое решение? Будет хорошо, если он будет работать быстрее, чем O(n^2), где n размер исходного массива

Edit.Проблема будет решена, если я знаю подход к разбиению отсортированного массива на ячейки с независимыми элементами O(n),

array  = [1 1 1 2 3 3]
groups = {[1 2 3], [4], [5 6]}

Answer 1

Я не знаю, как это сделать без циклов for, но вы можете использовать комбинацию sort, diff, а также find организовать и разбить идентификаторы класса эквивалентности. Это даст вам в основном векторизованное решение, где уровень цикла M-кода O(n) где n это количество классов, а не длина всего входного массива. Это должно быть довольно быстро на практике.

Вот грубый пример использования индексации. Быть осторожен; возможно, где-то там была ошибка с одним случайным случаем, так как я только что это исправил.

function [eqVals,eqIx] = equivsets(a,x)
%EQUIVSETS Find indexes of equivalent values

[b,ix] = sort(x);
ixEdges = find(diff(b)); % identifies partitions between equiv classes
ix2 = [0 ixEdges numel(ix)];
eqVals = cell([1 numel(ix2)-1]);
eqIx = cell([1 numel(ix2)-1]);
% Map back to original input indexes and values
for i = 1:numel(ix2)-1
    eqIx{i} = ix((ix2(i)+1):ix2(i+1));
    eqVals{i} = a(eqIx{i}); 
end

Я включил индексы в вывод, потому что они часто более полезны, чем сами значения. Вы бы назвали это так.

% Get indexes of occurrences of each class
equivs = equivsets(array, classes)
% You can expand that to get equivalences for each input element
equivsByValue = equivs(classes)

Намного эффективнее сначала создать списки для каждого класса, а затем расширить их, чтобы они соответствовали входным индексам. Вы не только должны сделать работу только один раз, но когда вы используете b = a(ix) Чтобы расширить небольшой массив ячеек на больший, оптимизация копирования при записи в Matlab приведет к повторному использованию памяти для базовых числовых mxArrays, так что вы получите более компактное представление в памяти.

Это преобразование часто появляется при работе с unique() или базы данных. Для систем поддержки принятия решений и вещей в стиле хранилища данных, с которыми я работал, это происходит повсеместно. Я хотел бы, чтобы это было встроено в Matlab. (И, возможно, он был добавлен в один из наборов инструментов db или timeseries в последние годы; я несколько версий позади.)

Реально, если производительность этого критична для вашего кода, вы можете также рассмотреть возможность перехода к функциям Java или C MEX и их реализации там. Но если ваши наборы данных имеют низкую мощность, то есть имеют небольшое количество классов / различных значений, например numel(unique(classes)) / numel(array) имеет тенденцию быть меньше чем 0,1 или около того - реализация M-кода, вероятно, будет просто в порядке.

Answer 2

Не уверен насчет сложности, но accumarray с выводом ячейки полезно для разбиения массива на основе уникальных значений классов:

data = sortrows([classes; array].',1) %' stable w.r.t. array
arrayPieces = accumarray(data(:,1),data(:,2)',[],@(x){x.'})
classElements = arrayPieces(classes).'

---

Относительно разбитого отсортированного массива на ячейки индейцев:

>> array  = [1 1 1 2 3 3]
>> arrayinds = accumarray(array',1:numel(array),[],@(x){x'})' %' transpose for rows
arrayinds = 
    [1x3 double]    [4]    [1x2 double]
>> arrayinds{:}
ans =
     1     2     3
ans =
     4
ans =
     5     6

Answer 3

По второму вопросу:

array  = [1 1 1 2 3 3]; %// example data

1. использование diff чтобы найти конец каждого прогона равных значений, и из этого построить группы:

   ind = [0 find(diff([array NaN])~=0)];
   groups = arrayfun(@(n) ind(n)+1:ind(n+1), 1:numel(ind)-1, 'uni', 0);
   

2. Тот же подход с использованием unique:

   [~, ind] = unique(array);
   ind = [0 ind];
   groups = arrayfun(@(n) ind(n)+1:ind(n+1), 1:numel(ind)-1, 'uni', 0);
   

Я не проверял, если сложность O(n), хотя.