Databases
StackOverflow2013
Postsdbo
PORandom sample from a large population runs into infinite loop
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PORandom sample from a large population runs into infinite loop
    text
    copied!<p>I want to draw n samples from a relatively large population without replacement. So I draw random numbers and keep track of my previous choices, so I can resample whenever I drew a number twice:</p> <pre><code>boost::mt19937 generator; boost::uniform_int&lt;&gt; distribution(0, 1669 - 1); boost::variate_generator&lt;boost::mt19937, boost::uniform_int&lt;&gt; &gt; gen(generator, distribution); int n = 100; std::vector&lt;int&gt; idxs; while(static_cast&lt;int&gt;(idxs.size()) &lt; n) { // get random samples std::generate_n(std::back_inserter(idxs), n - idxs.size(), gen); // remove duplicates // keep everything that's not duplicates to save time std::sort(idxs.begin(), idxs.end()); std::vector&lt;int&gt;::iterator it = std::unique(idxs.begin(), idxs.end()); idxs.resize(std::distance(idxs.begin(), it)); } </code></pre> <p>Unfortunately, I run into an infinite loop for the constants used above.</p> <p>I added some output (that shows that it keeps picking the same number) and stopping after 10 tries for showing the problem:</p> <pre><code>boost::mt19937 generator; boost::uniform_int&lt;&gt; distribution(0, 1669 - 1); boost::variate_generator&lt;boost::mt19937, boost::uniform_int&lt;&gt; &gt; gen(generator, distribution); int n = 100; int repeat = 0; std::vector&lt;int&gt; idxs; while(static_cast&lt;int&gt;(idxs.size()) &lt; n) { if(repeat++ &gt; 10) break; cout &lt;&lt; "repeat " &lt;&lt; repeat &lt;&lt; ", " &lt;&lt; idxs.size() &lt;&lt; " elements" &lt;&lt; endl; std::generate_n(std::back_inserter(idxs), n - idxs.size(), gen); cout &lt;&lt; "last " &lt;&lt; idxs.back() &lt;&lt; endl; std::sort(idxs.begin(), idxs.end()); std::vector&lt;int&gt;::iterator it = std::unique(idxs.begin(), idxs.end()); idxs.resize(std::distance(idxs.begin(), it)); } </code></pre> <p>The code prints</p> <pre><code>repeat 1, 0 elements last 1347 repeat 2, 99 elements last 1359 repeat 3, 99 elements last 1359 </code></pre> <p>and so on, and this seems to loop forever if I don't kill the program. This shouldn't happen, right? Am I just unlucky? Or am I doing something wrong?</p> <p><strong>short solution</strong> Thanks to @jxh! Using a reference helps:</p> <pre><code>boost::variate_generator&lt;boost::mt19937&amp;, boost::uniform_int&lt;&gt; &gt; gen(generator, distribution); </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload