Useful class, but I'm really not convinced it's statistically sound. You need
to normalize the stored value after every operation, otherwise as it gets
larger, you will get bigger jumps when values are reported. In order to do
this, you probably need to extend BDRA; put some hooks in.
On Wednesday 26 December 2007 20:51, robert at freenetproject.org wrote:
> Author: robert
> Date: 2007-12-26 20:51:38 +0000 (Wed, 26 Dec 2007)
> New Revision: 16817
>
> Added:
> trunk/freenet/src/freenet/support/math/DecayingKeyspaceAverage.java
> Modified:
> trunk/freenet/src/freenet/node/Location.java
> trunk/freenet/src/freenet/node/NodeStats.java
> Log:
> implement keyspace-aware averager
>
>
> Modified: trunk/freenet/src/freenet/node/Location.java
> ===================================================================
> --- trunk/freenet/src/freenet/node/Location.java 2007-12-26 20:48:13 UTC
(rev 16816)
> +++ trunk/freenet/src/freenet/node/Location.java 2007-12-26 20:51:38 UTC
(rev 16817)
> @@ -70,6 +70,20 @@
> }
> }
>
> + /**
> + * Given an arbitrary double (not bound to [0.0, 1.0]) return the
normalized double [0.0, 1.0] which would result in simple
> + * wrapping/overflowing. e.g. normalize(1.0+0.5)==0.5,
normalize(0.5-1.0)==0.5, normalize({0.0,1.0})=={0.0,1.0}
> + * @bug: if given double has wrapped too many times, the return value
> may
be not be precise.
> + */
> + public static double normalize(double rough) {
> + int intPart=(int)rough;
> + double maybeNegative=rough-intPart;
> + //note: maybeNegative is bound between (-1.0, 1.0)
> + if (maybeNegative < 0)
> + return 1.0+maybeNegative;
> + return maybeNegative;
> + }
> +
> public static boolean equals(double newLoc, double currentLocation) {
> return Math.abs(newLoc - currentLocation) < Double.MIN_VALUE *
> 2;
> }
>
> Modified: trunk/freenet/src/freenet/node/NodeStats.java
> ===================================================================
> --- trunk/freenet/src/freenet/node/NodeStats.java 2007-12-26 20:48:13 UTC
(rev 16816)
> +++ trunk/freenet/src/freenet/node/NodeStats.java 2007-12-26 20:51:38 UTC
(rev 16817)
> @@ -23,6 +23,7 @@
> import freenet.support.api.IntCallback;
> import freenet.support.api.LongCallback;
> import freenet.support.math.BootstrappingDecayingRunningAverage;
> +import freenet.support.math.DecayingKeyspaceAverage;
> import freenet.support.math.RunningAverage;
> import freenet.support.math.TimeDecayingRunningAverage;
> import freenet.support.math.TrivialRunningAverage;
> @@ -189,11 +190,11 @@
> this.backedOffPercent = new TimeDecayingRunningAverage(0.0,
> 180000, 0.0,
1.0, node);
> double nodeLoc=node.lm.getLocation();
> // FIXME PLEASE; (int) casts; (maxCacheKeys>MAXINT?) This value
> will
probably end up being a small constant anyway (200?).
> - this.avgCacheLocation = new
BootstrappingDecayingRunningAverage(nodeLoc, 0.0, 1.0,
(int)node.maxCacheKeys, null);
> - this.avgStoreLocation = new
BootstrappingDecayingRunningAverage(nodeLoc, 0.0, 1.0,
(int)node.maxStoreKeys, null);
> - this.avgCacheSuccess = new
BootstrappingDecayingRunningAverage(nodeLoc, 0.0, 1.0, 10000, null);
> - this.avgStoreSuccess = new
BootstrappingDecayingRunningAverage(nodeLoc, 0.0, 1.0, 10000, null);
> - this.avgRequestLocation = new
BootstrappingDecayingRunningAverage(nodeLoc, 0.0, 1.0, 10000, null);
> + this.avgCacheLocation = new DecayingKeyspaceAverage(nodeLoc,
(int)node.maxCacheKeys, null);
> + this.avgStoreLocation = new DecayingKeyspaceAverage(nodeLoc,
(int)node.maxStoreKeys, null);
> + this.avgCacheSuccess = new DecayingKeyspaceAverage(nodeLoc,
> 10000,
null);
> + this.avgStoreSuccess = new DecayingKeyspaceAverage(nodeLoc,
> 10000,
null);
> + this.avgRequestLocation = new DecayingKeyspaceAverage(nodeLoc,
> 10000,
null);
> preemptiveRejectReasons = new StringCounter();
> localPreemptiveRejectReasons = new StringCounter();
> pInstantRejectIncoming = new TimeDecayingRunningAverage(0,
> 60000, 0.0,
1.0, node);
>
> Added: trunk/freenet/src/freenet/support/math/DecayingKeyspaceAverage.java
> ===================================================================
> --- trunk/freenet/src/freenet/support/math/DecayingKeyspaceAverage.java
>
(rev 0)
> +++ trunk/freenet/src/freenet/support/math/DecayingKeyspaceAverage.java
2007-12-26 20:51:38 UTC (rev 16817)
> @@ -0,0 +1,139 @@
> +/* This code is part of Freenet. It is distributed under the GNU General
> + * Public License, version 2 (or at your option any later version). See
> + * http://www.gnu.org/ for further details of the GPL. */
> +package freenet.support.math;
> +
> +import freenet.node.Location;
> +
> +import freenet.support.Logger;
> +import freenet.support.SimpleFieldSet;
> +
> +/**
> + * @author robert
> + *
> + * A filter on BootstrappingDecayingRunningAverage which makes it aware of
the circular keyspace.
> + */
> +public class DecayingKeyspaceAverage implements RunningAverage {
> + /**
> + 'avg' is the non-normalized average location.
> + */
> + BootstrappingDecayingRunningAverage avg;
> +
> + //If the keyspace averager wraps more than this number of times, an
exception will be thrown.
> + public final static int WRAP_WARNING=1000;
> +
> + public DecayingKeyspaceAverage(double defaultValue, int maxReports,
SimpleFieldSet fs) {
> + avg=new BootstrappingDecayingRunningAverage(defaultValue,
> -WRAP_WARNING,
WRAP_WARNING, maxReports, fs);
> + }
> +
> + public DecayingKeyspaceAverage(BootstrappingDecayingRunningAverage a) {
> + //check the max/min values? ignore them?
> + avg=(BootstrappingDecayingRunningAverage)a.clone();
> + }
> +
> + public synchronized Object clone() {
> + return new DecayingKeyspaceAverage(avg);
> + }
> +
> + public synchronized double currentValue() {
> + return Location.normalize(avg.currentValue());
> + }
> +
> + public synchronized void report(double d) {
> + if ((d < 0.0) || (d > 1.0)) {
> + //Just because we use non-normalized locations doesn't
> mean we can
accept them.
> + throw new IllegalArgumentException("Not a valid
> normalized key: "+d);
> + }
> + double superValue=avg.currentValue();
> + double thisValue=Location.normalize(superValue);
> + double diff=Location.change(thisValue, d);
> + double toAverage=(superValue+diff);
> + /*
> + To gracefully wrap around the 1.0/0.0 threshold we average
> over (or
under) it, and simply normalize the result when reporting a currentValue
> + ---example---
> + d=0.2; //being reported
> + superValue=1.9; //already wrapped once, but at 0.9
> + thisValue=0.9; //the normalized value of where we are in the
> keyspace
> + diff = +0.3; //the diff from the normalized values;
Location.change(0.9, 0.2);
> + avg.report(2.2);//to successfully move the average towards the
> closest
route to the given value.
> + */
>
+ //System.err.println("debug: "+superValue+", "+thisValue+",
"+diff+", "+(superValue+diff)+", "+Location.normalize(superValue+diff));
> + if (toAverage>WRAP_WARNING || toAverage<-WRAP_WARNING)
> + Logger.error(this, "DecayingKeyspaceAverage is wrapped
> up too many
times");
> + avg.report(toAverage);
> + }
> +
> + public synchronized double valueIfReported(double d) {
> + if ((d < 0.0) || (d > 1.0)) {
> + throw new IllegalArgumentException("Not a valid
> normalized key: "+d);
> + }
> + double superValue=avg.currentValue();
> + double thisValue=Location.normalize(superValue);
> + double diff=Location.change(thisValue, d);
> + return avg.valueIfReported(superValue+diff);
> + }
> +
> + public synchronized long countReports() {
> + return avg.countReports();
> + }
> +
> + public void report(long d) {
> + throw new IllegalArgumentException("KeyspaceAverage does not
> like
longs");
> + }
> +
> + ///@todo: make this a junit test
> + public static void main(String[] args) {
> + DecayingKeyspaceAverage a=new DecayingKeyspaceAverage(0.9, 10,
> null);
> + a.report(0.9);
> + for (int i=10; i!=0; i--) {
> + a.report(0.2);
> + System.out.println("<-0.2-- current="+a.currentValue());
> + }
> + for (int i=10; i!=0; i--) {
> + a.report(0.8);
> + System.out.println("--0.8-> current="+a.currentValue());
> + }
> + System.out.println("--- positive wrap test ---");
> + for (int wrap=3; wrap!=0; wrap--) {
> + System.out.println("wrap test #"+wrap);
> + for (int i=10; i!=0; i--) {
> + a.report(0.25);
> + System.out.println("<-0.25-
> current="+a.currentValue());
> + }
> + for (int i=10; i!=0; i--) {
> + a.report(0.5);
> + System.out.println("--0.5->
> current="+a.currentValue());
> + }
> + for (int i=10; i!=0; i--) {
> + a.report(0.75);
> + System.out.println("-0.75->
> current="+a.currentValue());
> + }
> + for (int i=10; i!=0; i--) {
> + a.report(1.0);
> + System.out.println("<-1.0--
> current="+a.currentValue());
> + }
> + }
> + System.out.println("--- negative wrap test ---");
> + a=new DecayingKeyspaceAverage(0.2, 10, null);
> + a.report(0.2);
> + for (int wrap=3; wrap!=0; wrap--) {
> + System.out.println("negwrap test #"+wrap);
> + for (int i=10; i!=0; i--) {
> + a.report(0.75);
> + System.out.println("-0.75->
> current="+a.currentValue());
> + }
> + for (int i=10; i!=0; i--) {
> + a.report(0.5);
> + System.out.println("<-0.5--
> current="+a.currentValue());
> + }
> + for (int i=10; i!=0; i--) {
> + a.report(0.25);
> + System.out.println("<-0.25-
> current="+a.currentValue());
> + }
> + for (int i=10; i!=0; i--) {
> + a.report(1.0);
> + System.out.println("--1.0->
> current="+a.currentValue());
> + }
> + }
> + }
> +}
> \ No newline at end of file
>
> _______________________________________________
> cvs mailing list
> cvs at freenetproject.org
> http://emu.freenetproject.org/cgi-bin/mailman/listinfo/cvs
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL:
<https://emu.freenetproject.org/pipermail/devl/attachments/20080103/ff68ba22/attachment.pgp>
