[racket] on reversing a list by way of sort

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 <mb at 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