[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: benchmarks - sort
From: |
David Bateman |
Subject: |
Re: benchmarks - sort |
Date: |
Mon, 19 Jan 2004 04:40:06 -0600 |
User-agent: |
Mutt/1.4.1i |
Alois,
Ok, ignored... In any case I've looked further into the problem over the
weekend and found that the sign issues in IEEE 754 comparison can be treated
more elegantly. Look at the webpage
http://www.stereopsis.com/radix.html
Basically, I've taken his code and rewritten it for doubles, called it
mysort5 (my 5th attempt at getting something faster), and now I get the
benchmarks as follows
octave:2> a=randn(1000000,1); tic; b = mysort5(a); toc
ans = 0.48168
octave:4> a=randn(1000000,1); tic; b = sort(a); toc
ans = 3.4093
and under Matlab R12
I ran the code twice in all cases and took the second result to allow for
issues of dynamically loading the modules, etc
>> a=randn(1000000,1); tic; b = sort(a); toc
elapsed_time =
0.5301
So the code I have is basically the same speed as Matlab, correctly
sorts the NaN's and sorts equal values respecting the order as does
Matlab (something I don't believe the current octave code does). I
suspect that they use the same algorithm. The webpage above also
suggests using SSE prefetch instructions to achieve 25% better again,
however I'm not sure I can do that and remain easily compatiable
between platforms.
Now the question becomes one of how to treat the complex sorts. I
could easily sort on the absolute values, but this doesn't respect the
ordering of values with the same magnitude by there phase as matlab
does. What I suspect Matlab does is to convert the complex values to
magnitude and phase with the magnitude being more significant and then
do a radix sort on this. However, this will be much slower than the
double sort, as I'll have to create 12 histograms and not 6 as at
present, and I'll then have to make 12 passes through the data and not
6 to order the data correctly. Sorting only on the absolute value
without respecting this phase condition should be only twice as slow
as the double sort. This would explain why the sort of complex values
is roughly 20 times slower on Matlab.
Should I aim for exact Matlab compatiability in the sort algorithm, or
"good enough" and lightning fast for the sorting of complex values. It
should be noted that I don't think octave respects this sorting condition
at the moment in any case.
If you want to look at my code, I'll send it seperately, as its not
quite ready for review yet..
Cheers
David
According to Schloegl Alois <address@hidden> (on 01/18/04):
>
>
> My previous mail was not ready to go.
> Please, ignore the last sentence, it was not intended.
>
>
> I wanted to conclude that:
> - the algorithm should be of order O(n.log(n))
> here a different algorithm might be needed
> - and the comparison operator should be as fast and simple as possible
> here the 2-step approach as outlined in the previous mail could help.
>
>
>
> Alois
>
>
>
>
>
>
>
>
>
>
>
--
David Bateman address@hidden
Motorola CRM +33 1 69 35 48 04 (Ph)
Parc Les Algorithmes, Commune de St Aubin +33 1 69 35 77 01 (Fax)
91193 Gif-Sur-Yvette FRANCE
The information contained in this communication has been classified as:
[x] General Business Information
[ ] Motorola Internal Use Only
[ ] Motorola Confidential Proprietary
RE: benchmarks - sort, THOMAS Paul Richard, 2004/01/22