lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Mon, Mar 31, 2008 at 9:30 AM, Gé Weijers <> 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.