Re: Speed query

[Stefan Sandberg <keffo.sandberg@...>]

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