Быстрая сортировка на месте в matlab

Question

Я написал небольшую реализацию быстрой сортировки в Matlab для сортировки некоторых пользовательских данных.Поскольку я сортирую массив ячеек, и мне нужны индексы порядка сортировки, и я не хочу реструктурировать сам массив я, мне нужна собственная реализация (возможно, есть такая, которая работает, но я ее не нашел).

Моя текущая реализация работает путем разбиения на массивы left и right и последующей передачи этих массивов в рекурсивный вызов.Потому что я не знаю размера left и и right, я просто выращиваю их в цикле, который, как я знаю, ужасно медленен в matlab.был предупрежден о том, что никогда не следует изменять содержимое переменных, передаваемых в функцию, потому что вызов по ссылке не реализован так, как можно было бы ожидать в matlab (или так мне сказали).Это правильно?Будет ли работать быстрая сортировка на месте, как и ожидалось в Matlab, или мне нужно позаботиться о чем-то?Какие еще советы вы бы дали для реализации такого рода вещей?

Answer 1

Реализация сортировки сложных данных в пользовательском М-коде, вероятно, приведет к потере производительности из-за накладных расходов на операции уровня М по сравнению со встроенными в 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

Если вы сортируете по нескольким значениям поля, извлеките все mзначения ключа из n ячеек в массив размером n на m со столбцами в порядке убывания приоритета и использование 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 - этополучить ваши данные в примитивных массивах и использовать векторизованные операции с этими примитивными массивами.Код Matlab, который выглядит как код C ++ STL с алгоритмами и ссылками на функции сравнения и тому подобное, часто будет медленным;даже если ваш код хорош с точки зрения сложности O (n), фиксированная стоимость операций М-кода пользовательского уровня, особенно над не примитивами, может быть убийственной.

Кроме того, если ваши структуры однородны(то есть все они имеют одинаковый набор полей), вы можете хранить их непосредственно в массиве структур вместо массива структур ячеек, и он будет более компактным.Если вы можете сделать более обширный редизайн, переставьте ваши структуры данных, чтобы они были «планарно организованы» - где у вас есть структура массивов, считывающая через i-й элемент всех полей как запись, вместо массива структур скалярных полей.- может быть хорошая победа эффективности.Любая из этих реорганизаций удешевит создание массива ключей сортировки.

Answer 2

В этом посте я только объясняю соглашение о вызове функций MATLAB и не обсуждаю реализацию алгоритма быстрой сортировки.

При вызове функций MATLAB передает встроенные типы данных по значению, и любые изменения, внесенные в такие аргументы, не видны вне функции.

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

Это может быть неэффективно для больших данных, особенно если они не модифицируются внутри функций.Поэтому MATLAB внутренне реализует механизм копирования при записи : например, когда вектор копируется, копируются только некоторые метаданные, а сами данные совместно используются двумя копиями вектора.И только когда один из них изменен, данные фактически дублируются.

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

Обратите внимание, что для массивов и структур ячеек только измененные ячейки / поля передаются по значению (этоэто потому, что ячейки / поля хранятся отдельно), что делает копирование более эффективным для таких структур данных.Для получения дополнительной информации читайте это сообщение в блоге .

Кроме того, версии R2007 и выше (я думаю) обнаруживают операции на месте с данными и оптимизируют такие случаи.

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

Очевидно, что при вызове такой функции LHS должен совпадать с RHS (x = myFunc(x);).Также, чтобы воспользоваться этой оптимизацией, функции на месте должны вызываться из другой функции.

В MEX-функциях, хотя можно изменять входные переменные без копирования, это официально не поддерживаетсяи может привести к неожиданным результатам ...

Для пользовательских типов (OOP), MATLAB ввел концепцию объекта значения против объекта дескриптора поддержка ссылочная семантика .