StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>An alternative solution is to kind-of combine methods (1) and (3):</p> <p>(For a reference see the "The modern algorithm" section of <a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" rel="nofollow">http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle</a>.)</p> <ul> <li>Iterate an index <code>i</code> from <code>n</code> down to <code>1</code> (using 1-based indexing).</li> <li>At each step, pick a random number <code>m</code> between <code>1</code> and <code>i</code>.</li> <li>Insert the element of the array at index <code>m</code> to the front of the linked list. (We will build the list back-to-front, although actually it makes no difference if you decide to insert entries at the back of the list instead. Building back-to-front lets you avoid keeping track of a pointer to the back of the list, to avoid <code>O(n)</code> insertion time resulting from scanning to the end at each step.)</li> <li>Move the element of the array at index <code>i</code> to the slot at index <code>m</code>.</li> </ul> <p>This avoids a small amount of the overhead of an in-place shuffle, avoids the memory overhead of generating an array of indices, and avoids a complicated in-place shuffle of a linked list associated with method (2). It runs in <code>O(n)</code> time, using <code>O(1)</code> extra memory (ignoring the memory used for the original array and the linked list).</p> <p><strong>Edit:</strong> I think actually that the algorithm I describe above should be the easiest to implement by-hand out of the three options you have. Unless your array is very big the real-life run-time and memory-usage differences of the options you have will probably be negligible.</p> <p>If the sizes of the entries in the array are indeed quite large, this algorithm suffers from the same problem as an in-place shuffle does, namely having to move big data sets around, and in this case probably generating a list of indices is better.</p>

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