matlab中的就地Quicksort

Question

我在matlab中編寫了一個小的快速排序實現來排序一些自定義數據。因爲我正在對一個單元格數組進行排序，並且我需要排序順序的索引，並且不想重構單元格數組本身，所以我需要自己的實現（也許有一個可用的工作，但我沒有找到它） 。

我目前的實現通過分區爲left和right數組，然後將這些數組傳遞給遞歸調用。因爲我不知道left和right的大小，我只是在一個循環內生長它們，我知道它在matlab中速度很慢。

我知道你可以做一個適當的快速排序，但我被警告說永遠不要修改傳遞給函數的變量的內容，因爲引用調用並沒有按照人們期望的方式實現（或者我被告知）。它是否正確？在matlab中就地快速排序會如預期的那樣工作，還是有我需要照顧的地方？你會有什麼其他暗示來實現這種事情？

Answer 1

實現對用戶的M代碼的複雜數據排序可能將是在性能方面損失，由於M-級操作的開銷相比，Matlab的內置命令。嘗試用Matlab現有的矢量化函數來重新構建操作。

基於您的評論，它聽起來就像你整理一個單值密鑰會在細胞內部結構。您可以通過將排序鍵提取到原始數值數組並調用內建的sort來獲得很好的加速。

%// An example cell array of structs that I think looks like your input 
c = num2cell(struct('foo',{'a','b','c','d'}, 'bar',{6 1 3 2})) 
%// Let's say the "bar" field is what you want to sort on. 
key = cellfun(@(s)s.bar, c) %// Extract the sort key using cellfun 
[sortedKey,ix] = sort(key) %// Sort on just the key using fast numeric sort() builtin 
sortedC = c(ix); %// ix is a reordering index in to c; apply the sort using a single indexing operation 
reordering = cellfun(@(s)s.foo, sortedC) %// for human readability of results 

如果您在多個域值排序，提取所有從n細胞米鍵值的n乘米陣列，其中列按降序優先級順序，並在其上使用sortrows。

%// Multi-key sort 
keyCols = {'bar','baz'}; 
key = NaN(numel(c), numel(keyCols)); 
for i = 1:numel(keyCols) 
    keyCol = keyCols{i}; 
    key(:,i) = cellfun(@(s)s.(keyCol), c); 
end 
[sortedKey,ix] = sortrows(key); 
sortedC = c(ix); 
reordering = cellfun(@(s)s.foo, sortedC) 

在Matlab中性能的關鍵之一是讓你的數據在原始數組中，並在這些原始數組上使用矢量化操作。看起來像C++ STL代碼的Matlab代碼以及對比較函數等的引用通常會很慢;即使您的代碼在O（n）複雜性方面表現良好，用戶級別M代碼操作的固定成本（特別是在非原始代碼上）也可能成爲殺手鐗。另外，如果你的結構是同類的（也就是說，它們都具有相同的字段集合），你可以直接將它們存儲在一個結構數組中，而不是結構的單元數組，它會更加緊湊。如果您可以進行更廣泛的重新設計，則將數據結構重新排列爲「平面組織」 - 即您擁有數組結構的地方，將所有字段的第i個元素作爲記錄讀取，而不是標量字段結構數組 - 可能是一個很好的效率勝利。這些重組中的任何一個都會使構建排序鍵陣列更便宜。

Answer 2

在這篇文章中，我只解釋MATLAB函數調用約定，而不是在討論快速排序算法的實現。

當調用函數，MATLAB通行證內置數據類型by-value，以及這種論點所做的任何更改都不會在函數外可見。

function y = myFunc(x) 
    x = x .* 2;   %# pass-by-value, changes only visible inside function 
    y = x; 
end 

對於大數據，這可能是低效的，特別是如果它們沒有在函數內部修改。因此，MATLAB在內部實現了一個copy-on-write mechanism：例如，當一個向量被複制時，只有一些元數據被複制，而數據本身在向量的兩個副本之間共享。只有當它們中的一個被修改時，數據實際上是重複的。

function y = myFunc(x) 
    %# x was never changed, thus passed-by-reference avoiding making a copy 
    y = x .* 2; 
end 

注意，對於細胞陣列和結構，僅將細胞/字段改性傳遞按值（這是因爲細胞/字段在內部分開存儲），這使得複製爲這樣的數據結構更有效。欲瞭解更多信息，請閱讀blog post。

此外，版本R2007和向上（我認爲）上的數據檢測in-place operations和優化這樣的情況。

function x = myFunc(x) 
    x = x.*2; 
end 

顯然調用這樣功能時，LHS必須是相同的RHS（x = myFunc(x);）。此外，爲了利用這種優化，就地功能必須從另一個功能內部調用。

在MEX-功能，雖然它有可能改變輸入變量不進行復印，它不正式支持，可能會產生意想不到的結果......

對於user-defined types（OOP），MATLAB推出的value object vs. handle object的concept支持reference semantics。