Skip to main content

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.


from mediantracker import MedianTracker
tracker = MedianTracker()
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 | RSS feed

This version


Download files

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

Files for mediantracker, version 1.0
Filename, size File type Python version Upload date Hashes
Filename, size mediantracker-1.0.tar.gz (6.4 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page