Faster implementation of alexandria:median

[Anish Moorthy]

Hello!

I wanted to submit a re-implementation of alexandria:median. Currently the function works by fully sorting the sequence, which has a complexity of O(n log n). In the attached patch I provide an implementation as a special case of the quick select algorithm, which brings its complexity down to O(n).

The new implementation is more complicated, though I think it's still simpler than some other algorithms in alexandria. Anyways, the performance gains are dramatic enough that I thought I'd at least submit the patch. I did some testing via the timing code in median-timing.lisp, and observed speedups of 5-10x even on sequences with just 100 elements.

I could also provide the quick select algorithm as its own function if there's any interest, though I'm not sure what the appetite for adding new features is.

- Anish Moorthy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/alexandria-devel/attachments/20191127/d4201219/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Re-implement-median-function-using-the-quick-select-.patch
Type: text/x-patch
Size: 3241 bytes
Desc: not available
URL: <https://mailman.common-lisp.net/pipermail/alexandria-devel/attachments/20191127/d4201219/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: median-timing.lisp
Type: application/octet-stream
Size: 208 bytes
Desc: not available
URL: <https://mailman.common-lisp.net/pipermail/alexandria-devel/attachments/20191127/d4201219/attachment.obj>