[
https://issues.apache.org/jira/browse/RNG-179?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17542388#comment-17542388
]
Alex Herbert commented on RNG-179:
----------------------------------
I tested the speed of construction with long[] vs double[]. The frequencies
summing to approximately 2^62 can be created using:
{code:java}
final double sum = Arrays.stream(probabilities).sum();
final long[] frequencies = Arrays.stream(probabilities)
.mapToLong(x -> Math.round(0x1.0p62 * x / sum))
.toArray();
{code}
Here are the times for the fixed size distributions:
||Distribution||n||double[]||long[]||
|4SidedLoadedDie|4|842.9|761.0|
|Binomial_N67_P0.7|68|55466.3|8491.8|
|Geometric_P0.2|93|48722.1|12566.4|
|Poisson_Mean10_Mean20|53|19013.6|6807.2|
|Poisson_Mean3.22|20|7434.5|2984.9|
The longer length arrays are significantly slower when using the double[]
constructor.
Here are the times for random Dirichlet distributions:
||k||alpha||double[]||long[]||
|4|0.5|1065.4|1048.7|
| |1|930.8|858.6|
| |2|900.7|835.8|
|8|0.5|2080.8|1328.0|
| |1|1604.0|1478.3|
| |2|1582.2|1428.0|
|16|0.5|3539.6|2554.2|
| |1|3146.1|2480.8|
| |2|2786.4|2429.9|
Again, longer length double[] see a more significant slowdown.
Note that I used BigInteger for convenience. The BigIntegers have the value of
the mantissa with a shift created from the exponent offset. The offset is the
(exponent - min exponent). This may merit replacing the use of BigInteger with
a custom object to store the integers. This is because at most only 53 bits of
the BigInteger are non-zero but the length may be hundreds or thousands of bits
if there is a large range of magnitude in the input weights.
I am reluctant to implement a custom routine to sum the bit representation of
the integers (this is done in the reference c code). However once the sum is
performed using BigInteger (O(n)) then the O(nm) for-loop could use a custom
representation. This avoids costly repetition in the use of:
{code:java}
BigInteger.testBit(int)
{code}
Since most of the integer is zeros (due to left shift of the mantissa), then a
custom representation should be able to speed this up significantly. I will
look at the code and see if it can be optimised.
> The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete
> Probability Distributions
> ------------------------------------------------------------------------------------------------
>
> Key: RNG-179
> URL: https://issues.apache.org/jira/browse/RNG-179
> Project: Commons RNG
> Issue Type: New Feature
> Components: sampling
> Reporter: Vladimir Sitnikov
> Priority: Major
> Time Spent: 20m
> Remaining Estimate: 0h
>
> It might make sense to implement Fast Loaded Dice Roller sampler.
> See https://arxiv.org/pdf/2003.03830v2.pdf,
> https://github.com/probcomp/fast-loaded-dice-roller
> The authors claim that Fast Loaded Dice Roller is faster than the Alias
> Method.
--
This message was sent by Atlassian Jira
(v8.20.7#820007)