lua-users home
lua-l archive

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

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

> once upon a time,
> (, 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)


binary heap: 12.96 s
skew heap: 13.36 s
sorted queue: 68.30

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