Sortrows function and real-time systems

Question

Andrea Comina 2020-5-20

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/527493-sortrows-function-and-real-time-systems

回答： Walter Roberson 2020-5-20

采纳的回答： Walter Roberson

I would like to understand if sortrows is suited for real-time systems.

Is it based on a recursive algorithm?

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Walter Roberson 2020-5-20

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/527493-sortrows-function-and-real-time-systems#answer_434263

在 MATLAB Online 中打开

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.

This is worst case; an actual dedicated implementation could reduce the constants of proportionality .

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Ameer Hamza 2020-5-20

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/527493-sortrows-function-and-real-time-systems#answer_434238

编辑：Ameer Hamza 2020-5-20

在 MATLAB Online 中打开

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

n_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.