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 details)

Uploaded Source

File details

Details for the file mediantracker-1.0.tar.gz.

File metadata

  • Download URL: mediantracker-1.0.tar.gz
  • Upload date:
  • Size: 6.4 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No

File hashes

Hashes for mediantracker-1.0.tar.gz
Algorithm Hash digest
SHA256 c94504b2e82354e7f1241bfb521c88681beef159a8e95af0145262f77f5beacd
MD5 77666357b7340811a8b4d995c9ce1135
BLAKE2b-256 4494d67a68b8adb5c16ade6ff2a3054ef1c4a48f0197015cf08630b75d6d4ae5

See more details on using hashes here.

Supported by

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