Metadata-Version: 1.0
Name: mediantracker
Version: 1.0
Summary: Tracks the overall median of a stream of values "on-line" in reasonably efficient fashion.
Home-page: http://sourceforge.net/projects/mediantracker/
Author: John Kleint
Author-email: mediantracker-general@lists.sourceforge.net
License: MIT License
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
        
        
        
Keywords: median statistics online incremental dynamic mathematics
Platform: UNKNOWN
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: Natural Language :: English
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 2
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: License :: OSI Approved :: MIT License
