On Tue, Sep 16, 2014 at 8:22 AM, Robby Findler <ro...@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