Re: Speed query

[Geoff Leyland <geoff_leyland@...>]

> On 27/03/2008, at 2:39 AM, Roberto Ierusalimschy wrote:
> > > does table.qsort exist?  I can only find table.sort documented.
> >
> > table.sort uses the quicksort algorithm, if that is what you mean.

Thanks.  David had written table.qsort, rather than table.sort, so I  
was wondering.  The note in the reference manual saying it's not a  
stable sort made me suspect as much.

On 27/03/2008, at 5:45 AM, David Given wrote:
> Geoff Leyland wrote:
> > Good question.  I just tested (b) vs a pure lua binary heap and  
> > the binary heap is so much better (the sort version still hasn't  
> > finished) that I think I must have got (b) wrong (does table.qsort  
> > exist?  I can only find table.sort documented.  Which is better  
> > out of table_insert(t, x) and t[#t+1] = x?)
> > If you want to try my heap code I can send it, but I think there's  
> > one in loop that's bound to be better.
>
> That deeply surprises me, but I can hardly argue with results ---  
> so, yes please, I'd love a copy.

But you can - I was being a bit unfair and making the sort version re- 
sort after every insertion, rather than at every transition between  
insertion and removal.  With that changed I think it's fairer.

The test I used is insert X items, remove Y, and repeat Z times.
For X=10,000, y=7,500 and Z=100 (final queue length 250,000), in lua  
the sort is slightly faster.  With luajit the heap is slightly faster.
For X=1,000, y=750 and Z=1,000 (final queue length 250,000) the heap  
is about 10 times faster in both cases.

So I guess the answer is that it depends what you're doing.

Here's the code with the tests.  No guarantees it works :)

Cheers,
Geoff

Attachment: binary_heap-test.lua
Description: Binary data

Attachment: binary_heap.lua
Description: Binary data