in reply to need a faster median

I would assume that the "best" way to go really depends on what you really need, and by how much the calculated median is allowed to deviate from the real median.

You do realize that to find the real median, you always have to look at at least 50% of all elements in your set unless you do some preparation. If you can pre-sort your elements or use a heap, or a good estimate where your median will likely land, you might get away with throwing out more elements. But all of these approaches have drawbacks and you haven't stated what drawbacks are acceptable and which ones are not.

Replies are listed 'Best First'.
Re^2: need a faster median
by Anonymous Monk on Oct 18, 2011 at 16:46 UTC
    I have a non-sorted array of "floats" of size 10M+. I have no more assumptions.
[reply]

      I found that on my laptop, I can find the mode of 10 million floats in 13 seconds. Just keep a count of each value encountered and select the largest value. There's no need to sort it.

      Update: I forgot to mention that a hash is a good place to keep your counts...

      ...roboticus

      When your only tool is a hammer, all problems look like your thumb.

[reply]

In Section Seekers of Perl Wisdom