You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2019/02/28 17:38:52 UTC
[commons-rng] branch master updated (3a4b6db -> fcaf9e3)
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git.
from 3a4b6db ConstructionPerformance: Added Javadoc about purpose of the benchmark.
new 2112fa3 RNG-74: DiscreteUniformSampler can be optimised for the algorithm
new 5840be0 Merge branch 'improvement-RNG-74' of https://github.com/aherbert/commons-rng into aherbert-improvement-RNG-74
new 529b52c Merge branch 'aherbert-improvement-RNG-74'
new fcaf9e3 Track changes.
The 4 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../distribution/DiscreteUniformSampler.java | 134 ++++++++++++++++-----
src/changes/changes.xml | 4 +
2 files changed, 111 insertions(+), 27 deletions(-)
[commons-rng] 01/04: RNG-74: DiscreteUniformSampler can be
optimised for the algorithm
Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git
commit 2112fa3d258a827cba42efbea15743dd64e0225a
Author: aherbert <ah...@apache.org>
AuthorDate: Tue Feb 26 14:33:17 2019 +0000
RNG-74: DiscreteUniformSampler can be optimised for the algorithm
---
.../distribution/DiscreteUniformSampler.java | 134 ++++++++++++++++-----
1 file changed, 107 insertions(+), 27 deletions(-)
diff --git a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/DiscreteUniformSampler.java b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/DiscreteUniformSampler.java
index 54442a0..00e308b 100644
--- a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/DiscreteUniformSampler.java
+++ b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/DiscreteUniformSampler.java
@@ -27,12 +27,103 @@ import org.apache.commons.rng.UniformRandomProvider;
public class DiscreteUniformSampler
extends SamplerBase
implements DiscreteSampler {
- /** Lower bound. */
- private final int lower;
- /** Upper bound. */
- private final int upper;
- /** Underlying source of randomness. */
- private final UniformRandomProvider rng;
+
+ /** The appropriate uniform sampler for the parameters. */
+ private final DiscreteSampler delegate;
+
+ /**
+ * Base class for a sampler from a discrete uniform distribution.
+ */
+ private abstract static class AbstractDiscreteUniformSampler
+ implements DiscreteSampler {
+
+ /** Underlying source of randomness. */
+ protected final UniformRandomProvider rng;
+ /** Lower bound. */
+ protected final int lower;
+
+ /**
+ * @param rng Generator of uniformly distributed random numbers.
+ * @param lower Lower bound (inclusive) of the distribution.
+ */
+ AbstractDiscreteUniformSampler(UniformRandomProvider rng,
+ int lower) {
+ this.rng = rng;
+ this.lower = lower;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public String toString() {
+ return "Uniform deviate [" + rng.toString() + "]";
+ }
+ }
+
+ /**
+ * Discrete uniform distribution sampler when the range between lower and upper is small
+ * enough to fit in a positive integer.
+ */
+ private static class SmallRangeDiscreteUniformSampler
+ extends AbstractDiscreteUniformSampler {
+
+ /** Maximum range of the sample from the lower bound (exclusive). */
+ private final int range;
+
+ /**
+ * @param rng Generator of uniformly distributed random numbers.
+ * @param lower Lower bound (inclusive) of the distribution.
+ * @param range Maximum range of the sample from the lower bound (exclusive).
+ */
+ SmallRangeDiscreteUniformSampler(UniformRandomProvider rng,
+ int lower,
+ int range) {
+ super(rng, lower);
+ this.range = range;
+ }
+
+ @Override
+ public int sample() {
+ return lower + rng.nextInt(range);
+ }
+ }
+
+ /**
+ * Discrete uniform distribution sampler when the range between lower and upper is too large
+ * to fit in a positive integer.
+ */
+ private static class LargeRangeDiscreteUniformSampler
+ extends AbstractDiscreteUniformSampler {
+
+ /** Upper bound. */
+ private final int upper;
+
+ /**
+ * @param rng Generator of uniformly distributed random numbers.
+ * @param lower Lower bound (inclusive) of the distribution.
+ * @param upper Upper bound (inclusive) of the distribution.
+ */
+ LargeRangeDiscreteUniformSampler(UniformRandomProvider rng,
+ int lower,
+ int upper) {
+ super(rng, lower);
+ this.upper = upper;
+ }
+
+ @Override
+ public int sample() {
+ // Use a simple rejection method.
+ // This is used when (upper-lower) >= Integer.MAX_VALUE.
+ // This will loop on average 2 times in the worst case scenario
+ // when (upper-lower) == Integer.MAX_VALUE.
+ while (true) {
+ final int r = rng.nextInt();
+ if (r >= lower &&
+ r <= upper) {
+ return r;
+ }
+ }
+ }
+ }
/**
* @param rng Generator of uniformly distributed random numbers.
@@ -44,39 +135,28 @@ public class DiscreteUniformSampler
int lower,
int upper) {
super(null);
- this.rng = rng;
if (lower > upper) {
throw new IllegalArgumentException(lower + " > " + upper);
}
-
- this.lower = lower;
- this.upper = upper;
+ // Choose the algorithm depending on the range
+ final int range = (upper - lower) + 1;
+ delegate = range <= 0 ?
+ // The range is too wide to fit in a positive int (larger
+ // than 2^31); use a simple rejection method.
+ new LargeRangeDiscreteUniformSampler(rng, lower, upper) :
+ // Use a sample from the range added to the lower bound.
+ new SmallRangeDiscreteUniformSampler(rng, lower, range);
}
/** {@inheritDoc} */
@Override
public int sample() {
- final int max = (upper - lower) + 1;
- if (max <= 0) {
- // The range is too wide to fit in a positive int (larger
- // than 2^31); as it covers more than half the integer range,
- // we use a simple rejection method.
- while (true) {
- final int r = rng.nextInt();
- if (r >= lower &&
- r <= upper) {
- return r;
- }
- }
- } else {
- // We can shift the range and directly generate a positive int.
- return lower + rng.nextInt(max);
- }
+ return delegate.sample();
}
/** {@inheritDoc} */
@Override
public String toString() {
- return "Uniform deviate [" + rng.toString() + "]";
+ return delegate.toString();
}
}
[commons-rng] 03/04: Merge branch 'aherbert-improvement-RNG-74'
Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git
commit 529b52c51f04f3260e1a0fcd0435c9f0136762fe
Merge: 3a4b6db 5840be0
Author: aherbert <ah...@apache.org>
AuthorDate: Thu Feb 28 17:37:06 2019 +0000
Merge branch 'aherbert-improvement-RNG-74'
Closes #24
.../distribution/DiscreteUniformSampler.java | 134 ++++++++++++++++-----
1 file changed, 107 insertions(+), 27 deletions(-)
[commons-rng] 02/04: Merge branch 'improvement-RNG-74' of
https://github.com/aherbert/commons-rng into aherbert-improvement-RNG-74
Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git
commit 5840be0bd157eedeadaa0e60b5ff513eaa6c8bd8
Merge: 3a4b6db 2112fa3
Author: aherbert <ah...@apache.org>
AuthorDate: Thu Feb 28 17:36:29 2019 +0000
Merge branch 'improvement-RNG-74' of https://github.com/aherbert/commons-rng into aherbert-improvement-RNG-74
.../distribution/DiscreteUniformSampler.java | 134 ++++++++++++++++-----
1 file changed, 107 insertions(+), 27 deletions(-)
[commons-rng] 04/04: Track changes.
Posted by ah...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git
commit fcaf9e370f2548a4baac306995f418ab8c0ae4bf
Author: aherbert <ah...@apache.org>
AuthorDate: Thu Feb 28 17:38:51 2019 +0000
Track changes.
---
src/changes/changes.xml | 4 ++++
1 file changed, 4 insertions(+)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index a22da18..e49e200 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -75,6 +75,10 @@ re-run tests that fail, and pass the build if they succeed
within the allotted number of reruns (the test will be marked
as 'flaky' in the report).
">
+ <action dev="aherbert" type="update" issue="RNG-74">
+ "DiscreteUniformSampler": Algorithms for small and large integer ranges have
+ been delegated to specialised classes.
+ </action>
<action dev="aherbert" type="add" issue="RNG-72">
Add new JMH benchmark ConstructionPerformance.
</action>