Octave / Matlab: определение уникальных строк в очень большой матрице

У меня есть матрица 13146 x 13146 в Октаве, уникальные строки которой я хочу определить. unique(M, "rows") не удается из-за внутренних октав и/или ограничений памяти.

Я просмотрел другие сообщения о поиске уникальных строк, но ни одно из них не касалось этой проблемы с большими матрицами.

Мой подход сейчас был бы "разделяй и властвуй", например, путем 

A(:,:,i)=M(r_i:s_i,:)
B(:,:,i)=unique(A(:,:,i), "rows")

С i индексом подматрицы, r_i и s_i начальным и конечным номерами строк подматриц. Чтобы вернуть все данные в одну большую матрицу (и снова определить уникальные строки): 

C(:,:,i)=B(:,:,i)'
D=reshape(C,l,n*m)
E=D'
F=unique(E, "rows")

С n числом подматриц, m исходным числом строк в подматрице и l числом столбцов.

Есть ли лучший способ достичь желаемого результата?
3 5
matlab octave

3 ответа:

Вы можете использовать скользящее окно для столбцов и использовать размер окна, который не вызывает проблем с памятью. Вот решение 

function A = winuninque(A, winSz)
nCol = size(A,2);
I = zeros(size(A,1), 0);
for k=1:winSz:nCol
    [~, ~, I] = unique([I A(:,k:min(k+winSz-1,end))], 'rows');
end
[~, I] = unique(I);
A = A(I, :);
end

Бенчмарк

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

>> A=repmat(rand(13146,13146), 2, 1);
>> A=A(randperm(end), :);
>> A=A(1:end/2,:);

>> tic; B=rrunique(A); toc
Elapsed time is 13.318752 seconds.
>> tic; C=winunique(A, 16); toc
Elapsed time is 6.606122 seconds.
>> tic; D=unique(A, 'rows'); toc
Elapsed time is 29.815333 seconds.
>> isequal(B,C,D)
ans =
     1
>> size(D)
ans =
        9880       13146
1

Радикс сортировки!

Похоже, вам нужен эффективный алгоритм сортировки памяти. Уникальные строки можно найти, сначала отсортировав их, а затем проверив соседние строки на наличие дубликатов. Вы можете адаптировать для этого сортировку по радиксу, сортируя по каждому столбцу в последовательности (вместо каждой цифры в последовательности). Это будет пиковая стоимость памяти для сортировки одного столбца вместо всей матрицы. Затем пройдите по строкам в отсортированном результате и устраните дубликаты. Это операция O(n) и только требуется достаточно памяти, чтобы вместить две строки.

Он также может быть "стабильным". Если вы отслеживаете переупорядоченные индексы строк в дополнение к переупорядоченным значениям строк в процессе сортировки, вы можете вычислить индексы сопоставления ввода-вывода. (Это I в сигнатуре собственного [B,I] = sort(A) Matlab.) Это, в свою очередь, позволит вам переставить строки после удаления дубликатов обратно в их первоначальный порядок во входных данных, чтобы вы могли сохранить их порядок. (Как вариант setOrder='stable' в Matlab unique().) Они также могут быть использованы для вычисления индексов отображения in-out для общей операции уникальности, так что вы можете воспроизвести полную многовыходную сигнатуру unique(), что может быть весьма полезно.

Пример кода

Вот базовый пример реализации. Я не проверил его полностью, поэтому не используйте его в производстве, не проведя собственное тестирование.

function A = rrunique(A)
%RRUNIQUE "Radix Row Unique" - find unique rows using radix sort
%
% # Returns the distinct rows in A. Uses the memory-efficient radix sort
% # algorithm, so peak memory usage stays low(ish) for large matrices.

% # This uses a modified radix sort where only the row remapping indexes are
% # rearranged at each step, instead of sorting the whole input, to avoid
% # having to rewrite the large input matrix.

ix = 1:size(A,1); % # Final in-out mapping indexes

% # Radix sort the rows
for iCol = size(A,2):-1:1
    c = A(ix,iCol);
    [~,ixStep] = sort(c);
    % # Don't do this! too slow
    % # A = A(ixStep,:);
    % # Just reorder the mapping indexes
    ix = ix(ixStep);
end    

% # Now, reorder the big array all at once
A = A(ix,:);

% # Remove duplicates
tfKeep = true(size(A,1),1);
priorRow = A(1,:);
for iRow = 2:size(A,1)
    thisRow = A(iRow,:);
    if isequal(thisRow, priorRow)
        tfKeep(iRow) = false;
    else
        priorRow = thisRow;
    end
end
A = A(tfKeep,:);

end

Когда я тестировал это на матрице вашего размера на Matlab R2014b на OS X, она достигла пика примерно в 3 ГБ используемой памяти, против около 1 ГБ, чтобы вместить только входную матрицу. Неплохо.

>> m = rand([13146,13146]);
>> tic; rrunique(m); toc
Elapsed time is 17.435783 seconds.
6

Основная идея здесь та же, что и с Andrew's answer, просто реализация немного отличается на более позднем этапе. Итак, мы сортируем строки входного массива, помещая дубликаты друг на друга. Затем мы пробегаем по строкам в поисках дубликатов, что может быть эффективно сделано с помощью diff. Из выходных данных diff мы обнаруживаем строки all zeros, которые представляют эти повторяющиеся строки. Мы создаем логическую маску из обнаружения и используем эту маску для извлечения действительного строки из входного массива. Вот реализация, и это, кажется, использует половину памяти, чем с unique(...'rows') -

sM = sortrows(M);
out = sM([true ; any(diff(sM,[],1)~=0,2)],:);
0