快速MATLAB方法改變與調用sortRows列順序

我有數據（數值的M×N，N> 2）到達由第一列進行排序，然後通過第二個。有誰知道一個有效的算法，將數據轉換爲按第二列排序，然後是第一列？很明顯，sortrows（data，[2,1]）會訣竅，但我正在尋找一些利用輸入數據的現有結構以獲得更高速度的東西，因爲M非常大。快速MATLAB方法改變與調用sortRows列順序

另外，在第一兩列中的數據是已知的整數集合（每個多小於M）。

來源

2011-01-31 MatlabSorter

基於MATLAB R2010b的幫助文檔，函數SORTROWS使用穩定的版本的quicksort。由於stable sorting algorithms "maintain the relative order of records with equal keys"，你可以達到你想要的東西簡單地相對於訴諸已經排序的數據到第二列：

data = sortrows(data,2);

這一結果將保持在第一列元素的相對順序，使得數據將先按第二欄排序，然後按第一欄排序。

來源

2011-01-31 16:30:25 gnovice

好點，這確實加快了一點。查看nx3矩陣的sortrows算法（我在R2007a上），它調用每列的排序。所以避免這種情況會大大提高。 – MatlabSorter 2011-01-31 17:23:27

@MatlabSorter：另外，我剛纔檢查的說明文件R2007a實現調用sortRows的，並且該算法是穩定的，就像R2010b中實現，所以你可以使用上面的解決方案，無需任何擔心。 – gnovice 2011-01-31 17:33:15

由於在第一列中的數據已經排序，則不需要再次進行排序就可以了。這將是稍快，如果你這樣做：

>> 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

來源

2011-01-31 16:31:08

我不停地翻動走在這一點，但不能把它比調用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）請隨時補充。

來源

2011-02-02 22:39:20 MatlabSorter

快速MATLAB方法改變與調用sortRows列順序

回答

相關問題