On Tuesday 13 January 2009 00:23, Daniel Cheng wrote: > 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
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 <[email protected]> (0xE43DA450) > > + */ > > public class MedianMeanRunningAverage implements RunningAverage { > > > > final ArrayList<Double> reports;
pgpXiOpC7Wx8P.pgp
Description: PGP signature
_______________________________________________ Devl mailing list [email protected] http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
