[ 
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)

Reply via email to