Re: issorted & sortrows

[Jaroslav Hajek]

On Wed, Feb 11, 2009 at 3:37 PM, Jaroslav Hajek <address@hidden> wrote:
> hi,
>
> following the recent optimization of sort, I went ahead and
> implemented issorted and optimized sortrows:
>
> Summary of changes:
> issorted is now supported (built-in). issorted(..., 'rows') also
> works, except for sparse matrices.
> The check uses no temporary arrays and is quite fast (inlined versions
> in octave_sort).
>
> sortrows is still an m-file. The old O(M*N*log(M) + M*N^2) algorithm
> has been simply optimized to be O(M*N*log(M)).
> The homogeneous case (whole matrix is sorted or all columns
> identically oriented), is forwarded to a built-in implementation
> (__sortrows_idx__) that uses an even more efficient breadth-first
> tree-traversing algorithm, which I think is O(M*(N+log(M))).
>
> To get an idea of the speed-up, here's a short benchmark:
>
> # purely random array
> n = 5e5;
> a = randn (n, 10);
> tic; b = sortrows (a); toc
>
> # partially ordered array
> for k = 1:100
>  i = ceil (rand * (n-1));
>  # swap randomly
>  b = [b(j+1:end,:); b(1:j,:)];
> endfor
> tic; a = sortrows (b); toc
>
> with a recent tip, I got:
> Elapsed time is 1.62271 seconds.
> Elapsed time is 1.62623 seconds.
>
> whereas with the new tip, I get:
>
> Elapsed time is 0.194896 seconds.
> Elapsed time is 0.084264 seconds.
>
> i.e. speed-ups by factors 8.3 and 19.3.
>
> once again I'm wondering whether Matlab has an even better algorithm...
>

OK I just realized this benchmark is not really much realistic, as the
first column is almost enough to determine ordering.
Rounding to just 100 random values is somewhat better:

# purely random array
n = 5e5;
a = round (100*rand (n, 10));
tic; b = sortrows (a); toc

# partially ordered array
for k = 1:100
  i = ceil (rand * (n-1));
  # swap randomly
  b = [b(j+1:end,:); b(1:j,:)];
endfor
tic; a = sortrows (b); toc

and the times:

Elapsed time is 1.42739 seconds.
Elapsed time is 1.41714 seconds.

vs.

Elapsed time is 0.273507 seconds.
Elapsed time is 0.114233 seconds.

here, speedups are slightly smaller but still significant.

cheers

-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz