On 01/19/2016 09:26 PM, Timon Gehr wrote:
On 01/20/2016 02:20 AM, Andrei Alexandrescu wrote:
I've seldom have code write itself so beautifully. Which, of course,
means it needs to be destroyed.
https://github.com/D-Programming-Language/phobos/pull/3938 -- Andrei
This is not an implementation of the median of medians algorithm.
[snip]
Thanks again for sharing your insight. FWIW there's a bit of variation
floating on the Net regarding MoM. The Wikipedia article at
https://en.wikipedia.org/wiki/Median_of_medians moves the medians of
five to the beginning of the array (my implementation uses stride(),
thus trading computation for data movement). I'm unclear on which
approach is generally better.
http://austinrochford.com/posts/2013-10-28-median-of-medians.html does
not mention the mutual recursion, suggesting (at least in a cursory
reading) my wishy-washy previous implementation that doesn't use
quickselect.
https://www.ics.uci.edu/~eppstein/161/960130.html only uses one
recursive function, not two.
The original PICK algorithm at
https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf only uses one
recursive function.
Anyhow, I've implemented the two-functions version at
https://github.com/D-Programming-Language/phobos/pull/3938. I'll next
try whether the one-function version is just as good or better. Destroy?
Andrei
