Your backtracking code will backtrack forever and visit every node if
necessary ... could this skew the simulation results? I suggest you increment
depth just before calling n.request() in request(), this would be a closer
approximation with the same simulation performance, and more accurate path
lengths.
Also, do you use the request rate code?
On Friday 23 May 2008 22:58, mrogers at freenetproject.org wrote:
> Author: mrogers
> Date: 2008-05-23 21:58:34 +0000 (Fri, 23 May 2008)
> New Revision: 20085
>
> Added:
> trunk/apps/freenet-caching/
> trunk/apps/freenet-caching/CachingSim.java
> trunk/apps/freenet-caching/FifoNode.java
> trunk/apps/freenet-caching/LruNode.java
> trunk/apps/freenet-caching/Node.java
> trunk/apps/freenet-caching/RandomNode.java
> trunk/apps/freenet-caching/RequestGenerator.java
> trunk/apps/freenet-caching/UTest.java
> trunk/apps/freenet-caching/UniformRequestGenerator.java
> trunk/apps/freenet-caching/ZipfRequestGenerator.java
> Log:
> Caching simulations (LRU vs FIFO vs random replacement).
>
>
> Added: trunk/apps/freenet-caching/CachingSim.java
> ===================================================================
> --- trunk/apps/freenet-caching/CachingSim.java
> (rev
0)
> +++ trunk/apps/freenet-caching/CachingSim.java 2008-05-23 21:58:34 UTC
> (rev
20085)
> @@ -0,0 +1,141 @@
> +// This software has been placed in the public domain by its author
> +
> +import java.lang.reflect.Field;
> +import java.util.ArrayList;
> +import java.util.HashSet;
> +
> +class CachingSim
> +{
> + public static int NODES = 1000, DEGREE = 20, KEYS = 200000;
> +
> + ArrayList<Node> nodes;
> + RequestGenerator requests;
> +
> + CachingSim()
> + {
> + nodes = new ArrayList<Node> (NODES);
> + for (int i = 0; i < NODES; i++) nodes.add (Node.create());
> + makeKleinbergNetwork();
> + ArrayList<Double> keys = new ArrayList<Double> (KEYS);
> + for (int i = 0; i < KEYS; i++) keys.add (Math.random());
> + requests = RequestGenerator.create();
> + requests.init (keys);
> + storeKeys (keys);
> + }
> +
> + void run()
> + {
> + double success = 0.0, depth = 0.0, cost = 0.0;
> + // Request each key 100 times
> + for (int i = 0; i < KEYS * 100; i++) {
> + // Reset the counters halfway through the simulation
> + if (i == KEYS * 50) success = depth = cost = 0.0;
> + int random = (int) (Math.random() * nodes.size());
> + Node node = nodes.get (random);
> + double key = requests.generateRequest();
> + HashSet<Node> visited = new HashSet<Node>();
> + int d = node.request (key, 0, visited);
> + if (d != -1) {
> + success++; // Success rate should be close to 1
> + depth += d; // Depth of successful searches
> + cost += visited.size() - 1; // Bandwidth cost
> + }
> + }
> + System.out.println (
> + success / (KEYS * 50) + " " +
> + depth / success + " " +
> + cost / success
> + );
> + }
> +
> + void makeKleinbergNetwork()
> + {
> + for (Node a : nodes) {
> + // Normalise the probabilities
> + double norm = 0.0;
> + for (Node b : nodes) {
> + if (a.loc == b.loc) continue;
> + norm += 1.0 / distance (a.loc, b.loc);
> + }
> + // Create DEGREE/2 outgoing connections
> + for (Node b : nodes) {
> + if (a.loc == b.loc) continue;
> + double p = 1.0 / distance (a.loc, b.loc) / norm;
> + for (int i = 0; i < DEGREE / 2; i++) {
> + if (Math.random() < p) {
> + a.neighbours.add (b);
> + b.neighbours.add (a);
> + break;
> + }
> + }
> + }
> + }
> + }
> +
> + static double distance (double x, double y)
> + {
> + if (x > y) return Math.min (x - y, y - x + 1.0);
> + else return Math.min (y - x, x - y + 1.0);
> + }
> +
> + // Store each key permanently on the node nearest its location
> + void storeKeys (ArrayList<Double> keys)
> + {
> + for (double key : keys) {
> + double bestDistance = Double.POSITIVE_INFINITY;
> + Node bestNode = null;
> + for (Node node : nodes) {
> + double distance = distance (node.loc, key);
> + if (distance < bestDistance) {
> + bestDistance = distance;
> + bestNode = node;
> + }
> + }
> + bestNode.store.add (key);
> + }
> + }
> +
> + public static void main (String[] args)
> + {
> + // Command line args are used to set static values by reflection
> + try {
> + for (String arg : args) {
> + // Arguments are in the form class.field=value
> + String[] cfv = arg.split ("=");
> + String[] cf = cfv[0].split ("\\.");
> + Class c = Class.forName (cf[0]);
> + Field f = c.getField (cf[1]);
> + String v = cfv[1];
> + // Determine the type and parse the value
> + Class type = f.getType();
> + if (type == Boolean.TYPE) {
> + boolean b = Boolean.parseBoolean (v);
> + f.setBoolean (null, b);
> + }
> + else if (type == Double.TYPE) {
> + double d = Double.parseDouble (v);
> + f.setDouble (null, d);
> + }
> + else if (type == Integer.TYPE) {
> + int i = Integer.parseInt (v);
> + f.setInt (null, i);
> + }
> + else if (type == Class.class) {
> + ClassLoader cl
> + = ClassLoader.getSystemClassLoader();
> + f.set (null, cl.loadClass (v));
> + }
> + }
> + }
> + catch (Exception e) {
> + System.err.println (e);
> + System.exit (1);
> + }
> + // Print the arguments so we can tell the output files apart
> + System.out.print ("# args:");
> + for (String arg : args) System.out.print (" " + arg);
> + System.out.println();
> + // Run the simulation
> + new CachingSim().run();
> + }
> +}
>
> Added: trunk/apps/freenet-caching/FifoNode.java
> ===================================================================
> --- trunk/apps/freenet-caching/FifoNode.java (rev 0)
> +++ trunk/apps/freenet-caching/FifoNode.java 2008-05-23 21:58:34 UTC (rev
20085)
> @@ -0,0 +1,32 @@
> +// This software has been placed in the public domain by its author
> +
> +import java.util.LinkedHashMap;
> +import java.util.Map;
> +
> +class FifoNode extends Node
> +{
> + FifoMap<Double,Double> cache = new FifoMap<Double,Double>();
> +
> + boolean cacheGet (double key)
> + {
> + return cache.containsKey (key);
> + }
> +
> + void cachePut (double key)
> + {
> + cache.put (key, null);
> + }
> +
> + class FifoMap<Key,Value> extends LinkedHashMap<Key,Value>
> + {
> + FifoMap()
> + {
> + super (CACHE_SIZE, 0.75f, false);
> + }
> +
> + protected boolean removeEldestEntry (Map.Entry<Key,Value> entry)
> + {
> + return size() > CACHE_SIZE;
> + }
> + }
> +}
>
> Added: trunk/apps/freenet-caching/LruNode.java
> ===================================================================
> --- trunk/apps/freenet-caching/LruNode.java (rev 0)
> +++ trunk/apps/freenet-caching/LruNode.java 2008-05-23 21:58:34 UTC (rev
20085)
> @@ -0,0 +1,33 @@
> +// This software has been placed in the public domain by its author
> +
> +import java.util.LinkedHashMap;
> +import java.util.Map;
> +
> +class LruNode extends Node
> +{
> + LruMap<Double,Double> cache = new LruMap<Double,Double>();
> +
> + boolean cacheGet (double key)
> + {
> + // Use get() rather than containsKey() to update the LRU order
> + return cache.get (key) != null;
> + }
> +
> + void cachePut (double key)
> + {
> + cache.put (key, key);
> + }
> +
> + class LruMap<Key,Value> extends LinkedHashMap<Key,Value>
> + {
> + LruMap()
> + {
> + super (CACHE_SIZE, 0.75f, true);
> + }
> +
> + protected boolean removeEldestEntry (Map.Entry<Key,Value> entry)
> + {
> + return size() > CACHE_SIZE;
> + }
> + }
> +}
>
> Added: trunk/apps/freenet-caching/Node.java
> ===================================================================
> --- trunk/apps/freenet-caching/Node.java (rev 0)
> +++ trunk/apps/freenet-caching/Node.java 2008-05-23 21:58:34 UTC (rev
> 20085)
> @@ -0,0 +1,65 @@
> +// This software has been placed in the public domain by its author
> +
> +import java.util.ArrayList;
> +import java.util.Collections;
> +import java.util.Comparator;
> +import java.util.HashSet;
> +
> +abstract class Node implements Comparator<Node>
> +{
> + public static int CACHE_SIZE = 1000, MAX_DEPTH = 10;
> + public static Class CLASS = null; // Factory class
> +
> + // Factory method
> + static Node create()
> + {
> + try {
> + return (Node) CLASS.newInstance();
> + }
> + catch (Exception e) {
> + System.err.println (e);
> + System.exit (2);
> + return null;
> + }
> + }
> +
> + double loc = Math.random(), target = 0.0;
> + HashSet<Node> neighbours = new HashSet<Node>();
> + HashSet<Double> store = new HashSet<Double>();
> +
> + abstract boolean cacheGet (double key);
> + abstract void cachePut (double key);
> +
> + // Return the depth at which the request succeeded, or -1 if it failed
> + int request (double key, int depth, HashSet<Node> visited)
> + {
> + if (!visited.add (this)) return -1; // Loop
> + if (cacheGet (key) || store.contains (key)) return depth;
> + if (depth == MAX_DEPTH) return -1; // DNF
> + target = key; // Sort neighbours by closeness to requested key
> + ArrayList<Node> nbrs = new ArrayList<Node> (neighbours);
> + Collections.sort (nbrs, this);
> + for (Node n : nbrs) {
> + int d = n.request (key, depth + 1, visited);
> + if (d != -1) {
> + cachePut (key);
> + return d;
> + }
> + }
> + return -1; // RNF
> + }
> +
> + public int compare (Node n1, Node n2)
> + {
> + double d1 = CachingSim.distance (n1.loc, target);
> + double d2 = CachingSim.distance (n2.loc, target);
> + if (d1 < d2) return -1;
> + if (d1 > d2) return 1;
> + return 0;
> + }
> +
> + public boolean equals (Node n1, Node n2)
> + {
> + return compare (n1, n2) == 0;
> + }
> +}
>
> Added: trunk/apps/freenet-caching/RandomNode.java
> ===================================================================
> --- trunk/apps/freenet-caching/RandomNode.java
> (rev
0)
> +++ trunk/apps/freenet-caching/RandomNode.java 2008-05-23 21:58:34 UTC
> (rev
20085)
> @@ -0,0 +1,24 @@
> +// This software has been placed in the public domain by its author
> +
> +class RandomNode extends Node
> +{
> + double[] cache = new double[CACHE_SIZE];
> + double salt = Math.random();
> +
> + boolean cacheGet (double key)
> + {
> + return cache[hash (key)] == key;
> + }
> +
> + void cachePut (double key)
> + {
> + cache[hash (key)] = key;
> + }
> +
> + int hash (double key)
> + {
> + // Throw away the low-order bits because Math.random() sucks
> + long bits = Double.doubleToLongBits (key + salt) >> 8;
> + return (int) (bits & 0x7FFFFFFF) % CACHE_SIZE;
> + }
> +}
>
> Added: trunk/apps/freenet-caching/RequestGenerator.java
> ===================================================================
> --- trunk/apps/freenet-caching/RequestGenerator.java
(rev 0)
> +++ trunk/apps/freenet-caching/RequestGenerator.java 2008-05-23 21:58:34 UTC
(rev 20085)
> @@ -0,0 +1,80 @@
> +// This software has been placed in the public domain by its author
> +
> +import java.util.ArrayList;
> +import java.util.TreeSet;
> +
> +abstract class RequestGenerator
> +{
> + public static Class CLASS = null; // Factory class
> +
> + TreeSet<Request> queue = new TreeSet<Request>();
> + double now = 0.0;
> +
> + // Factory method
> + static RequestGenerator create()
> + {
> + try {
> + return (RequestGenerator) CLASS.newInstance();
> + }
> + catch (Exception e) {
> + System.err.println (e);
> + System.exit (2);
> + return null;
> + }
> + }
> +
> + // Schedule the first request for each key
> + void init (ArrayList<Double> keys)
> + {
> + for (int i = 0, size = keys.size(); i < size; i++) {
> + double rate = requestRate();
> + double time = now - Math.log (Math.random()) / rate;
> + queue.add (new Request (keys.get (i), rate, time));
> + }
> + }
> +
> + // Return the rate at which a given key will be requested
> + abstract double requestRate();
> +
> + // Return a key and schedule the next request for that key
> + double generateRequest()
> + {
> + Request r = queue.first();
> + queue.remove (r);
> + now = r.time;
> + double time = now - Math.log (Math.random()) / r.rate;
> + queue.add (new Request (r.key, r.rate, time));
> + return r.key;
> + }
> +
> + class Request implements Comparable<Request>
> + {
> + final double key, rate, time;
> +
> + Request (double key, double rate, double time)
> + {
> + this.key = key;
> + this.rate = rate;
> + this.time = time;
> + }
> +
> + // Must be consistent with compareTo()
> + public boolean equals (Request r)
> + {
> + return key == r.key && rate == r.rate && time == r.time;
> + }
> +
> + // Must be consistent with equals()
> + public int compareTo (Request r)
> + {
> + if (time < r.time) return -1;
> + if (time > r.time) return 1;
> + // Arbitrarily break ties using rate, then key
> + if (rate < r.rate) return -1;
> + if (rate > r.rate) return 1;
> + if (key < r.key) return -1;
> + if (key > r.key) return 1;
> + return 0;
> + }
> + }
> +}
>
> Added: trunk/apps/freenet-caching/UTest.java
> ===================================================================
> --- trunk/apps/freenet-caching/UTest.java (rev 0)
> +++ trunk/apps/freenet-caching/UTest.java 2008-05-23 21:58:34 UTC (rev
20085)
> @@ -0,0 +1,184 @@
> +// This software has been placed in the public domain by its author
> +
> +import java.io.*;
> +import java.util.ArrayList;
> +import java.util.Collections;
> +
> +class UTest
> +{
> + static final double zCritical = 2.576; // P = 0.01, two-tailed
> + // static final double zCritical = 1.96; // P = 0.05, two-tailed
> +
> +
> + static final int SMALLER = -1, INCONCLUSIVE = 0, LARGER = 1;
> +
> + static void die (String message)
> + {
> + System.err.println (message);
> + System.exit (1);
> + }
> +
> + static ArrayList <Double> readFile (String filename)
> + {
> + ArrayList <Double> arr = new ArrayList <Double> ();
> + try {
> + BufferedReader in;
> + in = new BufferedReader (new FileReader (filename));
> + while (true) {
> + String s = in.readLine();
> + if (s == null) break;
> + arr.add (new Double (s));
> + }
> + in.close();
> + }
> + catch (FileNotFoundException fnf) {
> + die (filename + " not found");
> + }
> + catch (IOException io) {
> + die ("Error reading from " + filename);
> + }
> + catch (NumberFormatException nf) {
> + die ("Invalid data in " + filename);
> + }
> + return arr;
> + }
> +
> + // The method used here is explained at
> + // http://faculty.vassar.edu/lowry/ch11a.html
> + static int test (String f1, String f2)
> + {
> + ArrayList <Double> a = readFile (f1);
> + ArrayList <Double> b = readFile (f2);
> + int nA = a.size(), nB = b.size();
> + if (nA < 5 || nB < 5) {
> + System.err.println ("Too few samples for U test\n");
> + return INCONCLUSIVE;
> + }
> +
> + /*
> + // Calculate the total rank of each set (old method, O(n^2))
> + ArrayList <Double> merged = new ArrayList <Double> (nA + nB);
> + merged.addAll (a);
> + merged.addAll (b);
> + Collections.sort (merged);
> + double tA = 0.0, tB = 0.0;
> + for (double x : a) {
> + int lessThan = 0, equalTo = 0;
> + for (double y : merged) {
> + if (y < x) lessThan++;
> + else if (y == x) equalTo++;
> + else break;
> + }
> + tA += lessThan + (equalTo + 1) / 2.0;
> + }
> + for (double x : b) {
> + int lessThan = 0, equalTo = 0;
> + for (double y : merged) {
> + if (y < x) lessThan++;
> + else if (y == x) equalTo++;
> + else break;
> + }
> + tB += lessThan + (equalTo + 1) / 2.0;
> + }
> + System.out.println ("Old method: " + tA + " " + tB);
> + */
> +
> + // Calculate the total rank of each set (new method, O(n log n))
> + double tA = 0.0, tB = 0.0;
> + Collections.sort (a);
> + Collections.sort (b);
> + int iA = 0, iB = 0, lessThan = 0;
> + while (iA < nA || iB < nB) {
> + int ties = 0, tieRanks = 0;
> + double currA, currB;
> + if (iA < nA) currA = a.get (iA);
> + else currA = Double.POSITIVE_INFINITY;
> + if (iB < nB) currB = b.get (iB);
> + else currB = Double.POSITIVE_INFINITY;
> + // If there are no more bs or next a is less than next b
> + if (currA < currB) {
> + // Count ties in a
> + while (iA + ties < nA &&
> + a.get (iA + ties) == currA) {
> + ties++;
> + tieRanks += ties;
> + }
> + // Increase a's total rank and update the index
> + tA += tieRanks + ties * lessThan;
> + iA += ties;
> + }
> + // Same the other way round
> + else if (currA > currB) {
> + // Count ties in b
> + while (iB + ties < nB &&
> + b.get (iB + ties) == currB) {
> + ties++;
> + tieRanks += ties;
> + }
> + // Increase b's total rank and update the index
> + tB += tieRanks + ties * lessThan;
> + iB += ties;
> + }
> + // Next a equal to next b: this is the tricky one
> + else {
> + int tiesA = 0, tiesB = 0;
> + // Count ties in a
> + while (iA + tiesA < nA &&
> + a.get (iA + tiesA) == currA) {
> + tiesA++;
> + ties++;
> + tieRanks += ties;
> + }
> + // Count ties in b
> + while (iB + tiesB < nB &&
> + b.get (iB + tiesB) == currB) {
> + tiesB++;
> + ties++;
> + tieRanks += ties;
> + }
> + double mean = tieRanks / (double) ties;
> + // Increase a's total rank and update the index
> + tA += tiesA * (mean + lessThan);
> + iA += tiesA;
> + // Increase b's total rank and update the index
> + tB += tiesB * (mean + lessThan);
> + iB += tiesB;
> + }
> + lessThan += ties;
> + }
> +
> + // The standard deviation of both total ranks is the same
> + double sigma = Math.sqrt (nA * nB * (nA + nB + 1.0) / 12.0);
> + // Means of the distributions of the total ranks
> + double muA = nA * (nA + nB + 1.0) / 2.0;
> + double muB = nB * (nA + nB + 1.0) / 2.0;
> + // Z scores
> + double zA, zB;
> + if (tA > muA) zA = (tA - muA - 0.5) / sigma;
> + else zA = (tA - muA + 0.5) / sigma;
> + if (tB > muB) zB = (tB - muB - 0.5) / sigma;
> + else zB = (tB - muB + 0.5) / sigma;
> +
> + if (zA > zCritical) return LARGER;
> + else if (zB > zCritical) return SMALLER;
> + else return INCONCLUSIVE;
> + }
> +
> + public static void main (String[] args)
> + {
> + if (args.length != 2) die ("usage: UTest <file1> <file2>");
> + switch (test (args[0], args[1])) {
> + case SMALLER:
> + System.out.println (args[0] + " is smaller");
> + break;
> +
> + case INCONCLUSIVE:
> + System.out.println ("No significant difference");
> + break;
> +
> + case LARGER:
> + System.out.println (args[0] + " is larger");
> + break;
> + }
> + }
> +}
>
> Added: trunk/apps/freenet-caching/UniformRequestGenerator.java
> ===================================================================
> --- trunk/apps/freenet-caching/UniformRequestGenerator.java
>
(rev 0)
> +++ trunk/apps/freenet-caching/UniformRequestGenerator.java 2008-05-23
21:58:34 UTC (rev 20085)
> @@ -0,0 +1,9 @@
> +// This software has been placed in the public domain by its author
> +
> +class UniformRequestGenerator extends RequestGenerator
> +{
> + double requestRate()
> + {
> + return 1.0; // All keys are requested at the same rate
> + }
> +}
>
> Added: trunk/apps/freenet-caching/ZipfRequestGenerator.java
> ===================================================================
> --- trunk/apps/freenet-caching/ZipfRequestGenerator.java
>
(rev 0)
> +++ trunk/apps/freenet-caching/ZipfRequestGenerator.java 2008-05-23
> 21:58:34
UTC (rev 20085)
> @@ -0,0 +1,9 @@
> +// This software has been placed in the public domain by its author
> +
> +class ZipfRequestGenerator extends RequestGenerator
> +{
> + double requestRate()
> + {
> + return 1.0 / Math.random(); // Zipf distribution
> + }
> +}
>
> _______________________________________________
> 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/20080805/3873f821/attachment.pgp>
