|
|
|
The following page was printed from RemoteCentral.com:
ProntoScript Sort() is "Unstable"
| |
|
Topic: | ProntoScript Sort() is "Unstable" This thread has 8 replies. Displaying all posts. |
|
Post 1 made on Thursday October 7, 2010 at 03:59 |
buzz Super Member |
Joined: Posts: | May 2003 4,382 |
|
|
Now that I have everyone's attention, this is not a bug report.
In the computer science texts a sort routine is thrown into one of two bins: "Stable" or "Unstable".
In this context a "Stable" sort retains the original element order if the keys are equal and an "Unstable" sort does not guarantee that order.
Consider the following unsorted table
11 A 11 B 10 A 10 B 10 C 11 C
An ascending stable sort by the first field would always return:
10 A 10 B 10 C 11 A 11 B 11 C
An ascending unstable sort by the first field might return:
10 C 10 A 10 B 11 A 11 C 11 B
Neither sort is intrinsically better, but it pays to know what you are dealing with -- if this matters in your application.
|
|
Post 2 made on Thursday October 7, 2010 at 12:49 |
Lyndel McGee RC Moderator |
Joined: Posts: | August 2001 12,999 |
|
|
Buzz, can I get some clarification? I presume it's not the ProntoScript Sort(), it is the sort algorithm supported by the Javascript engine Spidermonkey() 1.6R2?
Correct?
|
Lyndel McGee Philips Pronto Addict/Beta Tester
|
|
OP | Post 3 made on Friday October 8, 2010 at 08:01 |
buzz Super Member |
Joined: Posts: | May 2003 4,382 |
|
|
Lyndel,
I was using Array.sort() in the simulator.
I didn't discover this by accident. If the sort was stable, I could use a simpler orderfunc.
This is an interesting optimization challenge. I'm actually ordering the array by timestamp. On the simulator I see lots of equal keys, but on the actual remote I may not see any or many -- for this generation of hardware.
Array.sort() probably uses a variant of quicksort. Given that my array is nearly in order, quicksort is a poor choice. A tweaked variant of a bubble sort would be faster, but this would need to execute at the script level rather than as an intrinsic function. For interpreted languages, using a generalized "big job" intrinsic function often results in faster execution times than using a smarter scripted function.
Along these lines, have you done any time trials comparing passing an inline anonymous function argument vs passing a formal function name in loops?
|
|
Post 4 made on Friday October 8, 2010 at 11:39 |
Lyndel McGee RC Moderator |
Joined: Posts: | August 2001 12,999 |
|
|
I've done a bit of testing but not quite sure what you are asking. Can you give me an example?
Thanks, Lyndel
|
Lyndel McGee Philips Pronto Addict/Beta Tester
|
|
Post 5 made on Friday October 8, 2010 at 15:51 |
Barry Gordon Founding Member |
Joined: Posts: | August 2001 2,157 |
|
|
Quicksort,Bbubblesort, its been years since I heard those terms. I generally used a bubble sort with a decreasing list size as things bubbled out of the arrays unsorted portion. very easy to implement, Quicksort was trickier from an implementation standpoint.
|
|
OP | Post 6 made on Sunday October 10, 2010 at 12:04 |
buzz Super Member |
Joined: Posts: | May 2003 4,382 |
|
|
Lyndel, I was asking about the relative execution efficiency of : Array.sort( function(a,b) { return a-b }); vs function rank( a, b, ){ return( a - b ); } Array.sort( rank );
Last edited by buzz on October 10, 2010 16:37.
|
|
Post 7 made on Sunday October 10, 2010 at 15:45 |
Barry Gordon Founding Member |
Joined: Posts: | August 2001 2,157 |
|
|
oops, better get Lyndel's name right. I had to write it on the blackboard 100 times just to show penance.
|
|
OP | Post 8 made on Sunday October 10, 2010 at 16:38 |
buzz Super Member |
Joined: Posts: | May 2003 4,382 |
|
|
Thanks, I need a syntax checker.
|
|
Post 9 made on Sunday October 10, 2010 at 19:10 |
Lyndel McGee RC Moderator |
Joined: Posts: | August 2001 12,999 |
|
|
On October 10, 2010 at 12:04, buzz said...
Lyndel,
I was asking about the relative execution efficiency of :
Array.sort( function(a,b) { return a-b });
vs
function rank( a, b, ){ return( a - b ); }
Array.sort( rank ); I believe that the performance should be relatively the same between the 2.
|
Lyndel McGee Philips Pronto Addict/Beta Tester
|
|
|
Before you can reply to a message... |
You must first register for a Remote Central user account - it's fast and free! Or, if you already have an account, please login now. |
Please read the following: Unsolicited commercial advertisements are absolutely not permitted on this forum. Other private buy & sell messages should be posted to our Marketplace. For information on how to advertise your service or product click here. Remote Central reserves the right to remove or modify any post that is deemed inappropriate.
|
|