Great!
Thanks for making the change.
Dan
On Sat, Nov 1, 2014 at 6:11 AM, Robby Findler
wrote:
> I've (finally) pushed the change to use FY.
> (
> https://github.com/plt/racket/commit/73f4fa86a3304b34437c0a1b94ea0e14f6f62de0
> )
>
> Thanks for doing all the hard work.
>
> Robby
>
--
*Danie
2014-09-18 5:38 GMT+02:00 Daniel Prager :
> I've done some testing of the built-in (random n) and I haven't been able to
> detect evidence of modulo bias. Of course absence of evidence isn't evidence
> of absence!
If you are interested in such matters, then take a look at the
NIST Statistical Test
I've (finally) pushed the change to use FY.
(https://github.com/plt/racket/commit/73f4fa86a3304b34437c0a1b94ea0e14f6f62de0)
Thanks for doing all the hard work.
Robby
Racket Users list:
http://lists.racket-lang.org/users
I've done some testing of the built-in (random n) and I haven't been able
to detect evidence of modulo bias. Of course absence of evidence isn't
evidence of absence!
More generally though, this is an interesting case (at least to me) of the
trade-offs between efficiency, clarity, concision, cost o
There was a bunch of work done to improve the random number generation
algorithms used internally a while back, but if you wanted to have a
look at them again, that would be most welcome.
Here is a at least part of the code:
https://github.com/plt/racket/blob/master/racket/src/racket/src/random.i
Modulo bias is easy enough to correct by checking and occasional
re-sampling. It's explained nicely in the following article:
http://zuttobenkyou.wordpress.com/2012/10/18/generating-random-numbers-without-modulo-bias/
Let's *deliberately* generate some modulo bias in Racket by simulating a
low lar
On Wed, Sep 17, 2014 at 1:53 AM, Daniel Prager
wrote:
>
> [Sorry for drawing you further in.]
:) (Indeed, my main point is that all that random-number stuff is
foreign to me...)
> My take on your 3 points:
>
> Fisher-Yates is only a few lines, so although not a one-liner, it
> seems reasonable
Hi Eli
I tried to squeeze out a little more efficiency, hopefully not at the
expense of too much loss of clarity, but I'm not overly fussed which exact
version of Fisher-Yates is (hopefully ;-) adopted.
[Sorry for drawing you further in.]
My take on your 3 points:
1. Fisher-Yates is only a f
In Tue, Sep 16, 2014 at 11:08 PM, Daniel Prager
wrote:
> 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)]
>
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))
(ve
On Tue, Sep 16, 2014 at 8:22 AM, Robby Findler
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, wh
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 wrote:
> Haha, yes I too checked Racket `shuffle` after I read that. But `shuffle` is
> mathematically sound. (Was I rea
On Tue, Sep 16, 2014 at 12:34 AM, Asumu Takikawa wrote:
>
> Ah, you're right. I actually tried visualizing Racket's shuffle using
> picts and didn't notice any streaks so I was puzzled. That explains it.
The equivalent of Racket's shuffle on that page is the "sort (random
order)", except that the
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 nan
On 2014-09-15 21:24:53 -0700, Eric Dobson wrote:
> This is different than linked algorithm. This one assigns a random
> number from [0,1) to each element where the linked algorithm assigns a
> random pairwise ordering to each comparison.
>
> I don't think there is anything wrong from a correctness
On Mon, Sep 15, 2014 at 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://bos
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 int
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
On 09/15/14 2:16 PM, Robby Findler wrote:
Fritz Henglein has studied the problem "what
Fritz Henglein has studied the problem "what is a sorting function?" that
touches on this kind of thing.
http://www.sciencedirect.com/science/article/pii/S1567832608001094
Robby
On Monday, September 15, 2014, David Van Horn wrote:
> On 9/15/14, 4:53 PM, David Van Horn wrote:
> > I don't think
On 9/15/14, 4:53 PM, David Van Horn wrote:
> I don't think you made enough examples.
Nope - my bad. Cute. Awful, but cute (and there could be correct
implementations of sort that would break your rev).
David
Racket Users list:
http://lists.racket-lang.org/users
I don't think you made enough examples.
On 9/15/14, 4:48 PM, Daniel Bastos wrote:
> Dear Racketeers, I was studying the exercise 20.2.4 of HtDP when I
> came up with this way of reversing lists. (Every element is a least
> element. Or greatest.)
>
> (define (f x y) true)
>
> (define (rev ls) (so
Dear Racketeers, I was studying the exercise 20.2.4 of HtDP when I came up
with this way of reversing lists. (Every element is a least element. Or
greatest.)
(define (f x y)
true)
(define (rev ls)
(sort ls f))
Welcome to DrRacket, version 6.0.1 [3m].
Language: Intermediate Student; memory li
22 matches
Mail list logo
