[Haskell-cafe] hstats median algorithm

KC kc1956 at gmail.com
Sun Sep 2 08:14:08 CEST 2012

Is there any special structure in your data that could be exploited?

On Sat, Sep 1, 2012 at 6:17 PM, Gershom Bazerman <gershomb at gmail.com> wrote:
> 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?
> If you did, you could write it, and contact the package author with a patch.
> You also may be able to find something of use in Edward Kmett's
> order-statistics package:
> http://hackage.haskell.org/package/order-statistics
> Cheers,
> Gershom
> On 9/1/12 3:26 PM, David Feuer wrote:
>> The median function in the hstats package uses a naive O(n log n)
>> algorithm. Is there another package providing an O(n) option? If not,
>> what would it take to get the package upgraded?


More information about the Haskell-Cafe mailing list