HHC MMC Programming challenge inC code - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: HHC MMC Programming challenge inC code (/thread-176088.html) |
HHC MMC Programming challenge inC code - David Hayden - 12-20-2010 The programming challenge at HHC MMX was to write a UserRPL program to sort a list of integers with the odd numbers appearing first and the even numbers appearing second. Entries were scored based on the run-time multiplied by the program size. Just for fun, I wrote a solution in C code. Although this was clearly an invalid entry for the contest, I wanted to see if the huge increase in size would be offset by the increase in speed. The UserRPL programs can be found here. Here are the results. The input lists L10, L100 and L1000 are my own lists of 10, 100, and 1000 random integers. Note that these are not the input lists used by Joe Horn to judge the contest. Size is in bytes and runtime in seconds. Program names are as given in the link above, except that "dh2.c" is my C code implementation.
PROGRAM The C code is more than 100 times bigger than the biggest User RPL solution. For a 10-item list, it runs about 5 to 18 times faster, resulting in a "bytes times seconds" score far worse than any of the other programs. But when the list is 1000 items, it runs more than 100 times faster than the fastest User RPL program, which is itself almost three times faster than the next fastest entry. At 1,000 items, the C code's overall score is a close second place to the Bill Butler's winning program. Note that with a 50G, it's easy to store the C program on an SD card and access it with a small stub program that just recalls and evaluates it.
Here is the C code: #include <hpgcc49.h> Re: HHC MMC Programming challenge inC code - Oliver Unter Ecker - 12-24-2010 David,
Thanks for the interesting read.
Here's my would-be entry: f(v)=v.sort(function(a,b){return(a&1&&!(b&1))?-1:(!(a&1)&&b&1?1:a-b)})
71 bytes.
Easier to read (but slightly larger; and we're sweating bytes hereā¦), it would be written like this: function(v) {
Run-time for a 1000-element vector is 0.035s on my iPhone 3GS.
Run-time for the original 64-element vector from the competition is 0.002s. Score: 0.142
Run-time for a 100,000-element vector (generated in a little over a second) is 5.9s.
The integer vector is created either through this RPL program \<< \-> n \<< [] 1 n START RAND 2E12 * RND 1E12 - + NEXT \>> \>>
or, for higher speed, this equivalent JavaScript program function (n) {
Note, that iPhone and 50g use the same CPU architecture (ARM9), but the iPhone is clocked ~10x faster.
Re: HHC MMC Programming challenge inC code - David Hayden - 12-25-2010 Quote:It's probably using just-in-time compilation. Basically the interpreter compiles blocks of code as it encounters them and caches the results. The next time it encounters that block of code, it can execute the compiled block. This usually results in interpreted code running nearly as fast as compiled code. That's why java applications usually run pretty quickly. Re: HHC MMC Programming challenge inC code - Oliver Unter Ecker - 12-26-2010 David,
You're probably right. SquirrelFish Extreme (Nitro) is the JavaScript engine in Safari and, yes, it's JIT'ed. I don't know if Mobile Safari uses the same engine (the older JavaScriptCore engine had no JIT compiler). Re: HHC MMC Programming challenge inC code - Glenn Shields - 12-26-2010 Hello all, I'm still trying to figure out what is happening in the winning RPL program in the link. They are all amazing, but what is Re: HHC MMC Programming challenge inC code - Thomas Klemm - 12-26-2010
Quote: Try adding a HALT in the code object which is STREAMed:
\<< I\->R SORT DUP SIZE 3. ROT + Now you can SST into that code section as well. The top of the stack keeps track of where the odd numbers are inserted. With each even number inserted this pointer is incremented.
HTH
PS: Just tested this on a HP-48 emulator, but I assume this is similar on the HP-50.
Re: HHC MMC Programming challenge inC code - Glenn Shields - 12-28-2010 Thank you Thomas, that did it - I could follow the ifte process, and the use of that counter to let higher odd numbers "hop over" the accumulated even numbers in the stack. Amazing what these RPL experts can do with the tools available. Regards, Glenn
Re: HHC MMC Programming challenge inC code - Thomas Klemm - 12-28-2010 You might want to compare the programs in message #5 and #6 of this previous Programming Challenge.
Cheers Edited: 28 Dec 2010, 12:08 p.m.
Re: HHC MMC Programming challenge inC code - David Hayden - 12-31-2010 Quote:Glenn, I have submitted an article to Datafile that analyzes all five entries to the programming challenge.
Dave
|