Haha, yes I too checked Racket `shuffle` after I read that. But
`shuffle` is mathematically sound. (Was I really surprised?) It doesn't
use a random comparator. Rather, it assigns random *keys* to the
elements and then uses a standard `<` comparator, which preserves
transitivity (net of the nanoscopic chance of `random` returning the
same key twice).
I also verified this experimentally using Bostock's bias-correlation
technique. Here's Racket `shuffle` on a 10-card deck, shuffled a million
times (truly random shuffling will produce values close to zero):
+0.0037 -0.0037 +0.0107 -0.0087 +0.0049 +0.0432
-0.0306 +0.0025 -0.0319 +0.0099
-0.0589 +0.0066 +0.0295 -0.0337 -0.0308 +0.0288
-0.0106 +0.0375 +0.0202 +0.0114
-0.0191 +0.0381 -0.0308 -0.017 +0.0608 -0.0609
+0.0183 +0.0037 -0.0037 +0.0106
-0.0025 -0.0232 -0.0135 -0.0166 -0.0127 -0.0104
+0.0444 -0.0087 +0.0275 +0.0157
+0.0537 -0.0114 -0.0138 +0.0029 +0.0281 -0.0264
-0.0369 +0.0237 -0.0051 -0.0148
+0.0075 +0.0254 -0.0128 +0.048 +0.0309 -0.0053
-0.0055 -0.046 -0.0183 -0.0239
+0.0211 +0.005 -0.0162 +0.0326 -0.0019 -0.0062
-0.0423 -0.0036 +0.0501 -0.0386
+0.027 +0.0228 -0.0327 -0.001 -0.0256 +0.013 +0.0005
+0.0203 -0.0157 -0.0086
-0.0039 -0.059 +0.0769 -0.0294 -0.0045 +0.0046
+0.0121 -0.0035 -0.0344 +0.0411
-0.0286 -0.0006 +0.0027 +0.0229 -0.0492 +0.0196
+0.0506 -0.0259 +0.0113 -0.0028
And here's the evil random-comparator shuffle, which you write thus:
(sort l (λ(a b) (< (random) 0.5)) #:cache-keys? #t)
+5.5262 +5.3953 +0.2165 -4.1699 -6.8645 +5.3694
+5.3138 +0.2238 -4.1352 -6.8754
+5.3552 +5.5478 +0.2443 -4.1483 -6.8783 +5.2901
+5.3356 +0.3061 -4.1741 -6.8784
+4.0834 +4.0231 +1.1727 -3.128 -6.0845 +4.0658
+4.0908 +0.9624 -3.0706 -6.1151
+2.2696 +2.3085 +1.3081 -1.1473 -4.5383 +2.236
+2.1868 +1.2539 -1.3606 -4.5167
+0.2824 +0.2988 +1.0478 +0.3734 -1.7924 +0.264
+0.2866 +0.9759 +0.2977 -2.0342
-1.1146 -1.1627 +0.4308 +1.2617 +0.452 -0.885
-1.1186 +0.4888 +1.2433 +0.4043
-1.6973 -1.7075 -0.0871 +1.4717 +1.8591 -1.6837
-1.4007 -0.087 +1.4763 +1.8562
-2.9075 -2.945 +0.3826 +2.2916 +3.0588 -2.9184
-2.9246 +0.5772 +2.3114 +3.0739
-4.9106 -4.8946 -0.9329 +4.7021 +5.8784 -4.8757
-4.8899 -0.942 +4.9596 +5.9056
-6.8868 -6.8637 -3.7828 +2.493 +14.9097 -6.8625
-6.8798 -3.7591 +2.4522 +15.1798
QED
On 09/15/14 8:50 PM, Asumu Takikawa wrote:
On 2014-09-15 18:57:51 -0700, Matthew Butterick wrote:
Mike Bostock's visual demonstration of why naive sorting functions are false
friends. As he and Henglein point out, transitivity of the comparator is
essential.
http://bost.ocks.org/mike/shuffle/compare.html
Thanks, that's really interesting. Also means that our implementation of
`shuffle` in Racket stdlib is not great:
(define (shuffle l)
(sort l < #:key (λ(_) (random)) #:cache-keys? #t))
(more prose on the algorithm here:
http://bost.ocks.org/mike/algorithms/#shuffling)
Cheers,
Asumu
____________________
Racket Users list:
http://lists.racket-lang.org/users
