On Oct 13, 11:57 am, sturlamolden <sturlamol...@yahoo.no> wrote: > On 13 Okt, 18:33, Paul Rubin <http://phr...@nospam.invalid> wrote: > > > The obvious way to compute a running median involves a tree structure > > so you can quickly insert and delete elements, and find the median. > > That would be asymtotically O(n log n) but messy to implement. > > QuickSelect will find the median in O(log n) time.
Right. See http://code.activestate.com/recipes/269554/ for a sample implementation in Python. Raymond -- http://mail.python.org/mailman/listinfo/python-list