Making a hash of data   The danger of big-O notation

How not to shuffle a list

A frequent thing that people want to do in making games or interactive applications is to shuffle a list. One common and intuitive approach that people take is to simply sort the list, but use a random number generator as the comparison operation. (For example, this is what’s recommended in Fuzzball’s MPI documentation, and it is a common answer that comes up on programming forums as well.)

This way is very, very wrong.

First, there are two approaches which work really well that I’ll describe briefly; one is the Fisher-Yates shuffle algorithm, which works by walking down the array and randomly swapping the current element with any of the elements which follow it (including itself). This is an \(\mathcal{O}(N)\) operation which is trivial to implement in pretty much any imperative language and can be done in-place.

If you are in an environment which does not allow array-level swapping like that (such as, say, a functional programming language or a spreadsheet), an alternate approach is to map the array to one where each element is prefixed with a random number, then sort based on that Random prefix, and then remove the prefix. Here is how to do it in Excel, and how to do it in Fuzzball MPI. This generally is an \(\mathcal{O}(N \log_2 N)\) operation: not as efficient, but it still generates high-quality results.

But why are these approaches better? Well, both of them have an equal chance of any input cell ending up in any output cell; there is absolutely no bias to where things might end up, because all of their placements are independent from one another, and each placement happens effectively once.

But the coin-flip sorting approach introduces a lot of bias; cells can move an arbitrary number of times, and where they can move to depends on where they are located within the array to begin with.

So, let’s measure this bias using a \(\chi^2\) test.

Briefly, \(\chi^2\) measures how close your output distribution is to an expected distribution. If we were shuffling our lists uniformly, then we’d expect every value to end up in every cell about the same number of times; for an array of length \(N\), with a shuffle repeated \(K\) times, you’d expect each value to be in each cell \(\frac{K}{N}\) times.

Here is what the \(\chi^2\) distribution is for the good algorithms, with \(N=235\) and \(K=100000\):

pick-235.pngprefix-235.png

And here it is for three different random-sort algorithms, bubble sort, std::stable_sort, and merge sort, all using a coin-toss ordering function:

sort_bubble-235.pngsort_std-235.pngsort_merge-235.png

(The reason I went with std::stable_sort instead of std::sort is that the latter uses some optimizations that assume that the sort is transitive – which isn’t the case when you’re randomly flipping a coin. So std::sort tends to crash when this constraint is violated.)

For a better comparison of how the different algorithms stack up as \(N\) changes, here’s a chart:

N Fisher-Yates Random prefix Bubble sort std::stable_sort Merge sort
4 0.00005 pick-4.png 0.00004 prefix-4.png 0.139569 sort_bubble-4.png 0.158157 sort_std-4.png 0.00004 sort_merge-4.png
5 0.00002 pick-5.png 0.00005 prefix-5.png 0.218803 sort_bubble-5.png 0.273358 sort_std-5.png 0.0487565 sort_merge-5.png
6 0.00006 pick-6.png 0.00008 prefix-6.png 0.29487 sort_bubble-6.png 0.400601 sort_std-6.png 0.0330905 sort_merge-6.png
7 0.0000 pick-7.png 0.00006 prefix-7.png 0.364549 sort_bubble-7.png 0.527574 sort_std-7.png 0.0342361 sort_merge-7.png
8 0.00006 pick-8.png 0.00006 prefix-8.png 0.430965 sort_bubble-8.png 0.660637 sort_std-8.png 0.00005 sort_merge-8.png
10 0.0001 pick-10.png 0.00010 prefix-10.png 0.557523 sort_bubble-10.png 0.93249 sort_std-10.png 0.0335068 sort_merge-10.png
12 0.000127262 pick-12.png 0.000108561 prefix-12.png 0.674842 sort_bubble-12.png 1.19897 sort_std-12.png 0.024186 sort_merge-12.png
15 0.000148504 pick-15.png 0.000128046 prefix-15.png 0.831853 sort_bubble-15.png 1.60815 sort_std-15.png 0.0178444 sort_merge-15.png
18 0.000186571 pick-18.png 0.000189251 prefix-18.png 0.971268 sort_bubble-18.png 2.01685 sort_std-18.png 0.0259307 sort_merge-18.png
22 0.000212744 pick-22.png 0.000221075 prefix-22.png 1.14734 sort_bubble-22.png 2.56097 sort_std-22.png 0.0321786 sort_merge-22.png
27 0.000249649 pick-27.png 0.000268954 prefix-27.png 1.34988 sort_bubble-27.png 3.24243 sort_std-27.png 0.0271932 sort_merge-27.png
33 0.000348344 pick-33.png 0.000328459 prefix-33.png 1.56487 sort_bubble-33.png 4.06064 sort_std-33.png 0.0116926 sort_merge-33.png
41 0.000417497 pick-41.png 0.000404196 prefix-41.png 1.82521 sort_bubble-41.png 5.1443 sort_std-41.png 0.0301371 sort_merge-41.png
51 0.000494652 pick-51.png 0.000514062 prefix-51.png 2.11672 sort_bubble-51.png 6.50646 sort_std-51.png 0.026951 sort_merge-51.png
63 0.000612439 pick-63.png 0.000614844 prefix-63.png 2.4303 sort_bubble-63.png 8.14154 sort_std-63.png 0.0057482 sort_merge-63.png
78 0.000753832 pick-78.png 0.000759035 prefix-78.png 2.7903 sort_bubble-78.png 10.1829 sort_std-78.png 0.0270242 sort_merge-78.png
97 0.000952913 pick-97.png 0.000986311 prefix-97.png 3.19424 sort_bubble-97.png 12.7711 sort_std-97.png 0.022091 sort_merge-97.png
121 0.0011958 pick-121.png 0.0012227 prefix-121.png 3.65048 sort_bubble-121.png 16.0263 sort_std-121.png 0.0137545 sort_merge-121.png
151 0.00147693 pick-151.png 0.0015004 prefix-151.png 4.16317 sort_bubble-151.png 2.2788 sort_std-151.png 0.026883 sort_merge-151.png
188 0.00185188 pick-188.png 0.00186338 prefix-188.png 4.7293 sort_bubble-188.png 2.72105 sort_std-188.png 0.0242407 sort_merge-188.png
235 0.00231242 pick-235.png 0.00233842 prefix-235.png 5.3744 sort_bubble-235.png 3.24268 sort_std-235.png 0.0189719 sort_merge-235.png

And here is a logarithmic graph showing how the total \(\chi^2\) error changes as \(N\) increases:

rand.svg

So, as N increases, you would expect the \(\chi^2\) to increase if \(K\) remains constant, as it did in this case (as there are fewer overlapping samples). And in fact the bubble sort and std::stable_sort approaches increase pretty much in parallel with the Fisher-Yates and random prefix approaches (aside from the discontinuity at \(N=128\) due to the performance-tuning heuristics that algorithm uses) – but this is in a logarithmic graph, meaning that the random sorts increase orders of magnitude faster than the other ones.

Merge sort is a bit interesting, in that it is highly dependent on the actual size of the array, and in particular how close it is to a power of 2, with perfect powers of 2 having the same \(\chi^2\) as the ideal algorithms. (I leave this as an exercise to the reader to consider why this would be.) But there’s still a lot of inherent bias, and it’s not even casually-predictable bias.

Anyway, this is why when shuffling a list, you should use Fisher-Yates if possible, or sort based on a randomly-generated unassociated number if not.

(Here is the rather ugly source code if you want to play with it yourself.)

Comments

Before commenting, please read the comment policy.

Avatars provided via Libravatar