Re: Speed query

[Gé Weijers <ge@...>]

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é

Attachment: pq.lua
Description: Binary data

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