我有数据(数值的M×N,N> 2)到达由第一列进行排序,然后通过第二个。 有谁知道一个有效的算法,将数据转换为按第二列排序,然后是第一列?很明显,sortrows(data,[2,1])会诀窍,但我正在寻找一些利用输入数据的现有结构以获得更高速度的东西,因为M非常大。快速MATLAB方法改变与调用sortRows列顺序
另外,在第一两列中的数据是已知的整数集合(每个多小于M)。
我有数据(数值的M×N,N> 2)到达由第一列进行排序,然后通过第二个。 有谁知道一个有效的算法,将数据转换为按第二列排序,然后是第一列?很明显,sortrows(data,[2,1])会诀窍,但我正在寻找一些利用输入数据的现有结构以获得更高速度的东西,因为M非常大。快速MATLAB方法改变与调用sortRows列顺序
另外,在第一两列中的数据是已知的整数集合(每个多小于M)。
基于MATLAB R2010b的帮助文档,函数SORTROWS使用稳定的版本的quicksort。由于stable sorting algorithms "maintain the relative order of records with equal keys",你可以达到你想要的东西简单地相对于诉诸已经排序的数据到第二列:
data = sortrows(data,2);
这一结果将保持在第一列元素的相对顺序,使得数据将先按第二栏排序,然后按第一栏排序。
由于在第一列中的数据已经排序,则不需要再次进行排序就可以了。这将是稍快,如果你这样做:
>> d = rand(10000,2); d = round(d*100); d = sortrows(d,1);
>> tic; a1 = sortrows(d, 2); toc;
Elapsed time is 0.006805 seconds.
对战:
>> tic; a2 = sortrows(d, [2 1]); toc;
Elapsed time is 0.010207 seconds.
>> isequal(a1, a2)
ans =
1
我不停地翻动走在这一点,但不能把它比调用sortRows方法快。这利用了每一对密钥都是唯一的,这在上面我没有提到。
% This gives us unique rows of integers between one and 10000, sorted first
% by column 1 then 2.
x = unique(uint32(ceil(10000*rand(1e6,2))),'rows');
tic;
idx = zeros(size(x,1),1);
% Work out where each group of the second keys will start in the sorted output.
StartingPoints = cumsum([1;accumarray(x(:,2),1)]);
% Work out where each group of the first keys is in the input.
Ends = find([~all(diff(x(:,1),1,1)==0,2);true(1,1)]);
Starts = [1;Ends(1:(end-1))+1];
% Build the index.
for i = 1:size(Starts)
temp = x(Starts(i):Ends(i),2);
idx(StartingPoints(temp)) = Starts(i):Ends(i);
StartingPoints(temp) = StartingPoints(temp) + 1;
end
% Apply the index.
y = x(idx,:);
toc
tic;
z = sortrows(x,2);
toc
isequal(y,z)
给我的算法0.21秒和第二秒0.18(不同的随机种子稳定)。
如果有人看到任何进一步加快(比其他MEX)请随时补充。
好点,这确实加快了一点。查看nx3矩阵的sortrows算法(我在R2007a上),它调用每列的排序。所以避免这种情况会大大提高。 – MatlabSorter 2011-01-31 17:23:27
@MatlabSorter:另外,我刚才检查的说明文件R2007a实现调用sortRows的,并且该算法是稳定的,就像R2010b中实现,所以你可以使用上面的解决方案,无需任何担心。 – gnovice 2011-01-31 17:33:15