On Tue, Jan 13, 2009 at 7:16 AM, <[email protected]> wrote:
> Author: toad
> Date: 2009-01-12 23:16:02 +0000 (Mon, 12 Jan 2009)
> New Revision: 25043
>
> Modified:
> trunk/freenet/src/freenet/support/math/MedianMeanRunningAverage.java
> Log:
> Document
>
>
> Modified: trunk/freenet/src/freenet/support/math/MedianMeanRunningAverage.java
> ===================================================================
> --- trunk/freenet/src/freenet/support/math/MedianMeanRunningAverage.java
> 2009-01-12 23:14:18 UTC (rev 25042)
> +++ trunk/freenet/src/freenet/support/math/MedianMeanRunningAverage.java
> 2009-01-12 23:16:02 UTC (rev 25043)
> @@ -1,8 +1,13 @@
> package freenet.support.math;
>
> import java.util.ArrayList;
> -import java.util.TreeSet;
>
> +/**
> + * A RunningAverage that tracks both the median and mean of a series of
> values.
> + * WARNING: Uses memory and proportional to the number of reports! Only for
> debugging!
> + * (Also uses CPU time O(N log N) with the number of reports in
> currentValue()).
There is an incremental algorithm for getting the median -- O(lg n)
insertion, O(1) retrieval.
Just keep two binary heap ( java.util.PriorityQueue )
-- one maximum heap
holding the numbers less then median,
-- one minimum heap:
the another holds those are greater then the median
> + * @author Matthew Toseland <[email protected]> (0xE43DA450)
> + */
> public class MedianMeanRunningAverage implements RunningAverage {
>
> final ArrayList<Double> reports;
>
> _______________________________________________
> cvs mailing list
> [email protected]
> http://emu.freenetproject.org/cgi-bin/mailman/listinfo/cvs
>
_______________________________________________
Devl mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
