25
$\begingroup$

On smaller window sizes, n log n sorting might work. Are there any better algorithms to achieve this?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I think this is the first candidate to be moved to Stack Overflow. $\endgroup$
    – user88
    Commented Jul 19, 2010 at 21:38
  • $\begingroup$ Possibly, but it'd need a lot more explanation on SO. $\endgroup$
    – walkytalky
    Commented Jul 20, 2010 at 1:29
  • 2
    $\begingroup$ Most programmers know "median". (sort(array))[length/2] is a big enough hint for those who forgot. Also at its most basic for each new point you only need to do a bisection/insert on one half of the array... $\endgroup$
    – Paul
    Commented Jul 20, 2010 at 9:04
  • 1
    $\begingroup$ Re-opened following discussion at meta.stats.stackexchange.com/questions/276/… $\endgroup$
    – Rob Hyndman
    Commented Aug 13, 2010 at 0:31
  • 2
    $\begingroup$ Too trivial to be more than a comment, but code for the median of 3s is just a + b + c - max(a, b, c) - min(a, b. c). That works fine even if ties are present. That was only obvious to me once I'd thought about it from someone else's code (why is he (in this case) adding and subtracting to get a median???) and a few others might have the same reaction. max() and min() are often implemented as super-fast functions. Sadly there is no such trick in general. $\endgroup$
    – Nick Cox
    Commented Feb 27, 2018 at 15:31

8 Answers 8

Reset to default
15
$\begingroup$

#Edit: As @Hunaphu's points out (and @whuber below in his answer) the original answer I gave to the OP (below) is wrong. It is indeed quicker to first sort the initial batch and then keep updating the median up or down (depending on whether a new data points falls to the left or to the right of the current median).

It's bad form to sort an array to compute a median. Medians (and other quantiles) are typically computed using the quickselect algorithm, with $O(n)$ complexity.

You may also want to look at my answer to a recent related question here.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @Hunaphu: you are correct. I edited my answer. $\endgroup$
    – user603
    Commented Aug 20, 2021 at 9:18
7
$\begingroup$

If you're willing to tolerate an approximation, there are other methods. For example, one approximation is a value whose rank is within some (user specified) distance from the true median. For example, the median has (normalized) rank 0.5, and if you specify an error term of 10%, you'd want an answer that has rank between 0.45 and 0.55.

If such an answer is appropriate, then there are many solutions that can work on sliding windows of data. The basic idea is to maintain a sample of the data of a certain size (roughly 1/error term) and compute the median on this sample. It can be shown that with high probability, regardless of the nature of the input, the resulting median satisfies the properties I mentioned above.

Thus, the main question is how to maintain a running sample of the data of a certain size, and there are many approaches for that, including the technique known as reservoir sampling. For example, this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136

Improve this answer
$\endgroup$
7
$\begingroup$

If you maintain a length-k window of data as a sorted doubly linked list then, by means of a binary search (to insert each new element as it gets shifted into the window) and a circular array of pointers (to immediately locate elements that need to be deleted), each shift of the window requires O(log(k)) effort for inserting one element, only O(1) effort for deleting the element shifted out of the window, and only O(1) effort to find the median (because every time one element is inserted or deleted into the list you can update a pointer to the median in O(1) time). The total effort for processing an array of length N therefore is O((n-k)log(k)) <= O(n log(k)). This is better than any of the other methods proposed so far and it is not an approximation, it is exact.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Could you elaborate on how you propose to do a binary search in a sorted doubly-linked list? $\endgroup$
    – NPE
    Commented Nov 28, 2010 at 12:14
  • $\begingroup$ one 'link' allows you to traverse the list in sorted order; the other allows you to traverse in the order in which the elements appear. It is not clear how you would do this with pointers, though, as @aix questions. $\endgroup$
    – shabbychef
    Commented Nov 28, 2010 at 17:02
  • 2
    $\begingroup$ @aix I think your intimation is correct; I would need an indexable skip list, not just a sorted doubly-linked list. The idea is to have a data structure that permits the insertion of one element, the deletion of one element, and finding the median in expected O(log(n)) time (or better). $\endgroup$
    – whuber ♦
    Commented Nov 28, 2010 at 19:17
7
$\begingroup$

Here is an article describing one possible algorithm. Source code included and a quite serious application (gravitational wave detection based on laser interferometry), so you can expect it to be well tested.

Improve this answer
$\endgroup$
2
4
$\begingroup$

Here is a solution O(1) for finding current median, and O(log n) for adding a new number http://www.dsalgo.com/RunningMedian.php

Improve this answer
$\endgroup$
1
  • $\begingroup$ This seems more like for cumulative median, not for moving window median. $\endgroup$
    – Wei Qiu
    Commented Oct 25, 2022 at 6:24
3
$\begingroup$

As you mentioned sorting would be O(n·log n) for a window of length n. Doing this moving adds another l=vectorlength making the total cost O(l·n·log n).

The simplest way to push this is by keeping an ordered list of the last n elements in memory when moving from one window to the next one. As removing/inserting one element from/into an ordered list are both O(n) this would result in costs of O(l·n).

Pseudocode:

l = length(input)
aidvector = sort(input(1:n))
output(i) = aid(n/2)
for i = n+1:l
    remove input(i-n) from aidvector
    sort aid(n) into aidvector
    output(i) = aid(n/2)
Improve this answer
$\endgroup$
2
$\begingroup$

If you can live with an estimate instead of the true median, the Remedian Algorithm (PDF) is one-pass with low storage requirements and well defined accuracy.

The remedian with base b proceeds by computing medians of groups of b observations, and then medians of these medians, until only a single estimate remains. This method merely needs k arrays of size b (where n = b^k)...

Improve this answer
$\endgroup$
1
  • $\begingroup$ The link is broken unfortunately. $\endgroup$
    – Turion
    Commented Dec 8, 2023 at 11:13
0
$\begingroup$

I used this RunningStats C++ Library in an embedded application. It is the most simple running stats library I have found yet.

From the link:

The code is an extension of the method of Knuth and Welford for computing standard deviation in one pass through the data. It computes skewness and kurtosis as well with a similar interface. In addition to only requiring one pass through the data, the algorithm is numerically stable and accurate.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Does that page say anything about median? $\endgroup$
    – musiphil
    Commented Nov 20, 2015 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.