Sortrows function and real-time systems
显示 更早的评论
I would like to understand if sortrows is suited for real-time systems.
Is it based on a recursive algorithm?
采纳的回答
Walter Roberson
2020-5-20
sortrows() is based on quicksort.
quicksort() does not require that the comparison operation be literally x(idx1) < x(idx2) : quicksort as an algorithm just says that at a particular point, you invoke a comparison function that tells you the relative order of two entries given their index. The comparison operator can be, for example,
temp = sign(x(idx1, :) - x(idx2, :)) .* sort_direction_hints;
if ~any(temp)
sort_flag = 0;
else
sort_flag = temp(find(temp),1); %first non-zero result
end
sort_flag of -1 means that row idx1 is "before" row idx2. sort_flag of 0 means that they are the same for sorting purposes. sort_flag if +1 means that row idx1 is "after" row idx2.
sort_direction_hints is a vector of values, one per column. -1 indicates descending sort; 0 indicates column to be ignored for sorting; +1 indicates ascending sort.
The construction of temp takes constant time proportional to the number of columns. The ~any(temp) could potentially take variable time that is at most proportional to the number of columns. The test could be rewritten to be constant time proportional to the number of columns.
The find() takes variable time that is at most proportional to the number of columns (and could be rewritten to constant time proportional to the number of columns.
The overall result is variable but proportional to the number of columns.
Ameer's 
would become 
where m is the number of columns.
would become where m is the number of columns.This is worst case; an actual dedicated implementation could reduce the constants of proportionality .
更多回答（1 个）
Ameer Hamza
2020-5-20
编辑：Ameer Hamza
2020-5-20
Although the documentation does not mention the complexity of the algorithm. However, since the lower-bound on sorting have the complexity of 
, and the experimental results also seem to confirm that
, and the experimental results also seem to confirm thatn_rows = round(linspace(1000, 1000000, 50));
t = zeros(1, numel(n_rows));
for i=1:numel(n_rows)
M = rand(n_rows(i), 3);
t(i) = timeit(@() sortrows(M));
end
%%
x = n_rows;
y = t;
figure;
plot(x, y, '+');
xlabel('Num. Rows');
ylabel('Execution Time');
The dependance on number of columns also seems to be linear
n_rows = 10:10:500;
t = zeros(1, numel(n_rows));
for i=1:numel(n_rows)
M = rand(10000, n_rows(i));
t(i) = timeit(@() sortrows(M));
end
%%
x = n_rows;
y = t;
figure;
plot(x, y, '+');
xlabel('Num. Columns');
ylabel('Execution Time');
So now it depends on your application, whether this complexity is acceptable. However, its performance already seems to be optimal, and you cannot gain much speed by using some other algorithm.
类别
在 帮助中心 和 File Exchange 中查找有关 Startup and Shutdown 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
