Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
I think we should put in a list shuffler into the core. Which should we use? The faster one? Jay On Thu, Nov 11, 2010 at 11:26 AM, Eli Barzilay e...@barzilay.org wrote: 5 minutes ago, Neil Toronto wrote: Carl Eastlund wrote: It's pick a random, uniform ordering, and then sort based on it. The random keys are chosen per element and cached (hence #:cache-keys? #t), not per comparison. Spanking good point, my good man. I think you're right. It's a very common method, and the classic example of the decorate-map-strip method that has some perl-guy's name slapped on it now. The wikipedia page on FY is pretty decent -- and one concern that I've encountered in the past is that it's sensitive to what that page calls modulo bias. The decorated version is more robust, especially with (random) that works at the highest `random' granularity. (BTW, to compare them you should use some (random 1000) thing to avoid the fp cost.) -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://barzilay.org/ Maze is Life! _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev -- Jay McCarthy j...@cs.byu.edu Assistant Professor / Brigham Young University http://faculty.cs.byu.edu/~jay The glory of God is Intelligence - DC 93 _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
I think we want the one recommended by the statisticians. :) Robby On Fri, Nov 12, 2010 at 2:36 PM, Jay McCarthy jay.mccar...@gmail.com wrote: I think we should put in a list shuffler into the core. Which should we use? The faster one? Jay On Thu, Nov 11, 2010 at 11:26 AM, Eli Barzilay e...@barzilay.org wrote: 5 minutes ago, Neil Toronto wrote: Carl Eastlund wrote: It's pick a random, uniform ordering, and then sort based on it. The random keys are chosen per element and cached (hence #:cache-keys? #t), not per comparison. Spanking good point, my good man. I think you're right. It's a very common method, and the classic example of the decorate-map-strip method that has some perl-guy's name slapped on it now. The wikipedia page on FY is pretty decent -- and one concern that I've encountered in the past is that it's sensitive to what that page calls modulo bias. The decorated version is more robust, especially with (random) that works at the highest `random' granularity. (BTW, to compare them you should use some (random 1000) thing to avoid the fp cost.) -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://barzilay.org/ Maze is Life! _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev -- Jay McCarthy j...@cs.byu.edu Assistant Professor / Brigham Young University http://faculty.cs.byu.edu/~jay The glory of God is Intelligence - DC 93 _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
Any objections to `shuffle' in `racket/list'? -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://barzilay.org/ Maze is Life! _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
Not by me. On Fri, Nov 12, 2010 at 2:25 PM, Eli Barzilay e...@barzilay.org wrote: Any objections to `shuffle' in `racket/list'? -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://barzilay.org/ Maze is Life! _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev -- Jay McCarthy j...@cs.byu.edu Assistant Professor / Brigham Young University http://faculty.cs.byu.edu/~jay The glory of God is Intelligence - DC 93 _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
[racket-dev] How about adding this simple list-shuffling procedure to racket?
I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list #:key (lambda (_) (random)) #:cache-keys? #t)) Thanks. _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
Eric Hanchrow wrote: I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list #:key (lambda (_) (random)) #:cache-keys? #t)) Is the distribution of shuffled lists uniform? That'd be hard to analyze, since it would depend on the sorting algorithm. I would guess it's not. (Don't worry if you didn't catch this yourself. It's not exactly straightforward.) If you want an unbiased shuffle, see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle Neil T _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
On Thu, Nov 11, 2010 at 12:18 PM, Neil Toronto neil.toro...@gmail.com wrote: Eric Hanchrow wrote: I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list #:key (lambda (_) (random)) #:cache-keys? #t)) Is the distribution of shuffled lists uniform? That'd be hard to analyze, since it would depend on the sorting algorithm. I would guess it's not. (Don't worry if you didn't catch this yourself. It's not exactly straightforward.) It should be uniform regardless of algorithm, since #:cache-keys? is #t. Shouldn't it? --Carl _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
I think that if random doesn't pick the same number twice you're guaranteed to be independent of the sorting algorithm, at least. Robby On Thu, Nov 11, 2010 at 11:18 AM, Neil Toronto neil.toro...@gmail.com wrote: Eric Hanchrow wrote: I find myself using this all the time; it seems it'd be handy to have built in. (define (shuffled list) (sort list #:key (lambda (_) (random)) #:cache-keys? #t)) Is the distribution of shuffled lists uniform? That'd be hard to analyze, since it would depend on the sorting algorithm. I would guess it's not. (Don't worry if you didn't catch this yourself. It's not exactly straightforward.) If you want an unbiased shuffle, see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle Neil T _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto neil.toro...@gmail.com wrote: I don't know. I know that the run through the list and swap with another random element algorithms are usually non-uniform, and so are a lot of other things that seem like they'd work. I wouldn't use something that wasn't proven to shuffle uniformly, at least for any serious statistics work. But this is not run through the list and swap with another random element. It's pick a random, uniform ordering, and then sort based on it. The random keys are chosen per element and cached (hence #:cache-keys? #t), not per comparison. --Carl _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
On Thu, Nov 11, 2010 at 11:40 AM, Carl Eastlund c...@ccs.neu.edu wrote: On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto neil.toro...@gmail.com wrote: I don't know. I know that the run through the list and swap with another random element algorithms are usually non-uniform, and so are a lot of other things that seem like they'd work. I wouldn't use something that wasn't proven to shuffle uniformly, at least for any serious statistics work. But this is not run through the list and swap with another random element. It's pick a random, uniform ordering, and then sort based on it. The random keys are chosen per element and cached (hence #:cache-keys? #t), not per comparison. Note that this is not the algorithm at the other end of the link that Neil T. sent; but one could probably make one like it in a simple manner using this idea. Robby _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
5 minutes ago, Neil Toronto wrote: Carl Eastlund wrote: It's pick a random, uniform ordering, and then sort based on it. The random keys are chosen per element and cached (hence #:cache-keys? #t), not per comparison. Spanking good point, my good man. I think you're right. It's a very common method, and the classic example of the decorate-map-strip method that has some perl-guy's name slapped on it now. The wikipedia page on FY is pretty decent -- and one concern that I've encountered in the past is that it's sensitive to what that page calls modulo bias. The decorated version is more robust, especially with (random) that works at the highest `random' granularity. (BTW, to compare them you should use some (random 1000) thing to avoid the fp cost.) -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://barzilay.org/ Maze is Life! _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] How about adding this simple list-shuffling procedure to racket?
When truly picking uniformally shuffled lists from a given list, see: http://telefonica.net/web2/koot/natural-to-permutation.scm and try (require srfi/27) ; for random-integer (require natural-to-permutation.scm) (let* ((lst (build-list 1000 (lambda (k) (round (quotient k 10) (shuffler (make-K-P lst eq?)) (K (random-integer (nPs lst eq? (time (shuffler K))) Where random-integer is assumed to produce a uniform distribution. Jos _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
