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 88f7f97a9a174ae6d6ea3dc3a629d1834fb3aec3
Author: Alex Herbert <aherb...@apache.org>
AuthorDate: Mon Sep 2 14:34:57 2024 +0100
Delegate to ArraySampler for shuffle
---
.../apache/commons/rng/sampling/ArraySampler.java | 42 ++++++++++++++++++++++
.../apache/commons/rng/sampling/ListSampler.java | 35 ++----------------
.../commons/rng/sampling/PermutationSampler.java | 21 +++--------
.../commons/rng/sampling/SubsetSamplerUtils.java | 2 +-
4 files changed, 50 insertions(+), 50 deletions(-)
diff --git
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/ArraySampler.java
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/ArraySampler.java
index 9be2de44..86886705 100644
---
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/ArraySampler.java
+++
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/ArraySampler.java
@@ -16,6 +16,7 @@
*/
package org.apache.commons.rng.sampling;
+import java.util.List;
import org.apache.commons.rng.UniformRandomProvider;
/**
@@ -268,6 +269,34 @@ public final class ArraySampler {
return array;
}
+ /**
+ * Shuffles the entries of the given list.
+ *
+ * <p>Note: This method is intentionally package-private.
+ *
+ * <p>This method exists to allow the shuffle performed by the {@link
ListSampler} to
+ * match the {@link PermutationSampler} and {@link ArraySampler}.
+ *
+ * @param <T> Type of the items.
+ * @param rng Source of randomness.
+ * @param array Array whose entries will be shuffled (in-place).
+ */
+ static <T> void shuffle(UniformRandomProvider rng, List<T> array) {
+ int i = array.size();
+ for (; i > BATCH_2; --i) {
+ swap(array, i - 1, rng.nextInt(i));
+ }
+ // Batches of 2
+ final int[] productBound = {i * (i - 1)};
+ for (; i > 1; i -= 2) {
+ final int[] indices = randomBounded2(i, i - 1, productBound, rng);
+ final int index1 = indices[0];
+ final int index2 = indices[1];
+ swap(array, i - 1, index1);
+ swap(array, i - 2, index2);
+ }
+ }
+
/**
* Shuffles the entries of the given array in the range {@code [from, to)}.
*
@@ -629,6 +658,19 @@ public final class ArraySampler {
array[j] = tmp;
}
+ /**
+ * Swaps the two specified elements in the list.
+ *
+ * @param <T> Type of the list items.
+ * @param list List.
+ * @param i First index.
+ * @param j Second index.
+ */
+ private static <T> void swap(List<T> list, int i, int j) {
+ final T tmp = list.get(i);
+ list.set(i, list.get(j));
+ list.set(j, tmp);
+ }
/**
* Return two random values in {@code [0, range1)} and {@code [0,
range2)}. The
diff --git
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/ListSampler.java
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/ListSampler.java
index 638b66d7..9d7a860c 100644
---
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/ListSampler.java
+++
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/ListSampler.java
@@ -98,15 +98,11 @@ public final class ListSampler {
List<T> list) {
if (list instanceof RandomAccess || list.size() <
RANDOM_ACCESS_SIZE_THRESHOLD) {
// Shuffle list in-place
- for (int i = list.size(); i > 1; i--) {
- swap(list, i - 1, rng.nextInt(i));
- }
+ ArraySampler.shuffle(rng, list);
} else {
// Shuffle as an array
final Object[] array = list.toArray();
- for (int i = array.length; i > 1; i--) {
- swap(array, i - 1, rng.nextInt(i));
- }
+ ArraySampler.shuffle(rng, array);
// Copy back. Use raw types.
final ListIterator it = list.listIterator();
@@ -150,31 +146,4 @@ public final class ListSampler {
shuffle(rng, list.subList(start, list.size()));
}
}
-
- /**
- * Swaps the two specified elements in the list.
- *
- * @param <T> Type of the list items.
- * @param list List.
- * @param i First index.
- * @param j Second index.
- */
- private static <T> void swap(List<T> list, int i, int j) {
- final T tmp = list.get(i);
- list.set(i, list.get(j));
- list.set(j, tmp);
- }
-
- /**
- * Swaps the two specified elements in the array.
- *
- * @param array Array.
- * @param i First index.
- * @param j Second index.
- */
- private static void swap(Object[] array, int i, int j) {
- final Object tmp = array[i];
- array[i] = array[j];
- array[j] = tmp;
- }
}
diff --git
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/PermutationSampler.java
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/PermutationSampler.java
index 4fb8d1d1..d715cf09 100644
---
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/PermutationSampler.java
+++
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/PermutationSampler.java
@@ -79,7 +79,6 @@ public class PermutationSampler implements
SharedStateObjectSampler<int[]> {
/**
* @return a random permutation.
- *
* @see #PermutationSampler(UniformRandomProvider,int,int)
*/
@Override
@@ -100,14 +99,13 @@ public class PermutationSampler implements
SharedStateObjectSampler<int[]> {
/**
* Shuffles the entries of the given array.
*
- * @see #shuffle(UniformRandomProvider,int[],int,boolean)
- *
* @param rng Random number generator.
* @param list Array whose entries will be shuffled (in-place).
+ * @see #shuffle(UniformRandomProvider,int[],int,boolean)
*/
public static void shuffle(UniformRandomProvider rng,
int[] list) {
- shuffle(rng, list, list.length - 1, true);
+ ArraySampler.shuffle(rng, list);
}
/**
@@ -117,7 +115,7 @@ public class PermutationSampler implements
SharedStateObjectSampler<int[]> {
* The {@code start} and {@code towardHead} parameters select which part
* of the array is randomized and which is left untouched.
*
- * <p>Sampling uses {@link UniformRandomProvider#nextInt(int)}.</p>
+ * <p>Sampling uses {@link UniformRandomProvider#nextInt()}.</p>
*
* @param rng Random number generator.
* @param list Array whose entries will be shuffled (in-place).
@@ -132,19 +130,10 @@ public class PermutationSampler implements
SharedStateObjectSampler<int[]> {
boolean towardHead) {
if (towardHead) {
// Visit all positions from start to 0.
- // Do not visit 0 to avoid a swap with itself.
- for (int i = start; i > 0; i--) {
- // Swap index with any position down to 0
- SubsetSamplerUtils.swap(list, i, rng.nextInt(i + 1));
- }
+ ArraySampler.shuffle(rng, list, 0, start + 1);
} else {
// Visit all positions from the end to start.
- // Start is not visited to avoid a swap with itself.
- for (int i = list.length - 1; i > start; i--) {
- // Swap index with any position down to start.
- // Note: i - start + 1 is the number of elements remaining.
- SubsetSamplerUtils.swap(list, i, rng.nextInt(i - start + 1) +
start);
- }
+ ArraySampler.shuffle(rng, list, start, list.length);
}
}
diff --git
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/SubsetSamplerUtils.java
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/SubsetSamplerUtils.java
index efac8d1a..9133ed66 100644
---
a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/SubsetSamplerUtils.java
+++
b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/SubsetSamplerUtils.java
@@ -93,7 +93,7 @@ final class SubsetSamplerUtils {
* @param i the first index
* @param j the second index
*/
- static void swap(int[] array, int i, int j) {
+ private static void swap(int[] array, int i, int j) {
final int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
