public class MedianFinder
extends java.lang.Object
The weighted median of n values x[i] is the value x that minimizes the following function:
n-1 f(x) = sum w[i]*abs(x-x[i]) i=0Here, the x[.] are values for which the median is to be computed, the w[.] are positive weights, and x is the desired weighted median. The function f(x) is convex and piecewise linear, so at least one (but no more than two) of the specified values x[i] minimizes the function f(x).
To find a minimum, we define sums of weights w[.] for which x[.] is less than, equal to, and greater than x:
wl(x) = sum of w[i] for x[i] < x wm(x) = sum of w[i] for x[i] = x wr(x) = sum of w[i] for x[i] > xand then define the left and right derivatives of f(x):
dl(x) = wl(x)-wm(x)-wr(x) <= 0 dr(x) = wl(x)+wm(x)-wr(x) >= 0These inequality conditions are necessary and sufficient for x to minimize f(x), that is, for x to be the weighted median.
When either dl(x) = 0 or dr(x) = 0, then the function f(x) has zero slope between two values x[i] that both minimize f(x), and the weighted median is then computed to be the average of those two minimizing values. For example, such an average is always computed when the number of values x[.] is even and all weights w[.] are equal.
Computational complexity for both the median and the weighted median is O(n), where n is the number of values x[.] (and weights w[.]). In benchmark tests for large n, the cost of a median is about 16 times more costly than a simple mean, and the cost of a weighted median is about 1.5 times more costly than an unweighted median.
Constructor and Description |
---|
MedianFinder(int n)
Constructs a median finder.
|
Modifier and Type | Method and Description |
---|---|
float |
findMedian(float[] x)
Returns the median of the specified array of values.
|
float |
findMedian(float[] w,
float[] x)
Returns the weighted median of the specified array of values.
|
public MedianFinder(int n)
n
- number of values for which to compute medians.public float findMedian(float[] x)
x
- array of values.public float findMedian(float[] w, float[] x)
w
- array of positive weights.x
- array of values.