Wednesday, February 13, 2008

Scheme For Enlightenment Part Fifteen - Time Is Change

So this change counting thing turns out to be a benchmark, complete with times run under various hardware on LispMe, MIT Scheme and PocketC (which is not Scheme, or really even C, but runs on a Palm). So i ran it on a 2.8 GHz Pentium 4 under Guile 1.8, and it took 0.156 seconds. Startup for Guile is around 0.028 seconds, so the run time was around 0.128 seconds, which doesn't tell me much. This benchmark is way too short for a modern desktop. I already knew that this P4 was faster than any of the hardware listed. I'd like to know how long other programs might take. The run time on the desktop was so short, one can't really extrapolate to other circumstances with much confidence. And i know nothing about what this program does or how it does it. So i ran it on the Handspring Visor Platinum in LispMe. I needed some way to get the time for the benchmark, so i added this code to the script, set the auto-off on the Palm to thirty minutes (1800 seconds) and ran it saying (doit).

(define (doit)
(define tk (current-ticks))
(cc 100 coins)
(ticks-since tk))

I also ran (ticks-per-sec) to find out that my Palm counts time in hundredths of seconds. All this time stuff is LispMe specific, and i can divide by 100 in my head, so i didn't bother having LispMe do that. I should note that the Palm is otherwise useless when running long programs. I don't care that much that my rechargeable batteries are draining a little quicker than usual. There is no A/C adapter, so there are limits to run time. For example, no overnight runs.

Anyway, it returned 26296, which is 262.96 seconds. That makes my Visor faster than a Palm IIIc, which i already knew. It's not as fast as a Palm Tungsten T3, which might be a newer Arm based Palm. That would make sense too. From the desktop timing above, one might expect scripts to run anywhere from 1600 to 2000 times faster on a desktop than on a Palm. That means that even scripts that seem to take no time at all on the desktop may be impractical on the Palm. One second is half an hour.

My original confusion had to do with my expectations and not (yet) reading the manual. I thought that this script made change. It has many of the elements that i'd expected. The cryptic comment says it counts change. It has a list of dollars or coin values. The function takes an amount. It does some list walking, with car and cdr, checking for the end of the list with null?. It subtracts. But what would a function look like that does what i thought this one does?

; count change. How many coins does it take?
(define coins '(50 25 10 5 1))
(define (cc am c)
(if (null? c) 0
(if (< (- am (car c)) 0)
(cc am (cdr c))
(+ 1 (cc (- am (car c)) c)))))

For reference, here's the original:

; count change
(define coins '(50 20 10 5 2 1))
;(define coins '(50 25 10 5 1))
(define (cc am c)
(if (eq? am 0) 1
(if (or (< am 0) (null? c)) 0
(+ (cc (- am (car c)) c)
(cc am (cdr c))))))

They are the same number of lines. Both have two nested if's. They both use car, cdr and null? to walk the list. They both do a bit of the work and call themselves to finish it. They both use addition to count. They both use subtraction to mark that a coin has been used. So how can you tell that it does one thing instead of another? At the moment, it looks like one must step through them to see what each one does.

No comments: