Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>In order to ensure that the list doesn't repeat, it would have to keep a list of numbers previously returned. As it has to therefore generate the entire list by the end of the algorithm, this is equivalent in storage requirement to generating the ordered list and then shuffling.</p> <p>More about shuffling here: <a href="https://stackoverflow.com/questions/168037/creating-a-random-ordered-list-from-an-ordered-list">Creating a random ordered list from an ordered list</a></p> <p>However, if the range of the random numbers is very large but the quantity of numbers required is small (you've hinted that this is the actual requirement in a comment), then generate a complete list and shuffling it is wasteful. A shuffle on a huge array involves accessing pages of virtual memory in a way that (by definition) will defeat the OS's paging system (on a smaller scale the same problem would occur with the CPU's memory cache).</p> <p>In this case, searching the list-so-far will be much more efficient. So the ideal would be to use heuristics (determined by experiment) to pick the right implementation for the given arguments. (Apologies for giving examples in C# rather than C++ but <a href="http://www.earwicker.com/asfacppb.html" rel="nofollow noreferrer">ASFAC++B</a> I'm training myself to think in C#).</p> <pre><code>IEnumerable&lt;int&gt; GenerateRandomNumbers(int range, int quantity) { int[] a = new int[quantity]; if (range &lt; Threshold) { for (int n = 0; n &lt; range; n++) a[n] = n; Shuffle(a); } else { HashSet&lt;int&gt; used = new HashSet&lt;int&gt;(); for (int n = 0; n &lt; quantity; n++) { int r = Random(range); while (!used.Add(r)) r = Random(range); a[n] = r; } } return a; } </code></pre> <p>The cost of doing the checking for repeated numbers, the looping while there are collisions, etc. will be expensive, but there will likely be some <code>Threshold</code> value where it becomes faster than allocating for the entire range.</p> <p>For sufficiently small quantity requirements, it may be faster to use an array for <code>used</code> and do linear searches in it, due to the greater locality, lower overhead, the cheapness of the comparison...</p> <p>Also for large quantities AND large ranges, it might be preferable to return an object that produces the numbers in the sequence on request, instead of allocating the array for the results upfront. This is very easy to implement in C# thanks to the <code>yield return</code> keyword:</p> <pre><code>IEnumerable&lt;int&gt; ForLargeQuantityAndRange(int quantity, int range) { for (int n = 0; n &lt; quantity; n++) { int r = Random(range); while (!used.Add(r)) r = Random(range); yield return r; } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POCreate Random Number Sequence with No Repeats
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USDaniel Earwicker
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COCheck out random_shuffle in <algorithm> for a clean C++ implementation of the Knuth-Fisher-Yates shuffle, provided you've populated your list of values into a RandomAccessIterator compatible container.
      singulars
      1. PO
      1. USJeremy CD
    2. COThe first sentence is not true. A properly set up implementation of a linear feedback shift register will go through all the values in its range precisely once before it comes back to the beginning.
      singulars
      1. PO
      1. USSteve Melnikoff
    3. COYou're right, I'm assuming the source of randomness is a function taking the required range, which may be unnecessary. But I guess the problem with LFSR is scaling the output to a specified range without causing collisions?
      singulars
      1. PO
      1. USDaniel Earwicker
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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