| Interesting property of sort [message #53994] |
Wed, 16 May 2007 05:41  |
cmancone
Messages: 30
Registered: May 2007
|
Member |
|
|
while attempting to build a faster star matching algorithm, I
"discovered" an interesting property of sort - or, an interesting use
for it. Of course, you guys have all probably seen this before
anyway, but I thought I would share it because it can be very useful.
Essentially, I found the easy way to make a sort lookup table. So,
let's say you have the array:
test = [5,4,1,3,2]
and you sort it:
sortindex = sort(test)
sorted = test[sortindex]
now, what if you want to know where the 5 (or any other number) ended
up in the sorted array? It turns out that you can make a lookup table
by simply sorting sortindex.
lookup = sort(sortindex)
so, if you wanted to know where the first element of test ended up in
the sorted list, you would say:
print,lookup[0]
; prints "4"
print,sorted[lookup[0]]
; prints "5"
In retrospect, I suppose this result isn't suprising, and probably
should have been immediately obvious. Still, I thought I'd share.
|
|
|
|
| Re: Interesting property of sort [message #54053 is a reply to message #53994] |
Thu, 17 May 2007 10:55  |
cmancone
Messages: 30
Registered: May 2007
|
Member |
|
|
That is a very good point. Actually, I should have realized that
myself. Although my machine is a linux box, my machine is also a very
old linux box. I often ssh into other computers on my network to
steal their unused processor cycles (shh!!! don't tell anyone). My
favorite is my advisor's - he's got a very nice mac with a dual core
G5. It's very nice to be able to ssh into his computer and get an
instant 5x speed up.
p.s. I'm not actually stealing processor cycles. My advisor is well
aware that I do this :)
On May 16, 1:01 pm, David Fanning <n...@dfanning.com> wrote:
> cmanc...@ufl.edu writes:
>> I guess I really just didn't have
>> to worry, since I'm on linux.
>
> I would say you don't have to worry if the software
> is running on YOUR machine. You will have to worry
> a great deal if it ever sneaks onto another machine.
>
> Cheers,
>
> David
>
> P.S. People make a BIG mistake thinking they will be
> the only ones to run their software, no matter how
> badly the software is written. I'm looking at a piece
> of software right now that no one imagined would be
> running on MY machine. :-)
>
> --
> David Fanning, Ph.D.
> Fanning Software Consulting, Inc.
> Coyote's Guide to IDL Programming:http://www.dfanning.com/
> Sepore ma de ni thui. ("Perhaps thou speakest truth.")
|
|
|
|
| Re: Interesting property of sort [message #54082 is a reply to message #53994] |
Wed, 16 May 2007 10:01 |
David Fanning
Messages: 11724
Registered: August 2001
|
Senior Member |
|
|
cmancone@ufl.edu writes:
> I guess I really just didn't have
> to worry, since I'm on linux.
I would say you don't have to worry if the software
is running on YOUR machine. You will have to worry
a great deal if it ever sneaks onto another machine.
Cheers,
David
P.S. People make a BIG mistake thinking they will be
the only ones to run their software, no matter how
badly the software is written. I'm looking at a piece
of software right now that no one imagined would be
running on MY machine. :-)
--
David Fanning, Ph.D.
Fanning Software Consulting, Inc.
Coyote's Guide to IDL Programming: http://www.dfanning.com/
Sepore ma de ni thui. ("Perhaps thou speakest truth.")
|
|
|
|
| Re: Interesting property of sort [message #54083 is a reply to message #53994] |
Wed, 16 May 2007 09:52 |
cmancone
Messages: 30
Registered: May 2007
|
Member |
|
|
Interesting. That explains a lot. I had checked the results of my
sort to see whether or not it maintained order for equal value points,
and I didn't see any loss of order. When it was suggested to use
bsort to maintain the order, I just assumed that sort happened to get
it right for the things I checked. I guess I really just didn't have
to worry, since I'm on linux.
On May 16, 11:55 am, "wlands...@jhu.edu" <wlands...@gmail.com> wrote:
>> Humm. Well, I haven't looked at it in a long time.
>> Looks to me like BSORT uses the IDL SORT command to
>> get the initial cut. (And I have NO idea what algorithm
>> is used for that. It is the standard OS SORT routine,
>> I'm sure.)
>
> That's right, the IDL SORT uses the sort algorithm of the OS, so the
> way it treats equal values depends on the OS. From previous
> discussions here, I believe that most Linux systems preserve order for
> equal values, but Windows and Mac OSX do not. I've been tempted to
> update bsort.pro to just call SORT if the user is on the "right" OS,
> but that sort ( pun intended) of coding is difficult to maintain. --
> Wayne
|
|
|
|
| Re: Interesting property of sort [message #54084 is a reply to message #53994] |
Wed, 16 May 2007 08:55 |
wlandsman@jhu.edu
Messages: 12
Registered: September 2006
|
Junior Member |
|
|
> Humm. Well, I haven't looked at it in a long time.
> Looks to me like BSORT uses the IDL SORT command to
> get the initial cut. (And I have NO idea what algorithm
> is used for that. It is the standard OS SORT routine,
> I'm sure.)
>
That's right, the IDL SORT uses the sort algorithm of the OS, so the
way it treats equal values depends on the OS. From previous
discussions here, I believe that most Linux systems preserve order for
equal values, but Windows and Mac OSX do not. I've been tempted to
update bsort.pro to just call SORT if the user is on the "right" OS,
but that sort ( pun intended) of coding is difficult to maintain. --
Wayne
|
|
|
|
| Re: Interesting property of sort [message #54085 is a reply to message #53994] |
Wed, 16 May 2007 07:37 |
David Fanning
Messages: 11724
Registered: August 2001
|
Senior Member |
|
|
cmancone@ufl.edu writes:
> Ahhh... Bsort = bubble sort (duh!). I glanced at the code for bsort
> real fast, but I didn't look in depth. I thought it used the built in
> IDL sort routine and then added some code to force it to keep stuff in
> the proper order. I didn't realize it's a whole new implementation of
> a bubble sort. Do you happen to know what type of sort the built in
> idl sort routine implements?
Humm. Well, I haven't looked at it in a long time.
Looks to me like BSORT uses the IDL SORT command to
get the initial cut. (And I have NO idea what algorithm
is used for that. It is the standard OS SORT routine,
I'm sure.) Then, the equal "clumps" are processed to
put the values in the right order.
It looks like it uses a WHERE and SHIFT to find the
clumps of equal values. So there would be *some*
additional overhead. I guess it will depend on how
many overlaps you have.
If you were sorting integers, it might be faster to
use some kind of HISTOGRAM method, but this looks fine
to me as a general purpose sort of any data type.
Cheers,
David
--
David Fanning, Ph.D.
Fanning Software Consulting, Inc.
Coyote's Guide to IDL Programming: http://www.dfanning.com/
Sepore ma de ni thui. ("Perhaps thou speakest truth.")
|
|
|
|
| Re: Interesting property of sort [message #54086 is a reply to message #53994] |
Wed, 16 May 2007 07:23 |
cmancone
Messages: 30
Registered: May 2007
|
Member |
|
|
Ahhh... Bsort = bubble sort (duh!). I glanced at the code for bsort
real fast, but I didn't look in depth. I thought it used the built in
IDL sort routine and then added some code to force it to keep stuff in
the proper order. I didn't realize it's a whole new implementation of
a bubble sort. Do you happen to know what type of sort the built in
idl sort routine implements?
On May 16, 9:50 am, David Fanning <n...@dfanning.com> wrote:
> cmanc...@ufl.edu writes:
>> excellent point, thanks for the tip. Out of curiosity, does bsort add
>> a lot of overhead compared to a regular sort?
>
> I don't know. I rarely sort a million things. :-)
>
> My experience with NASA Astronomy routines is that
> there are fewer IDL programs any better. This is a
> bubble sort. Not the fastest sorting algorithm in
> the world, probably. But at least you know it is
> accurate.
>
> Cheers,
>
> David
> --
> David Fanning, Ph.D.
> Fanning Software Consulting, Inc.
> Coyote's Guide to IDL Programming:http://www.dfanning.com/
> Sepore ma de ni thui. ("Perhaps thou speakest truth.")
|
|
|
|
| Re: Interesting property of sort [message #54088 is a reply to message #53994] |
Wed, 16 May 2007 06:50 |
David Fanning
Messages: 11724
Registered: August 2001
|
Senior Member |
|
|
cmancone@ufl.edu writes:
> excellent point, thanks for the tip. Out of curiosity, does bsort add
> a lot of overhead compared to a regular sort?
I don't know. I rarely sort a million things. :-)
My experience with NASA Astronomy routines is that
there are fewer IDL programs any better. This is a
bubble sort. Not the fastest sorting algorithm in
the world, probably. But at least you know it is
accurate.
Cheers,
David
--
David Fanning, Ph.D.
Fanning Software Consulting, Inc.
Coyote's Guide to IDL Programming: http://www.dfanning.com/
Sepore ma de ni thui. ("Perhaps thou speakest truth.")
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
