I've just been playing about with writing a quick sort, using partition
(to replace one implemented by two "filter"s).
(define (quick-sort l gt?)
(if
(null? l) null
(call-with-values
(lambda () (partition (curry gt? (car l)) (cdr l)))
(lambda (lt-part gt-part)
(append
(quick-sort lt-part gt?)
(cons (car l)
(quick-sort gt-part gt?)))))))
I thought, looking at the shape of it, that I could change my "if" with
a "match", just to give it a different looking syntax.
(define (quick-sort/match l gt?)
(match l
['() null]
[(cons hd tl)
(call-with-values
(lambda () (partition (curry gt? hd) tl))
(lambda (lt-part gt-part)
(append
(quick-sort/match lt-part gt?)
(cons hd (quick-sort/match gt-part gt?)))))]))
I wanted to see how much performance that extra syntactic sugar _cost_
me, so I put the effort into timing the functions.
(let ((big-list (build-list 1000000 (lambda (i) (random 100000000)))))
(time (quick-sort big-list >))
(time (quick-sort/match big-list >))
(void))
Er... that can't be right! The second one (with the match) is coming
out 2% faster!
I've just done another run...
cpu time: 10047 real time: 10046 gc time: 4987
cpu time: 8158 real time: 8175 gc time: 3259
... 20% faster (although that might be some artifact of the timing).
Looking at the expansion of the match, it matches the pair? (or not),
and then, knowing it's a pair uses unsafe-car or unsafe-cdr. The
expansion also has a large number of nested (let-values ...), but I
guess the JIT is making short work of those.
I wouldn't be as confident using an unsafe-... in my code as the match
is (since it gets its confidence from being mechanically correct). In
fact, looking at the original code; I'm making an assumption that l is
a list (a pair or null); which is something else that the match will
help pick up, although I'd probably want an _ clause at the end.
This is truly a surprise to me -- not an engineered situation. Which is
a bit annoying, since now I have to rethink how I implement solutions in
racket, since the language now seems to be capable of behaving as if
it's smarter than I am [although the same could probably be said of BF].
Anyway, enough rambling -- I just wished to heap praise on those of
you whose work has combined to make this so.
Yours, much impressed,
Tim
--
| Tim Brown <tim.br...@timb.net> |
____________________
Racket Users list:
http://lists.racket-lang.org/users
