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).
I hope it's of some use.
Gé
On Mar 27, 2008, at 2:50 PM, Geoff Leyland wrote:
On 28/03/2008, at 12:36 AM, Tony Finch wrote:
On 2008年3月26日, Javier Guerra wrote:
but also noted that your speed test of the sort()ed queue just inserts
numbers in the queue, while the heap uses a {key,value} table for each
item... no fair!
You could avoid this by storing all the keys and values in one table
and
the ordering in another, i.e.
pairs[key] = value
index[n] = key
Good idea, but I tried it and it didn't seem to make a significant
difference with lua or luajit.
I also tried changing the entries to { k, v } rather than { key=k,
value=v } figuring I'd swap some hash lookups for index lookups, but
it was slightly slower on lua and only a little faster with luajit,
so I figured it wasn't worth it.
Javier's #self improvement is even better with luajit. I tried going
further by having a manually updated self.size to avoid *all* the
#selfs, but it was no better.
Cheers,
Geoff
--
Gé Weijers
ge@weijers.org