Re: Fast sorting of FFIzed data
- From: Coda Highland <chighland@xxxxxxxxx>
- To: luajit@xxxxxxxxxxxxx
- Date: Tue, 18 Jun 2013 13:36:49 -0700
On Tue, Jun 18, 2013 at 1:27 PM, Mike Pall <mike-1306@xxxxxxxxxx> wrote:
> Coda Highland wrote:
>> The obvious choice, if you ask me, is to write a sorting routine in
>> Lua. Something that operates in-place may be ideal.
>
> Yes, that would be my recommendation, too. In fact, I've
> considered to rewrite table.sort() in Lua code for LuaJIT 2.1.
>
> The fastest non-in-place method is probably some mergesort variant
> like Timsort. But I guess the O(n) memory overhead makes it
> unsuitable as a general table.sort() replacement. That seems to
> apply for Alexander's use case, too.
>
> The most promising in-place method I could find was Smoothsort:
>
> http://en.wikipedia.org/wiki/Smoothsort
> http://www.keithschwarz.com/smoothsort/
>
> It's a bit hard to understand and tricky to implement efficiently.
> For a plain Lua implementation I'd replace the scaled bitmap with
> a small array. So, if someone wants to have a go ...
>
> To Alexander: I'd suggest to try qsort() plus a (slow) FFI callback
> first. As Demetri said: it might be fast enough for your needs.
>
> --Mike
>
That does look like a pretty good choice of algorithm, though I have
to admit in-place quicksort looks attractive too. It's a simpler
algorithm and has a similar O(log n) memory requirement (a somewhat
higher coefficient, I admit).
/s/ Adam
Other related posts:
