matlab - 倍频程/Matlab : Determine unique rows in very large matrix

Question

我在 Octave 中有一个 13146 x 13146 的矩阵，我想确定它的唯一行。 unique(M, "rows") 由于 Octave 内部结构和/或内存限制而失败。

我查看了其他关于查找唯一行的帖子，但没有一篇涉及大型矩阵的这个问题。

我现在的方法是“分而治之”，例如。 G。通过

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 是列数。

是否有更好的方法来达到预期的效果？

Answer 1

基数排序吧!

听起来您需要一种节省内存的排序算法。可以通过首先对行进行排序，然后检查相邻行的重复项来找到唯一行。您可以为此调整基数排序，按顺序对每一列进行排序(而不是按顺序对每个数字进行排序)。这将是对一列而不是整个矩阵进行排序的峰值内存成本。然后遍历排序结果中的行并消除重复项。这是一个 O(n) 操作，只需要足够的内存来容纳两行。

它也可以是“稳定的”。如果在排序过程中除了跟踪重新排列的行值之外还跟踪重新排列的行索引，则可以计算输入-输出映射索引。 (这些是 Matlab 自己的 [B,I] = sort(A) 签名中的 I。)这反过来将允许您重新排列后复制-删除行回到输入中的原始顺序，这样您就可以保留它们的顺序。 (类似于Matlab的unique()的setOrder='stable'选项。)它们也可以用于计算整体唯一性操作的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

当我在 OS X 上的 Matlab R2014b 上对您大小的矩阵进行测试时，它的峰值使用了大约 3 GB 的内存，而仅容纳输入矩阵的内存约为 1 GB。不错。

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