[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
issorted & sortrows
From: |
Jaroslav Hajek |
Subject: |
issorted & sortrows |
Date: |
Wed, 11 Feb 2009 15:37:12 +0100 |
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...
cheers
--
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz
- issorted & sortrows,
Jaroslav Hajek <=
- issorted & sortrows, John W. Eaton, 2009/02/11
- Re: issorted & sortrows, Jaroslav Hajek, 2009/02/11
- Re: issorted & sortrows, John W. Eaton, 2009/02/11
- Re: issorted & sortrows, Jaroslav Hajek, 2009/02/11
- Re: issorted & sortrows, David Bateman, 2009/02/11
- Re: issorted & sortrows, John W. Eaton, 2009/02/12
- Re: issorted & sortrows, Jaroslav Hajek, 2009/02/12
- Re: issorted & sortrows, John W. Eaton, 2009/02/12
- Re: issorted & sortrows, Jaroslav Hajek, 2009/02/12
- Re: issorted & sortrows, dbateman, 2009/02/12