Guest User

test.java

a guest
Jan 17th, 2012
605
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2. * By D. Lemire.
  3. */
  4.  
  5. import java.util.*;
  6. class test {
  7.     public static ArrayList<String> listofstrings(int lengthdividedby3) {
  8.         String[] allcollide = { "Ace","BDe","AdF","BEF"};
  9.         ArrayList<String> al = new ArrayList<String>();
  10.         al.add("");
  11.         if(lengthdividedby3 <= 0 ) return al;
  12.         int mask = 0xFFFF;
  13.         for(int k = 0; k<lengthdividedby3;++k) {
  14.             ArrayList<String> oldarray = al;
  15.             al = new ArrayList<String>();
  16.             for(String s : oldarray)
  17.               for(String t : allcollide)
  18.                 al.add(s+t);
  19.         }
  20.         System.out.println("generated "+al.size()+" ASCII strings of length "+al.get(0).length());
  21.         int expectedhashcode = al.get(0).hashCode() & mask;
  22.         for (String t: al)
  23.           if((t.hashCode() & mask)!= expectedhashcode) throw new RuntimeException("Got it wrong!");
  24.         System.out.println("... and they all collide (on first 16 bits)");       
  25.         return al;
  26.     }
  27.     static void testme(int lengthdividedby3) {
  28.         long bef, aft;
  29.         double average, worse;
  30.         ArrayList<String> x = listofstrings(lengthdividedby3);
  31.         {
  32.           System.out.println("testing how long it usually takes to add "+x.size()+" elements to a hash table");
  33.  
  34.           bef = System.currentTimeMillis();
  35.           Hashtable<String,Integer> testhash = new Hashtable<String,Integer>();
  36.           for(int k = 0; k< x.size();++k)
  37.             testhash.put(Integer.toString(k),1);
  38.           aft = System.currentTimeMillis();
  39.           average = (aft-bef)/1000.0;  
  40.           System.out.println("about "+average+" s");
  41.         }
  42.         {  
  43.           System.out.println("testing how long it usually takes to add "+x.size()+" elements to a hash table in our cooked up case");
  44.  
  45.             // now watch the hash table suffer!
  46.           bef = System.currentTimeMillis();
  47.             Hashtable<String,Integer> myhash = new Hashtable<String,Integer>();
  48.             for(String s : x)
  49.                 myhash.put(s,1);
  50.           aft = System.currentTimeMillis();
  51.           worse =   (aft-bef)/1000.0;
  52.           System.out.println("about "+worse+" s");
  53.         }
  54.         System.out.println("ratio = "+worse/average);      
  55.         {  
  56.           System.out.println("testing how long it usually takes to add "+x.size()+" elements to a tree in our cooked up case");
  57.  
  58.             // now watch the hash table suffer!
  59.           bef = System.currentTimeMillis();
  60.             TreeMap<String,Integer> myhash = new TreeMap<String,Integer>();
  61.             for(String s : x)
  62.                 myhash.put(s,1);
  63.           aft = System.currentTimeMillis();
  64.           double treetime =     (aft-bef)/1000.0;
  65.           System.out.println("about "+treetime+" s");
  66.         }
  67.         System.out.println();
  68.     }
  69.     static public void main(String[] args) {
  70.         testme(6);
  71.         testme(7);
  72.         testme(8);
  73.  
  74.         testme(6);
  75.         testme(7);
  76.         testme(8);
  77.  
  78.     }
  79. }
RAW Paste Data