[racket] on reversing a list by way of sort

Here's a version of "inside-out" Fisher-Yates that should fit the bill:

(define (fy-shuffle lst)
  (define v (list->vector lst))
  (for/list ([n (in-range (length lst) 0 -1)])
    (let* ([i (sub1 n)]
           [j (random n)]
           [v_j (vector-ref v j)])
      (when (not (= i j))
        (vector-set! v j (vector-ref v i)))
      v_j)))

Dan


On Tue, Sep 16, 2014 at 8:22 PM, Eli Barzilay <eli at barzilay.org> wrote:

> On Tue, Sep 16, 2014 at 8:22 AM, Robby Findler
> <robby at eecs.northwestern.edu> wrote:
> > But is fisher-yates is linear time, right? (And probably more
> > efficient in practice on larger lists, if not smaller.)
>
> Yes, but there are more considerations that I had when I did the simple
> version.  In case anyone wants to tackle this, what I vaguely remember
> is:
>
> * FY is faster, but will require much more than a one-liner, since the
>   list needs to be copied into a vector, then shuffled in-place, then
>   copied back.  I'm not saying that this will make it slower -- since
>   sort is doing a vector round-trip anyway; it'll just make it much
>   heavier than something that is not needed too often, and probably very
>   rarely with big lists when the differene would matter.
>
> * Looking at the wikipedia page to refresh myself, there is also an
>   "inside-out" algorithm that they say is better for creating a shuffled
>   copy of the input vector.  The nice thing in that is that it scans the
>   source vector in sequence, which means that it could work well to use
>   it, taking items from the list and putting them into an array that is
>   then converted back into a list.
>
> * I vaguely remember something about the problem of using integer random
>   numbers, which are usually the result of modulo (the WP page talks
>   about it too).  I think that there was some concern about that
>   possibly leading to some bias in the result somehow.  As a result,
>   since I don't know enough about such issues, I used (random) which has
>   the additional penalty of allocating floats.  IOW, the nice thing
>   about the current one-liner is that I didn't need to go too deep into
>   considering such issues, allowing me to keep my ignorance while being
>   relatively confident in the result not suffering from any bias.
>
>   In any case, this is also a point to consider if anyone wants to
>   implement FY.
>
> --
>           ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
>                     http://barzilay.org/                   Maze is Life!
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>



-- 
*Daniel Prager*
Agile/Lean Coaching, Software Development and Leadership
Startup: www.youpatch.com
Twitter: @agilejitsu <https://twitter.com/agilejitsu>
Blog: agile-jitsu.blogspot.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140916/131326b4/attachment-0001.html>