On Tuesday 13 January 2009 00:23, Daniel Cheng wrote:
> On Tue, Jan 13, 2009 at 7:16 AM, <toad at freenetproject.org> 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
Hmmm, I was assuming that currentValue() wouldn't be called often, but in fact
we call it every time we log ... IMHO it's not a big deal either way. Even
with the impl you mention, we would still have the memory leak, unless we
spend a lot more memory on an LRU...
>
> > + * @author Matthew Toseland <toad at amphibian.dyndns.org> (0xE43DA450)
> > + */
> > public class MedianMeanRunningAverage implements RunningAverage {
> >
> > final ArrayList<Double> reports;
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: not available
URL:
<https://emu.freenetproject.org/pipermail/devl/attachments/20090113/edaec92f/attachment.pgp>
