Re: Christmas gift - new game
Rob Craig wrote:
>If the elements that you are sorting are all integers within
>a known range of possible values, this could be a job for
>"bucket sort". See demo\allsorts.ex, or post the problem
>to this list and start another performance competition!
>To sort 163840 integers on my Pentium -150 MHz, I get:
> great sort 2.87 sec.
> shell sort 4.64 sec.
> bucket sort 0.54 sec.
>(I set constant MAX = 200000 in allsorts.ex)
It is not that simple... in fact, I'm sorting strings. But I'm not maintaining
each string as an element of a sequence. Instead, the sequence to be sorted
contains 'pointers' to positions in another sequence, containing a single
string.
For example:
String= "foobar"
Order={1,2,3,4,5,6} -- A pointer to each position in String
1 points to "foobar", 2 points to "oobarf", 3 points to "obarfo" and so on
(when the end of String is reached, you go back to the beggining). The order
of
the rotations (in fact what I'm doing is rotating String) after sorting would
be:
arfoob -- starting at position 5
barfoo -- 4
foobar -- 1
obarfo -- 3
oobarf -- 2
rfooba -- 6
So, after sorting, Order would be {5,4,1,3,2,6} . Hope my explanation isn't
too confusing :)
It doesn't look so difficult. It's simple to use custom_sort() to do the job,
but it's faster to use a method designed for this kind of situation, specially
when you're dealing with several thousand bytes. BTW, yesterday I was able to
speed the program up by about 25% (now it takes 6.8 seconds to sort
library.doc).
I'll probably post it next month to see if someone is able to make it even
faster.
Anyway, I think it's not *so* slow now. If you want to distribute the
compressed
file, the time you have to wait is probably worth the better compression
ratio.
Decompressing is fast, the users won't have to wait so much.
Regards,
Davi Figueiredo
davitf at usa.net
____________________________________________________________________
Get free e-mail and a permanent address at http://www.amexmail.com/?A=1
|
Not Categorized, Please Help
|
|
