Guest User

Untitled

a guest
Jul 11th, 2012
1,425
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.awt.Point;
  2. import java.io.*;
  3. import java.math.BigInteger;
  4. import java.util.*;
  5. import static java.lang.Math.*;
  6.  
  7. public class AntiHashSetGenerator implements Runnable {
  8.  
  9.     BufferedReader in;
  10.     PrintWriter out;
  11.     StringTokenizer tok = new StringTokenizer("");
  12.  
  13.     public static void main(String[] args) {
  14.         new Thread(null, new AntiHashSetGenerator(), "", 256 * (1L << 20)).start();
  15.     }
  16.  
  17.     public void run() {
  18.         try {
  19.             long t1 = System.currentTimeMillis();
  20.             if (System.getProperty("ONLINE_JUDGE") != null) {
  21.                 in = new BufferedReader(new InputStreamReader(System.in));
  22.                 out = new PrintWriter(System.out);
  23.             } else {
  24.                 in = new BufferedReader(new FileReader("input.txt"));
  25.                 out = new PrintWriter("output.txt");
  26.             }
  27.             Locale.setDefault(Locale.US);
  28.             solve();
  29.             in.close();
  30.             out.close();
  31.             long t2 = System.currentTimeMillis();
  32.             System.err.println("Time = " + (t2 - t1));
  33.         } catch (Throwable t) {
  34.             t.printStackTrace(System.err);
  35.             System.exit(-1);
  36.         }
  37.     }
  38.  
  39.     String readString() throws IOException {
  40.         while (!tok.hasMoreTokens()) {
  41.             tok = new StringTokenizer(in.readLine());
  42.         }
  43.         return tok.nextToken();
  44.     }
  45.  
  46.     int readInt() throws IOException {
  47.         return Integer.parseInt(readString());
  48.     }
  49.  
  50.     long readLong() throws IOException {
  51.         return Long.parseLong(readString());
  52.     }
  53.  
  54.     double readDouble() throws IOException {
  55.         return Double.parseDouble(readString());
  56.     }
  57.  
  58.     // solution
  59.  
  60.     int hashinv(int h) {
  61.         h ^= (h >>> 4) ^ (h >>> 7) ^ (h >>> 8) ^ (h >>> 14) ^ (h >>> 15)
  62.                 ^ (h >>> 18) ^ (h >>> 19) ^ (h >>> 20) ^ (h >>> 21)
  63.                 ^ (h >>> 23) ^ (h >>> 26) ^ (h >>> 28);
  64.         return h;
  65.     }
  66.  
  67.     int bitreverse(int h) {
  68.         int res = 0;
  69.         for (int i = 0; i < 31; i++)
  70.             if ((h & (1 << i)) != 0)
  71.                 res |= (1 << (30 - i));
  72.         return res;
  73.     }
  74.  
  75.     void solve() throws IOException {
  76.         final int size = 100000;
  77.         int[] s = new int[size];
  78.         for (int i = 0, val = 0; i < size; i++) {
  79.             s[i] = Integer.MAX_VALUE;
  80.             while (s[i] > 1000000000)
  81.                 s[i] = hashinv(bitreverse(val++));
  82.         }
  83.  
  84. Arrays.sort(s);
  85. /*
  86. List<Integer> list = new ArrayList<Integer>();
  87. for (int i = 0; i < size; i++) list.add(s[i]);
  88. Collections.shuffle(list, new Random(System.currentTimeMillis()));
  89. for (int i = 0; i < size; i++) s[i] = list.get(i);
  90. */
  91.        
  92.         //out.println(size);
  93.         for (int i = 0; i < size; i++) {
  94.             //out.print(s[i]);
  95.             //if (i == size-1) out.println(); else o ut.print(' ');
  96.         }
  97.        
  98.         long startTime = System.currentTimeMillis();
  99.         HashSet<Integer> h = new HashSet<Integer>(size);
  100.         for (int i = 0; i < size; i++)
  101.             h.add(s[i]);
  102.         System.out.println("HashSet adding time = " + (System.currentTimeMillis() - startTime));
  103.     }
  104.  
  105. }
RAW Paste Data