在Matlab中进行就地快速排序 [英] In-Place Quicksort in matlab

问题描述

我在matlab中编写了一个小型quicksort实现，以对一些自定义数据进行排序.因为我正在对一个细胞数组进行排序，并且需要排序顺序的索引，并且不想重组细胞数组本身，所以我需要自己的实现(也许有一个可行的方法，但是我没有找到它)

I wrote a small quicksort implementation in matlab to sort some custom data. Because I am sorting a cell-array and I need the indexes of the sort-order and do not want to restructure the cell-array itself I need my own implementation (maybe there is one available that works, but I did not find it).

我当前的实现方式是将分区划分为left和right数组，然后将这些数组传递给递归调用.因为我不知道left和right的大小，所以我只是将它们在一个循环中增长，我知道这在matlab中非常慢.

My current implementation works by partitioning into a left and right array and then passing these arrays to the recursive call. Because I do not know the size of left and and right I just grow them inside a loop which I know is horribly slow in matlab.

我知道您可以进行就地快速排序，但是警告我永远不要修改传递给函数的变量的内容，因为按引用调用的实现方式未达到人们期望的在matlab中的方式(或者被告知) .这样对吗?就地快速排序是否可以在Matlab中按预期工作，还是我需要照顾一些东西?您还会对实现这种事情有什么其他提示?

I know you can do an in place quicksort, but I was warned about never modifying the content of variables passed into a function, because call by reference is not implemented the way one would expect in matlab (or so I was told). Is this correct? Would an in-place quicksort work as expected in matlab or is there something I need to take care of? What other hints would you have for implementing this kind of thing?

推荐答案

在用户M代码中对复杂数据实施排序可能会由于M级操作的开销而导致性能方面的损失. Matlab的内建函数.尝试根据Matlab现有的矢量化函数来重构操作.

Implementing a sort on complex data in user M-code is probably going to be a loss in terms of performance due to the overhead of M-level operations compared to Matlab's builtins. Try to reframe the operation in terms of Matlab's existing vectorized functions.

根据您的评论，听起来您正在对单元格结构内的单值键进行排序.通过将排序键提取到原始数字数组并在其上调用内置的sort，可能会获得良好的加速效果.

Based on your comment, it sounds like you're sorting on a single-value key that's inside the structs in the cells. You can probably get a good speedup by extracting the sort key to a primitive numeric array and calling the builtin sort on that.

%// 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个单元格中的所有m个键值提取到n-m数组中，并按优先级降序排列列，并在其上使用sortrows.

If you're sorting on multiple field values, extract all the m key values from the n cells to an n-by-m array, with columns in descending order of precedence, and use sortrows on it.

%// 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代码操作的固定成本(尤其是在非原始代码上)可能是致命的.

One of the keys to performance in Matlab is to get your data in primitive arrays, and use vectorized operations on those primitive arrays. Matlab code that looks like C++ STL code with algorithms and references to comparison functions and the like will often be slow; even if your code is good in O(n) complexity terms, the fixed cost of user-level M-code operations, especially on non-primitives, can be a killer.

此外，如果您的结构是同构的(即它们都具有相同的字段集)，则可以将它们直接存储在结构数组中，而不是结构的单元格数组中，它将更加紧凑.如果您可以进行更广泛的重新设计，则将数据结构重新排列为平面组织的"-您拥有数组的结构，将所有字段的第i个元素读取为记录，而不是标量字段的结构数组-可能是一个不错的效率胜利.这些重组中的任何一种都会使构建排序键数组的成本降低.

Also, if your structs are homogeneous (that is, they all have the same set of fields), you can store them directly in a struct array instead of a cell array of structs, and it will be more compact. If you can do more extensive redesign, rearranging your data structures to be "planar-organized" - where you have a struct of arrays, reading across the ith elemnt of all the fields as a record, instead of an array of structs of scalar fields - could be a good efficiency win. Either of these reorganizations would make constructing the sort key array cheaper.

这篇关于在Matlab中进行就地快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！