<p>I was thinking it should offer a randomized version (taking a generator), since randomized median algorithms provide the best expected performance. It could also offer a deterministic version using some variant of median-of-medians, intended for long lists. I guess it probably should retain the naive version for short lists. Some benchmarking would suggest a good cutoff. Has anyone come up with a better practical deterministic O(n) algorithm since median-of-medians? I saw a paper by Dorit Dor on reducing the number of comparisons to a bit under 3n, which also showed a lower bound of a bit over 2n, but the algorithm she gives strikes me as far too complex to be practical.</p>
<div class="gmail_quote">On Sep 1, 2012 9:17 PM, "Gershom Bazerman" <<a href="mailto:gershomb@gmail.com">gershomb@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
In my experience, doing much better than the naive algorithm for median is surprisingly hard, and involves a choice from a range of trade-offs. Did you have a particular better algorithm in mind?<br>
<br>
If you did, you could write it, and contact the package author with a patch.<br>
<br>
You also may be able to find something of use in Edward Kmett's order-statistics package: <a href="http://hackage.haskell.org/package/order-statistics" target="_blank">http://hackage.haskell.org/<u></u>package/order-statistics</a><br>
<br>
Cheers,<br>
Gershom<br>
<br>
On 9/1/12 3:26 PM, David Feuer wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
The median function in the hstats package uses a naive O(n log n)<br>
algorithm. Is there another package providing an O(n) option? If not,<br>
what would it take to get the package upgraded?<br>
<br>
______________________________<u></u>_________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/haskell-cafe</a><br>
</blockquote>
<br>
</blockquote></div>