Is there faster ranking for matrices than double sort()?

I have a uint16 matrix, where I want to determine the rank of each element with respect to its column in sorted form. The sort function doesn't quite do this, but using the second output twice does it. I need to repeat this routine many times in my code, and profiling reveals that it's by far the slowest part. So, I was wondering if there is a faster way to accomplish this (double sort() seems a bit of an overkill for this perhaps).

Here is a MWE:

M = 50;

m = 50;

n = 2000;

A = randi(M,m,n,'uint16'); % generate an example matrix

% Ranking via double sort():

tic;

[~,I] = sort(A,1);

[~,R] = sort(I,1);

toc;

Answer 1

[Bruno Luong]

Not sure it is faster, but on the theorical complexity it is better (single sort).

A = randi(10,5,3)

A = 5×3

10 5 9 9 1 5 9 3 9 8 3 3 1 9 2

[~,I] = sort(A,1);
[m,n] = size(A);
R = zeros(m,n);
R(I+(0:n-1)*m) = repmat((1:m)',1,n)

R = 5×3

5 4 4 3 1 3 4 2 5 2 3 2 1 5 1

[Marin Genov]

Thanks! I will give it a try and report back with some times.

[Bruno Luong]

Might be a for-loop is faster, rather than using the last startement of linear indexing

for j=1:n
    R(I(:,j),j) = 1:m;
end

[Bruno Luong]

There are three methods, the timing might varies according to your HW and version

A = randi(10,10000,1000);
[~,I] = sort(A,1);
[m,n] = size(A);

% double sort
tic
[~,R] = sort(I,1);
toc

Elapsed time is 0.225407 seconds.

% reverse linear indexing
tic
R = zeros(m,n);
R(I+(0:n-1)*m) = repmat((1:m)',1,n);
toc

Elapsed time is 0.127484 seconds.

% reverse for-loop
tic
R = zeros(m,n);
r = 1:m;
for j=1:n
    R(I(:,j),j) = r;
end
toc

Elapsed time is 0.072377 seconds.

% accumarray
tic;
R=accumarray(reshape(I+(0:n-1)*m,[],1),repmat((1:m)',n,1),[m*n,1]); % EDIT BUG FIX
R=reshape(R,m,n);
toc

Elapsed time is 0.127192 seconds.

[Marin Genov]

For A = randi(10,10000,1000), which is 'double',I am getting in terms of performance the same ranking of methods as you do (consistently over multiple executions), but for A = randi(50,50,20000,'uint16') (I added an extra zero to 2000 b/c the times were very small) the accumaray method, while still being the fastest for me, is followed by reverse linear indexing, then double sort, and only then reverse for-loop (also consistently over several executions).

[Marin Genov]

Dear @Bruno Luong: the accumarray method appears to be producing a different result than the other three methods (whose outputs all agree). Could you please have a second look at it?

[Bruno Luong]

Ops good catch. I edit the code can you please check it?

[Marin Genov]

@Bruno Luong: Just checked the new version, it's still producing a different output.

[Bruno Luong]

Are you sure? it looks fine to me for toy example

A = randi(10,5,3);
[~,I] = sort(A,1);
[m,n] = size(A);
% double sort
[~,R] = sort(I,1)

R = 5×3

1 4 5 3 1 1 4 3 2 5 2 3 2 5 4

% accumarray
R=accumarray(reshape(I+(0:n-1)*m,[],1),repmat((1:m)',n,1),[m*n,1]); % EDIT BUG FIX
R=reshape(R,m,n)

R = 5×3

1 4 5 3 1 1 4 3 2 5 2 3 2 5 4

[Marin Genov]

@Bruno Luong: Apologies, I forgot to rename the R from the new method after copying the code, so MATLAB compared the original output again with the old output that was still in the workspace. Everything seems fine now. Many thanks!