• Subject: Re: Speed query
• From: Geoff Leyland <geoff_leyland@...>
• Date: Thu, 27 Mar 2008 07:43:25 +1300

```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