Alex Rivera | Logout

How to calculate or approximate the median of a list without storing the list

Asked 2009-03-12T10:28:59.970
53

I'm trying to calculate the median of a set of values, but I don't want to store all the values as that could blow memory requirements. Is there a way of calculating or approximating the median without storing and sorting all the individual values?

Ideally I would like to write my code a bit like the following

var medianCalculator = new MedianCalculator();
foreach (var value in SourceData)
{
  medianCalculator.Add(value);
}
Console.WriteLine("The median is: {0}", medianCalculator.Median);

All I need is the actual MedianCalculator code!

Update: Some people have asked if the values I'm trying to calculate the median for have known properties. The answer is yes. One value is in 0.5 increments from about -25 to -0.5. The other is also in 0.5 increments from -120 to -60. I guess this means I can use some form of histogram for each value.

Thanks

Nick

algorithm optimization median
Edit
Report

1 Answer

2

Find Min and Max of the list containing N items through linear search and name them as HighValue and LowValue Let MedianIndex = (N+1)/2

1st Order Binary Search:

Repeat the following 4 steps until LowValue < HighValue.

  1. Get MedianValue approximately = ( HighValue + LowValue ) / 2

  2. Get NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

  3. is K = MedianIndex, then return MedianValue

  4. is K > MedianIndex ? then HighValue = MedianValue Else LowValue = MedianValue

It will be faster without consuming memory

2nd Order Binary Search:

LowIndex=1 HighIndex=N

Repeat Following 5 Steps until (LowIndex < HighIndex)

  1. Get Approximate DistrbutionPerUnit=(HighValue-LowValue)/(HighIndex-LowIndex)

  2. Get Approximate MedianValue = LowValue + (MedianIndex-LowIndex) * DistributionPerUnit

  3. Get NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

  4. is (K=MedianIndex) ? return MedianValue

  5. is (K > MedianIndex) ? then HighIndex=K and HighValue=MedianValue Else LowIndex=K and LowValue=MedianValue

It will be faster than 1st order without consuming memory

We can also think of fitting HighValue, LowValue and MedianValue with HighIndex, LowIndex and MedianIndex to a Parabola, and can get ThirdOrder Binary Search which will be faster than 2nd order without consuming memory and so on...

answered 2009-03-12T13:56:15.387

Your Answer