Alex Herbert created RNG-187:
--------------------------------
Summary: 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
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)
