Skip to main content
Help us improve PyPI by participating in user testing. All experience levels needed!

Tracks the overall median of a stream of values "on-line" in reasonably efficient fashion.

Project description

Track the median of a stream of values “on-line” in reasonably efficient fashion.

Usage:

from mediantracker import MedianTracker
tracker = MedianTracker()
tracker.add(1)
tracker.add(2)
tracker.add(3)
tracker.add(4)
assert tracker.lower_median() == 2
assert tracker.upper_median() == 3

MedianTracker supports efficient median queries on and dynamic additions to a list of values. It provides both the lower and upper median of all values seen so far. Any __cmp__()-able object can be tracked, in addition to numeric types. add() takes log(n) time for a tracker with n items; lower_median() and upper_median() run in constant time. Since all values must be stored, memory usage is proportional to the number of values added (O(n)).

The values can be accessed via iteration over the MedianTracker, though they are not ordered in any particular way:

sum = 0.0
for val in tracker:
    sum += val
mean = sum / len(tracker)

Use this module if you are processing values “on-line,” one at a time, as they arrive, and need to know the new median after each new value (or batch of values). If you just want the median of a whole list, there are much more efficient linear-time median (or more general k-th smallest selection) algorithms. Using this module will take O(nlogn) time and an extra O(n) space to compute the median of n items. On the other hand, a MedianTracker will only take O(nlogn + m) time for any sequence of n adds and m median queries, whereas running a traditional non-incremental median algorithm m times would take O(n*m).

Finally, some sources define the median of an even-length list to be the average of the middle two values. This is easily and efficiently computed (in constant time):

tracker = MedianTracker([1, 2, 3, 4])
median = (tracker.lower_median() + tracker.upper_median()) / 2.0
assert median == 2.5

Project details


Release history Release notifications

This version
History Node

1.0

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size & hash SHA256 hash help File type Python version Upload date
mediantracker-1.0.tar.gz (6.4 kB) Copy SHA256 hash SHA256 Source None Sep 2, 2009

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging CloudAMQP CloudAMQP RabbitMQ AWS AWS Cloud computing Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page