## Sliding Median

### June 29, 2012

Our function is just a direct translation of the algorithm stated above, stopping after *n* items; the `next`

function fetches the next item from the input stream each time it is called:

`(define (sliding-median k next n)`

(let ((window (make-vector k)) (xs (make-dict <)))

(do ((i 0 (+ i 1))) ((= i k))

(let ((x (next)))

(vector-set! window i x)

(set! xs (xs 'insert x x))))

(do ((i 0 (+ i 1))) ((= i n))

(let ((x (next)))

(display

(if (odd? k)

(car (xs 'nth (quotient k 2)))

(/ (+ (car (xs 'nth (quotient k 2)))

(car (xs 'nth (+ (quotient k 2) 1))))

2)))

(newline)

(set! xs (xs 'delete (vector-ref window (modulo i k))))

(set! xs (xs 'insert x x))

(vector-set! window (modulo i k) x)))))

This will break if the sliding window ever contains two or more identical items; you could fix that with a custom dictionary that permits identical items. Here’s an example, with the input stream read from a string port:

`> (with-input-from-string "13 28 94 34 32 78 12 10 84 93 45 66 67 52 24 49"`

(lambda () (sliding-median 5 read 12)))

32

34

34

32

32

78

45

66

67

66

52

52

You can run the program at http://programmingpraxis.codepad.org/rsJImeg0, where we used a random number generator to supply the stream of numbers, instead of a string, because codepad doesn’t support the `with-input-from-string`

syntax.

[…] 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):

Fairly basic python implementation.

It uses a sorted list for the ordered map.

templated c++ implementation.

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).

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 […]