title: How to optimize rejection sampling
body: <p>I have an std::map mymap that I am trying to sample based on the values for each key. I have set up an algorithm based on rejection sampling that seems to be working, however it is extremely slow (this algorithm gets called thousands of times in my program). </p>
  
  <p>So I am wondering if this would be the best approach or if there is something quicker/more efficient that I could be doing instead. </p>
  
  <p>Here is what I have so far below:</p>
  
  <pre><code>std::map&lt;int, float&gt; mymap; //My map that I am sampling
  
  //These three floats are precomputed
  int minKey;  //Min key in the map.  
  int maxKey;  //Max key in the map.  
  float maxValue; //Max value in the map.  
  
  float x1, x2; //Two random variables;
  int key;
  float value;
  do 
  {
      x1 = (float)rand()/(float)RAND_MAX;
      x2 = maxValue * (float)rand()/(float)RAND_MAX;
      key = minKey*(1.0-x1) + maxKey*x1; //Linearly interpolate random value to get key;
      value = mymap[key]; //Get value;
  } while(x2 &gt; value) 
  
  
  return std::pair&lt;int, float)(key, value);
  </code></pre>
  
  <p>^So what I am doing above is uniformly randomly selecting a key. Then creating another random variable and comparing it against that key's value. If it is larger, repeat the process. This way, keys with higher values get sampled more often than keys with lower values. However, the do-while loop can loop many times before finding an acceptable key-value pair to sample and this is causing quite the bottleneck in my application</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>Also, is it necessary for me to do any adjusting to my samples since they are biased here? I know that in monte carlo integration, you have to divide the value of the sample by the PDF of that sample...but I'm not sure if that would apply here. If it does apply, how would I find the PDF?</p>