Efficient Running Median

R

Raymond Hettinger

I've updated the running median recipe to use a new algorithm with O
(log n) updates for a large sliding window traversing a data stream.
See http://code.activestate.com/recipes/576930/

The engine is a new collection class called IndexableSkiplist. It is
like a regular skiplist as detailed at http://en.wikipedia.org/wiki/Skip_list,
but it also records the width of each link field. That allows values
to be retrieved by their position index in O(log n) time.

The key operations are:
O(log n) -- sl.insert(value) # add a value to the skiplist,
maintaining sorted order
O(log n) -- s.remove(value) # remove a value from the skiplist,
maintaining sorted order
O(log n) -- s # retrieve the i-th item
O(n) -- list(sl) # iterate over the skiplist in sorted
order
O(1) -- len(sl) # number of items in the skiplist

The performance of an IndexableSkiplist is similar to a B+tree but the
implementation in pure python is much simpler.


Raymond
 
A

Aahz

The performance of an IndexableSkiplist is similar to a B+tree but the
implementation in pure python is much simpler.

Nice! Can you summarize why IndexableSkipList is simpler?
 
B

Bearophile

Very nice. I have added a comment at the bottom, using a circular
queue instead of a deque may be faster.

Bye,
bearophile
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top