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.

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 | RSS feed

This version

1.0

Download files

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

Source Distribution

mediantracker-1.0.tar.gz (6.4 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page