But is fisher-yates is linear time, right? (And probably more efficient in practice on larger lists, if not smaller.)
Robby On Mon, Sep 15, 2014 at 11:40 PM, Matthew Butterick <m...@mbtype.com> wrote: > 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 ____________________ Racket Users list: http://lists.racket-lang.org/users
