[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Speed query
- From: "Javier Guerra" <javier@...>
- Date: Mon, 31 Mar 2008 10:41:30 -0500
On Mon, Mar 31, 2008 at 9:30 AM, Gé Weijers <firstname.lastname@example.org> wrote:
> I've attached a small priority queue implementation based on skew
> heaps. It builds and destroys a 100,000 element priority queue in
> less than 3 seconds on my laptop (1.3 seconds on luajit).
now that is fast! (less than 2 secs on my desktop without JIT)
and the code is much, much simpler than the binary heap. i think
mostly because it uses small tables to hold the heap tree, instead of
the old optimization of using an array to fold the tree. that might
be a big gain on C using fixed-size records, but on Lua it's neater,
cleaner and (at least) as fast to use tables instead of integer
'pointers' on an array.
a lovely humbling lesson.