Re: Speed query

[ge@...]

The skew heap is surprisingly simple and fast, especially considering its
simplicity. I also tried another simple priority queue algorithm, the
two-pass pairing heap, in Lua, but it's a little slower on random input
(though faster on ordered sequences), and the code is larger.

There are a number of data structures that are good examples of a
combination of elegance and (relative) speed. The skew heap is one, and
another one I like to use is the 'treap' or tree-ordered heap, which is a
randomized search tree with O(log n) expected access time. It's far
simpler to implement than red-black trees or splay trees, and has similar
performance, assuming you have a fast pseudo-random generator (e.g.
math.random).

Gé

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