Guest User

comparing HashSet, TreeSet and a sorted array

a guest
May 20th, 2010
767
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class Stupid {
  4.    
  5.     public static void run() { 
  6.      for(int N = 32; N<=1048576;N*=2) {
  7.         int[] x = new int[N];
  8.         Random rand = new Random();
  9.         for(int k = 0;k < N; ++k) x[k]=rand.nextInt();
  10.         Arrays.sort(x);
  11.         HashSet<Integer> hs = new HashSet<Integer>();
  12.         for(int k = 0;k < N; ++k) hs.add(x[k]);
  13.         TreeSet<Integer> ts = new TreeSet<Integer>();
  14.         for(int k = 0;k < N; ++k) ts.add(x[k]);
  15.         int howmanyqueries = 1000000;
  16.         int[] whichvalues = new int[howmanyqueries];
  17.         for(int k = 0;k<howmanyqueries; ++k)
  18.           whichvalues[k] = rand.nextInt();
  19.         long aft1 = System.currentTimeMillis();
  20.         for(int t=1;t<10;++t) for(int wv : whichvalues) Arrays.binarySearch(x,wv);
  21.         long aft2 = System.currentTimeMillis();
  22.         for(int t=1;t<10;++t) for(int wv : whichvalues) hs.contains(wv);
  23.         long aft3 = System.currentTimeMillis();
  24.         for(int t=1;t<10;++t) for(int wv : whichvalues) ts.contains(wv);
  25.         long aft4 = System.currentTimeMillis();
  26.         System.out.println(N+" "+(aft2-aft1)/(1000.0*howmanyqueries)+ " "+(aft3-aft2)/(1000.0*howmanyqueries)+ " "+(aft4-aft3)/(1000.0*howmanyqueries));
  27.      }
  28.     }
  29.    
  30.     public static void main(String [] a) {
  31.         run();
  32.     }
  33. }
RAW Paste Data