Re: A very basic thing I don't get

[Geoff Leyland <geoff_leyland@...>]

On 6/10/2011, at 10:41 AM, Javier Guerra Giraldez wrote:

> once upon a time,
> (http://lua-users.org/lists/lua-l/2008-03/msg00498.html), there was a
> thread where a few of us enjoyed optimizing a priority queue;
> comparing a heap structure with a sorted table.
> 
> at first, a binary heap (easy to implement on an array) performed
> really well; but then Gé Weijers surprised everybody with the speed of
> a skew heap (that uses a tree-like structure internally).
> 
> the surprising part is that Gé's code instantiated lots of small
> tables (with named fields!) to create the internal tree, but it still
> was far faster than the supposedly-optimized binary heap (which used a
> single integer-indexed array).
> 
> moral of the story: Lua tables are wicked fast!

I certainly agree with the moral of the story, but I'm not sure that the conclusion regarding binary vs skew heaps holds [1].  In any case, I've dug out the code I wrote at the time and put it here [2], so you can draw your own conclusions (either about heaps or about the quality of my implementations)

Cheers,
Geoff

[1]
Lua:
binary heap: 12.96 s
skew heap: 13.36 s
sorted queue: 68.30

LuaJIT:
binary heap: 2.37 s
skew heap: 4.56 s
sorted queue: 30.70 s

[2] https://github.com/geoffleyland/lua-heaps