search

smol-rs / fastrand

A simple and fast random number generator
Apache License 2.0
409 stars 35 forks source link

Implementation of `choose_multiple` #63

Closed sigaloid closed 1 year ago

sigaloid commented 1 year ago

Hi, I have a question about the implementation of choose_multiple. Once you've collected the elements into a reservoir...

https://github.com/smol-rs/fastrand/blob/96c01d960e02b1ae49cb0bd72a9828471ebbc028/src/lib.rs#L380-L393

Why not use the built-in shuffle function? https://github.com/smol-rs/fastrand/blob/96c01d960e02b1ae49cb0bd72a9828471ebbc028/src/lib.rs#L514-L518

The if let Some check for get_mut confuses me, as we've already .take'n amount, and we've confirmed the length matches, so why check for errors?

I think alternatively we could replace all of this: https://github.com/smol-rs/fastrand/blob/96c01d960e02b1ae49cb0bd72a9828471ebbc028/src/lib.rs#L382-L402

with simply rng.shuffle(&mut reservoir) (and maybe handle an over-allocation as well).

sigaloid commented 1 year ago

Ah, I misunderstood the original algorithm, I didn't even realize it was a reservoir sampling algorithm. Closing!