Sliding Median
June 29, 2012
We saw the streaming median problem in a recent exercise. Today we look at a slight variant on that problem, the sliding median, which slides a window of width k over an input stream, reporting the median of each successive window.
The streaming median required us to keep the entire input stream in memory. But for the sliding median, we keep only the most recent k items. We keep two data structures. A cyclical queue keeps the most recent input items, in the order in which they are input. An ordered map keeps the input items in sorted order. After reading the first k items, each time we read an item we output the current median, delete the oldest item in the cyclical queue from the ordered map, insert the new item into both the ordered map and the cyclical queue, and go on to the next item.
Your task is to write a program that implements the sliding median calculation. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to determine the median values of a sliding window over a […]
My Haskell solution (see http://bonsaicode.wordpress.com/2012/06/29/programming-praxis-sliding-median/ for a version with comments):
import Data.List slidingMedian :: (Ord a, Fractional a) => Int -> Int -> [a] -> [a] slidingMedian size count = map ((\ ~(x:xs) -> if odd size then x else (x + head xs) / 2) . drop (div (size - 1) 2) . sort . take size) . take count . tailsFairly basic python implementation.
It uses a sorted list for the ordered map.
from bisect import insort from collections import deque def sliding_median(iterable, k): ''' generator returning median value in a sliding window k elements wide. >>> data = [13, 28, 94, 34, 32, 78, 12, 10, 84, 93, 45, 66, 67, 52, 24, 49] >>> list(sliding_median(data, 5)) [32, 34, 34, 32, 32, 78, 45, 66, 67, 66, 52, 52] ''' fifo = deque(maxlen=k) omap = [] m = (k-1)//2 median = (lambda:omap[m]) if k&1 else (lambda:(omap[m] + omap[m+1])/2.0) for x in iter(iterable): fifo.append(x) insort(omap, x) if len(fifo) == k: yield median() omap.remove(fifo[0])templated c++ implementation.
#include <iostream> #include <vector> #include <algorithm> #include <iterator> template<class I, class J> void SlidingMedian( I inIter, I inEnd, J output, int window ) { typedef typename std::iterator_traits<I>::value_type T; std::vector<T> cq( window ); std::vector<T> ordered( window ); int index = 0; bool full = false; for( ; inIter != inEnd; ++inIter ) { T in = *inIter; T old = cq[index]; cq[index] = in; index = ( index+1 ) % window; if( index == 0 ) full = true; ordered.erase( std::lower_bound( ordered.begin(), ordered.end(), old ) ); ordered.insert( std::upper_bound( ordered.begin(), ordered.end(), in ), in ); if( full ) { if( window % 2 ) *output++ = ordered[ window/2 ]; else *output++ = ( ordered[ window/2-1 ] + ordered[ window/2 ] ) / T(2); } } } int main(int argc, char* argv[]) { double d[] = { 13, 28, 94, 34, 32, 78, 12, 10, 84, 93, 45, 66 }; std::vector<double> output; SlidingMedian( &d[0], &d[ sizeof(d)/sizeof(d[0]) ], std::insert_iterator< std::vector<double> >( output, output.begin() ), 5 ); for( double v : output ) { std::cout << v << " "; } std::cout << std::endl; return 0; }SlidingMedian class uses three data structures:
1) List which maintains the order of values as they arrive
2) Two STL sets, which are implemented as balanced binary search trees. One set stores all values less than or equal to the median, the other set stores values greater than or equal to the median.
Insert and median retrieval is therefore O(log n).
#include <iostream> #include <iomanip> #include <set> #include <list> // **************************************************** // **************************************************** class SlidingMedian { public: /** * Construct a new SlidingMedian class * @param k the window size of the sliding median */ SlidingMedian(size_t k); /** * Post a new value to the sliding median object * @param v the new value to post * @return the new median */ float post(int v); private: /** store the window size */ size_t window; /** store the orded list of values */ std::list<int> list; /** store the lower half set of values */ std::set<int> lowSet; /** store the upper half set of values */ std::set<int> hghSet; }; // **************************************************** // **************************************************** SlidingMedian::SlidingMedian(size_t k) : window(k) { } // **************************************************** // **************************************************** SlidingMedian::SlidingMedian(size_t k) : window(k) { } // **************************************************** // **************************************************** float SlidingMedian::post(int v) { // remove the old value if(this->list.size() == this->window) { int vOld(this->list.front()); // erase the value from the list this->list.erase(this->list.begin()); // see which set the value to remove is in if(this->lowSet.size() && vOld <= *(this->lowSet.rbegin())) { this->lowSet.erase(vOld); } else if(this->hghSet.size() && vOld >= *(this->hghSet.begin())) { this->hghSet.erase(vOld); } else { throw std::string("SlidingMedian::post Internal Error"); } } // insert the new value this->list.push_back(v); if(this->hghSet.size() && v >= (*this->hghSet.begin())) { this->hghSet.insert(v); } else { this->lowSet.insert(v); } // balance the two sets while(this->lowSet.size() > (this->hghSet.size())) { this->hghSet.insert(*this->lowSet.rbegin()); this->lowSet.erase(*this->lowSet.rbegin()); } while(this->hghSet.size() > (this->lowSet.size())) { this->lowSet.insert(*this->hghSet.begin()); this->hghSet.erase(*this->hghSet.begin()); } // return the median of the two sets if(this->lowSet.size() == this->hghSet.size()) { return ((*this->lowSet.rbegin()+*this->hghSet.begin())/2.0f); } else { return *this->lowSet.rbegin(); } } // **************************************************** // **************************************************** int main(int argc, char *argv[]) { SlidingMedian slm(17); for(size_t idx(0); idx < 100; ++idx) { float median(slm.post(rand() % 1000)); std::cout << "Median: " << median << std::endl; } return 0; }Of course, anyone that is actually paying attention would have used:
in place of
[…] have previously studied algorithms for the streaming median and sliding median that calculate the median of a stream of numbers; the streaming median requires storage of all the […]