Быстрый метод MATLAB для изменения порядка столбцов с помощью sortrows

Question

У меня есть данные (числовые M x N, n> 2), которые сортируются по первому столбцу, а затем по второму. Кто-нибудь знает эффективный алгоритм, который преобразует данные в сортировку по второму столбцу, а затем по первому? Очевидно, что sortrows (data, [2,1]) делает свое дело, но я ищу то, что использует существующую структуру входных данных для большей скорости, так как M очень велико.

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

Answer 1

На основании справочной документации для MATLAB R2010b функция SORTROWS использует стабильную версию быстрой сортировки .Поскольку стабильные алгоритмы сортировки «поддерживают относительный порядок записей с одинаковыми ключами» , вы можете достичь желаемого, просто прибегнув к уже отсортированным данным по второму столбцу:

data = sortrows(data,2);

Этот результат будет поддерживать относительный порядок элементов в первом столбце, так что данные будут отсортированы сначала по второму столбцу, а затем по первому столбцу.

Answer 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

Answer 3

Я продолжал стучать в это, но не мог получить это быстрее, чем метод 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), пожалуйста, не стесняйтесь добавлять.