You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Alex Herbert (Jira)" <ji...@apache.org> on 2021/07/08 11:23:00 UTC
[jira] [Commented] (RNG-153) Update the UnitBallSampler method to
use an exponential deviate
[ https://issues.apache.org/jira/browse/RNG-153?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17377327#comment-17377327 ]
Alex Herbert commented on RNG-153:
----------------------------------
The algorithm which uses the exponential deviate applies from 3 dimensions and above. Alternative faster methods are used for 1D and 2D.
The UnitBallSamplerBenchmark has a specialisation for 3D with inlined variables (no use of an array).
Output from the JMH test using the current ArhensDieterExponentialSampler for the BallPoint picking method:
{noformat}
Benchmark (dimension) (size) (type) Mode Cnt Score Error Units
UnitBallSamplerBenchmark.create3D N/A 100 Baseline avgt 5 700.635 ± 10.952 ns/op
UnitBallSamplerBenchmark.create3D N/A 100 Rejection avgt 5 3238.869 ± 71.318 ns/op
UnitBallSamplerBenchmark.create3D N/A 100 BallPoint avgt 5 5214.093 ± 77.012 ns/op
UnitBallSamplerBenchmark.create3D N/A 100 HypersphereDiscard avgt 5 3842.120 ± 27.774 ns/op
UnitBallSamplerBenchmark.createND 3 100 Baseline avgt 5 936.658 ± 22.256 ns/op
UnitBallSamplerBenchmark.createND 3 100 Rejection avgt 5 3876.780 ± 114.378 ns/op
UnitBallSamplerBenchmark.createND 3 100 BallPoint avgt 5 5277.980 ± 231.506 ns/op
UnitBallSamplerBenchmark.createND 3 100 HypersphereDiscard avgt 5 4277.272 ± 248.885 ns/op
UnitBallSamplerBenchmark.createND 4 100 Baseline avgt 5 1108.409 ± 31.299 ns/op
UnitBallSamplerBenchmark.createND 4 100 Rejection avgt 5 6777.629 ± 119.346 ns/op
UnitBallSamplerBenchmark.createND 4 100 BallPoint avgt 5 5959.731 ± 119.423 ns/op
UnitBallSamplerBenchmark.createND 4 100 HypersphereDiscard avgt 5 5068.090 ± 55.460 ns/op
UnitBallSamplerBenchmark.createND 5 100 Baseline avgt 5 1100.847 ± 26.218 ns/op
UnitBallSamplerBenchmark.createND 5 100 Rejection avgt 5 11742.655 ± 120.403 ns/op
UnitBallSamplerBenchmark.createND 5 100 BallPoint avgt 5 6963.309 ± 274.222 ns/op
UnitBallSamplerBenchmark.createND 5 100 HypersphereDiscard avgt 5 5905.606 ± 48.789 ns/op
{noformat}
Output with the ZigguratSampler.Exponential:
{noformat}
Benchmark (dimension) (size) (type) Mode Cnt Score Error Units
UnitBallSamplerBenchmark.create3D N/A 100 Baseline avgt 5 698.229 ± 13.538 ns/op
UnitBallSamplerBenchmark.create3D N/A 100 Rejection avgt 5 3245.750 ± 65.839 ns/op
UnitBallSamplerBenchmark.create3D N/A 100 BallPoint avgt 5 3844.501 ± 53.134 ns/op
UnitBallSamplerBenchmark.create3D N/A 100 HypersphereDiscard avgt 5 3815.796 ± 54.428 ns/op
UnitBallSamplerBenchmark.createND 3 100 Baseline avgt 5 908.916 ± 30.029 ns/op
UnitBallSamplerBenchmark.createND 3 100 Rejection avgt 5 3875.215 ± 20.120 ns/op
UnitBallSamplerBenchmark.createND 3 100 BallPoint avgt 5 3760.313 ± 73.070 ns/op
UnitBallSamplerBenchmark.createND 3 100 HypersphereDiscard avgt 5 4344.968 ± 31.376 ns/op
UnitBallSamplerBenchmark.createND 4 100 Baseline avgt 5 1118.589 ± 30.484 ns/op
UnitBallSamplerBenchmark.createND 4 100 Rejection avgt 5 6666.344 ± 43.247 ns/op
UnitBallSamplerBenchmark.createND 4 100 BallPoint avgt 5 4398.038 ± 120.180 ns/op
UnitBallSamplerBenchmark.createND 4 100 HypersphereDiscard avgt 5 5118.056 ± 56.887 ns/op
UnitBallSamplerBenchmark.createND 5 100 Baseline avgt 5 1148.524 ± 69.139 ns/op
UnitBallSamplerBenchmark.createND 5 100 Rejection avgt 5 11716.668 ± 87.230 ns/op
UnitBallSamplerBenchmark.createND 5 100 BallPoint avgt 5 5241.822 ± 160.387 ns/op
UnitBallSamplerBenchmark.createND 5 100 HypersphereDiscard avgt 5 5942.969 ± 85.991 ns/op
{noformat}
The current UnitBallSampler the HypersphereDiscard method for 3D and ND.
Note: The Rejection method has benefited from a recent change to the method to generate a uniform deviate in [-1, 1). This method can be efficiently inlined and improves the performance to make it the fastest method. This result is the same on JDK 8 (data not shown).
Thus sampling should use:
* 3D - Rejection
* ND - BallPoint picking
> Update the UnitBallSampler method to use an exponential deviate
> ---------------------------------------------------------------
>
> Key: RNG-153
> URL: https://issues.apache.org/jira/browse/RNG-153
> Project: Commons RNG
> Issue Type: Improvement
> Components: sampling
> Affects Versions: 1.4
> Reporter: Alex Herbert
> Priority: Trivial
> Fix For: 1.4
>
>
> Currently the UnitBallSampler uses n+2 normalised Gaussian deviates for sampling in n dimensions. An alternative algorithm is to use n normalised Gaussian deviates and one exponential deviate, see [BallPointPicking (wolfram)|https://mathworld.wolfram.com/BallPointPicking.html].
> The new ziggurat exponential sampler is as fast as the ziggurat Gaussian sampler. Changing the algorithm should result in faster sampling.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)