Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

New publications on integer range sampling and shuffling #570

Closed
vks opened this issue Jul 27, 2018 · 3 comments · Fixed by #1287
Closed

New publications on integer range sampling and shuffling #570

vks opened this issue Jul 27, 2018 · 3 comments · Fixed by #1287
Labels
P-low Priority: Low

Comments

@vks
Copy link
Collaborator

vks commented Jul 27, 2018

Daniel Lemire published a paper and Melissa O'Neil wrote a blog post about efficient range sampling, including some benchmarks on shuffling performance. This might be of interest for Rand.

@pitdicker
Copy link
Contributor

Just reading the article, we are doing ok already. We use the unbiased multiply method, where the cost of the modulus can be amortized. Or we use the bitmasking method on some integer sizes with sample_single, which may be a bit faster than taking the modulus.

Biased methods are still worth exposing somehow I think.

@vks Thank you for the links!

@dhardy
Copy link
Member

dhardy commented Jul 28, 2018

It would be interesting to see a straight-up comparison between this and the method @pitdicker implemented, which is similar to Lemire's but uses a different technique to avoid modulo computation. Perhaps @imneme would like to compare?

@vks
Copy link
Collaborator Author

vks commented Aug 24, 2021

Also see #1154, which implements the O'Neil method for range sampling.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
P-low Priority: Low
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants