title: Choosing random numbers efficiently
body: <p>I have a method, which uses random samples to approximate a calculation. This method is called millions of times, so its very important that the process of choosing the random numbers is efficient. </p>
  
  <p>I'm not sure how fast javas <code>Random().nextInt</code> really are, but my program does not seem to benefit as much as I would like it too. </p>
  
  <p>When choosing the random numbers, I do the following (in semi pseudo-code):</p>
  
  <pre><code>// Repeat this 300000 times
  Set set = new Set();
  while(set.length != 5)
      set.add(randomNumber(MIN,MAX));
  </code></pre>
  
  <p>Now, this obviously has a bad worst-case running time, as the random-function in theory can add duplicated numbers for an eternity, thus staying in the while-loop forever. However, the numbers are chosen from {0..45}, so a duplicated value is for the most part unlikely.</p>
  
  <p>When I use the above method, its only 40% faster than my other method, which does not approximate, but yields the correct result. This is ran ~ 1 million times, so I was expecting this new method to be at least 50% faster.</p>
  
  <p>Do you have any suggestions for a faster method? Or maybe you know of a more efficient way of generation a set of random numbers.</p>
  
  <p>To clarify, here is the two methods:</p>
  
  <pre><code>// Run through all combinations (1 million). This takes 5 seconds
   for(int c1 = 0; c1 &lt; deck.length; c1++){
      for(int c2 = c1+1; c2 &lt; deck.length; c2++){
       for(int c3 = c2+1; c3 &lt; deck.length; c3++){
          for(int c4 = c3+1; c4 &lt; deck.length; c4++){
           for(int c5 = c4+1; c5 &lt; deck.length; c5++){
               enumeration(hands, cards, deck, c1, c2, c3, c4, c5);
           }
              } 
        }     
     }
     }
  
  // Approximate (300000 combinations). This takes 3 seconds
  Random rand = new Random();
  HashSet&lt;Integer&gt; set = new HashSet&lt;Integer&gt;();
  int[] numbers = new int[5];
  while(enumerations &lt; 300000){
  set.clear();
  while(set.size() != 5){
      set.add(rand.nextInt(deck.length));
  }
  Iterator&lt;Integer&gt; i = set.iterator();
  int n = 0;
  while(i.hasNext()){
      numbers[n] = i.next();
      n++;
  }
  </code></pre>
  
  <p>After some testing and profiling, I found this method to be the most effective:</p>
  
  <pre><code>Random rand = new Random();
  int[] numbers = new int[5];
  ArrayList&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;();
  while(enumerations &lt; 300000){
   while(list.size() != 5) {
       int i = rand.nextInt(deck.length);
          if(!list.contains(i)) list.add(i);
   }
   int index = 0;
   for(int i : list){ numbers[index] = i; index++; }
   enumeration(hands, cards, deck,numbers);
  }
  </code></pre>