lua-users home
lua-l archive

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


I was initially quite skeptical, but it's 1,000,000, not 100,000 in the code...


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).

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 Wed, 26 Mar 2008, 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