Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
- public class Stupid {
- public static void run() {
- for(int N = 32; N<=1048576;N*=2) {
- int[] x = new int[N];
- Random rand = new Random();
- for(int k = 0;k < N; ++k) x[k]=rand.nextInt();
- Arrays.sort(x);
- HashSet<Integer> hs = new HashSet<Integer>();
- for(int k = 0;k < N; ++k) hs.add(x[k]);
- TreeSet<Integer> ts = new TreeSet<Integer>();
- for(int k = 0;k < N; ++k) ts.add(x[k]);
- IntOpenHashSet ohs = new IntOpenHashSet();
- for(int k = 0; k < N; ++k) ohs.add(x[k]);
- int howmanyqueries = 1000000;
- int[] whichvalues = new int[howmanyqueries];
- for(int k = 0;k<howmanyqueries; ++k)
- whichvalues[k] = rand.nextInt();
- long aft1 = System.currentTimeMillis();
- for(int t=1;t<10;++t) for(int wv : whichvalues) Arrays.binarySearch(x,wv);
- long aft2 = System.currentTimeMillis();
- for(int t=1;t<10;++t) for(int wv : whichvalues) hs.contains(wv);
- long aft3 = System.currentTimeMillis();
- for(int t=1;t<10;++t) for(int wv : whichvalues) ts.contains(wv);
- long aft4 = System.currentTimeMillis();
- for(int t=1;t<10;++t) for(int wv : whichvalues) ohs.contains(wv);
- long aft5 = System.currentTimeMillis();
- System.out.println(N+" "+(aft2-aft1)/(1000.0*howmanyqueries)+ " "+(aft3-aft2)/(1000.0*howmanyqueries)+ " "+(aft4-aft3)/(1000.0*howmanyqueries) + " "+(aft5-aft4)/(1000.0*howmanyqueries));
- }
- }
- public static void main(String [] a) {
- run();
- }
- }
- /*
- * 32 2.66E-7 3.62E-7 4.68E-7 2.71E-7
- 64 3.55E-7 3.77E-7 6.01E-7 3.29E-7
- 128 4.31E-7 3.83E-7 6.7E-7 2.83E-7
- 256 4.67E-7 3.63E-7 7.25E-7 2.96E-7
- 512 5.6E-7 4.05E-7 8.38E-7 2.66E-7
- 1024 5.79E-7 3.76E-7 9.37E-7 2.63E-7
- 2048 6.31E-7 3.8E-7 1.049E-6 2.62E-7
- 4096 6.71E-7 4.99E-7 1.418E-6 3.03E-7
- 8192 8.06E-7 4.53E-7 1.609E-6 2.65E-7
- 16384 8.12E-7 4.81E-7 1.913E-6 2.79E-7
- 32768 9.14E-7 6.43E-7 2.541E-6 2.85E-7
- 65536 1.025E-6 9.12E-7 4.414E-6 3.06E-7
- 131072 1.497E-6 1.362E-6 6.515E-6 3.4E-7
- 262144 1.703E-6 1.727E-6 8.585E-6 3.67E-7
- 524288 2.155E-6 1.828E-6 1.0578E-5 5.51E-7
- 1048576 2.867E-6 1.998E-6 1.2602E-5 7.88E-7
- */
Add Comment
Please, Sign In to add comment