[
https://issues.apache.org/jira/browse/RNG-187?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alex Herbert updated RNG-187:
-----------------------------
Attachment: shuffle-1.png
> Performance improvements for an array shuffle
> ---------------------------------------------
>
> Key: RNG-187
> URL: https://issues.apache.org/jira/browse/RNG-187
> Project: Commons RNG
> Issue Type: New Feature
> Components: sampling
> Affects Versions: 1.6
> Reporter: Alex Herbert
> Priority: Minor
> Attachments: shuffle-1.png, shuffle.png
>
>
> Improve the performance of array shuffling by generation of multiple indices
> in a range [0, n) from a single sample from a random source.
> The current UniformRandomProvider method to sample an integer in a range [0,
> n) uses a rejection method based on multiplication with a single use of a
> slow modulus operator if rejection is required. The author of that method has
> extended it to allow generation of multiple integers from 2 or more ranges
> from the same random sample.
> When applied to a shuffle algorithm the speed-up can be significant,
> typically in the range of up to 2-fold for smaller arrays depending on the
> speed of the random generator; slower generators see a greater speed-up.
> The method is described in:
> {noformat}
> Nevin Brackett-Rozinsky, Daniel Lemire,
> Batched Ranged Random Integer Generation,
> Software: Practice and Experience (to appear)
> {noformat}
> See [arXiv:2408.06213M|https://arxiv.org/abs/2408.06213].
> See also [Daniel Lemire Blog: Faster random integer generation with
> batching|https://lemire.me/blog/2024/08/17/faster-random-integer-generation-with-batching/]
>
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
