Author: mrogers
Date: 2008-05-23 21:57:16 +0000 (Fri, 23 May 2008)
New Revision: 20083
Removed:
trunk/apps/CachingSim.java
trunk/apps/FifoNode.java
trunk/apps/LruNode.java
trunk/apps/Node.java
trunk/apps/RandomNode.java
trunk/apps/UTest.java
trunk/apps/UniformRequestGenerator.java
trunk/apps/ZipfRequestGenerator.java
Log:
Argh.
Deleted: trunk/apps/CachingSim.java
===================================================================
--- trunk/apps/CachingSim.java 2008-05-23 21:53:30 UTC (rev 20082)
+++ trunk/apps/CachingSim.java 2008-05-23 21:57:16 UTC (rev 20083)
@@ -1,141 +0,0 @@
-// 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();
- }
-}
Deleted: trunk/apps/FifoNode.java
===================================================================
--- trunk/apps/FifoNode.java 2008-05-23 21:53:30 UTC (rev 20082)
+++ trunk/apps/FifoNode.java 2008-05-23 21:57:16 UTC (rev 20083)
@@ -1,32 +0,0 @@
-// 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;
- }
- }
-}
Deleted: trunk/apps/LruNode.java
===================================================================
--- trunk/apps/LruNode.java 2008-05-23 21:53:30 UTC (rev 20082)
+++ trunk/apps/LruNode.java 2008-05-23 21:57:16 UTC (rev 20083)
@@ -1,33 +0,0 @@
-// 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;
- }
- }
-}
Deleted: trunk/apps/Node.java
===================================================================
--- trunk/apps/Node.java 2008-05-23 21:53:30 UTC (rev 20082)
+++ trunk/apps/Node.java 2008-05-23 21:57:16 UTC (rev 20083)
@@ -1,65 +0,0 @@
-// 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;
- }
-}
Deleted: trunk/apps/RandomNode.java
===================================================================
--- trunk/apps/RandomNode.java 2008-05-23 21:53:30 UTC (rev 20082)
+++ trunk/apps/RandomNode.java 2008-05-23 21:57:16 UTC (rev 20083)
@@ -1,24 +0,0 @@
-// 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;
- }
-}
Deleted: trunk/apps/UTest.java
===================================================================
--- trunk/apps/UTest.java 2008-05-23 21:53:30 UTC (rev 20082)
+++ trunk/apps/UTest.java 2008-05-23 21:57:16 UTC (rev 20083)
@@ -1,184 +0,0 @@
-// 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;
- }
- }
-}
Deleted: trunk/apps/UniformRequestGenerator.java
===================================================================
--- trunk/apps/UniformRequestGenerator.java 2008-05-23 21:53:30 UTC (rev
20082)
+++ trunk/apps/UniformRequestGenerator.java 2008-05-23 21:57:16 UTC (rev
20083)
@@ -1,9 +0,0 @@
-// 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
- }
-}
Deleted: trunk/apps/ZipfRequestGenerator.java
===================================================================
--- trunk/apps/ZipfRequestGenerator.java 2008-05-23 21:53:30 UTC (rev
20082)
+++ trunk/apps/ZipfRequestGenerator.java 2008-05-23 21:57:16 UTC (rev
20083)
@@ -1,9 +0,0 @@
-// 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
- }
-}
