Efficient Running Median

Discussion in 'Python' started by Raymond Hettinger, Jan 15, 2010.

  1. 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
    Raymond Hettinger, Jan 15, 2010
    #1
    1. Advertising

  2. Raymond Hettinger

    Aahz Guest

    In article <>,
    Raymond Hettinger <> wrote:
    >
    >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?
    --
    Aahz () <*> http://www.pythoncraft.com/

    import antigravity
    Aahz, Jan 22, 2010
    #2
    1. Advertising

  3. Raymond Hettinger

    Bearophile Guest

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

    Bye,
    bearophile
    Bearophile, Jan 23, 2010
    #3
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andreas
    Replies:
    1
    Views:
    1,633
    Tuukka Toivonen
    Dec 2, 2003
  2. Robert Brewer

    RE: Mean, median, and mode

    Robert Brewer, Dec 5, 2004, in forum: Python
    Replies:
    5
    Views:
    435
    Paul McGuire
    Dec 6, 2004
  3. Alfred Canoy

    Re: Python-Help ( Mean,Median & Mode)

    Alfred Canoy, Dec 5, 2004, in forum: Python
    Replies:
    2
    Views:
    11,119
    Dan Bishop
    Dec 6, 2004
  4. Josiah Carlson

    Re: Mean, median, and mode

    Josiah Carlson, Dec 6, 2004, in forum: Python
    Replies:
    7
    Views:
    466
    Steven Bethard
    Dec 6, 2004
  5. Janto Dreijer

    efficient running median

    Janto Dreijer, Oct 13, 2009, in forum: Python
    Replies:
    26
    Views:
    2,260
    denis
    Oct 26, 2009
Loading...

Share This Page