[racket] on reversing a list by way of sort

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!