lua-users home
lua-l archive

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

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


Attachment: binary_heap-test.lua
Description: Binary data

Attachment: binary_heap.lua
Description: Binary data