Class ArraySampler

java.lang.Object
org.apache.commons.rng.sampling.ArraySampler
public final class ArraySampler extends Object
Utilities for shuffling an array in-place.

Shuffles use the Fisher-Yates algorithm.

Small ranges use batched random integer generation to increase performance.

  • Nevin Brackett-Rozinsky, Daniel Lemire, Batched Ranged Random Integer Generation, Software: Practice and Experience (to appear) arXiv:2408.06213M
Since:
1.6

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final int
    BATCH_2
    Length threshold to sample 2 integers from a random 32-bit value.
    private static final long
    MASK_32
    Mask the lower 32-bit of a long.
    private static final long
    POW_32
    2^32.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    private
    ArraySampler()
    Class contains only static methods.

  • Method Summary

    Modifier and Type
    Method
    Description
    private static int
    checkFromToIndex(int fromIndex, int toIndex, int length)
    Checks if the sub-range from fromIndex (inclusive) to toIndex (exclusive) is within the bounds of range from 0 (inclusive) to length (exclusive).
    (package private) static int[]
    randomBounded2(int range1, int range2, int[] productBound, UniformRandomProvider rng)
    Return two random values in [0, range1) and [0, range2).
    static boolean[]
    shuffle(UniformRandomProvider rng, boolean[] array)
    Shuffles the entries of the given array.
    static boolean[]
    shuffle(UniformRandomProvider rng, boolean[] array, int from, int to)
    Shuffles the entries of the given array in the range [from, to).
    static byte[]
    shuffle(UniformRandomProvider rng, byte[] array)
    Shuffles the entries of the given array.
    static byte[]
    shuffle(UniformRandomProvider rng, byte[] array, int from, int to)
    Shuffles the entries of the given array in the range [from, to).
    static char[]
    shuffle(UniformRandomProvider rng, char[] array)
    Shuffles the entries of the given array.
    static char[]
    shuffle(UniformRandomProvider rng, char[] array, int from, int to)
    Shuffles the entries of the given array in the range [from, to).
    static double[]
    shuffle(UniformRandomProvider rng, double[] array)
    Shuffles the entries of the given array.
    static double[]
    shuffle(UniformRandomProvider rng, double[] array, int from, int to)
    Shuffles the entries of the given array in the range [from, to).
    static float[]
    shuffle(UniformRandomProvider rng, float[] array)
    Shuffles the entries of the given array.
    static float[]
    shuffle(UniformRandomProvider rng, float[] array, int from, int to)
    Shuffles the entries of the given array in the range [from, to).
    static int[]
    shuffle(UniformRandomProvider rng, int[] array)
    Shuffles the entries of the given array.
    static int[]
    shuffle(UniformRandomProvider rng, int[] array, int from, int to)
    Shuffles the entries of the given array in the range [from, to).
    static long[]
    shuffle(UniformRandomProvider rng, long[] array)
    Shuffles the entries of the given array.
    static long[]
    shuffle(UniformRandomProvider rng, long[] array, int from, int to)
    Shuffles the entries of the given array in the range [from, to).
    static short[]
    shuffle(UniformRandomProvider rng, short[] array)
    Shuffles the entries of the given array.
    static short[]
    shuffle(UniformRandomProvider rng, short[] array, int from, int to)
    Shuffles the entries of the given array in the range [from, to).
    (package private) static <T> void
    shuffle(UniformRandomProvider rng, List<T> array)
    Shuffles the entries of the given list.
    static <T> T[]
    shuffle(UniformRandomProvider rng, T[] array)
    Shuffles the entries of the given array.
    static <T> T[]
    shuffle(UniformRandomProvider rng, T[] array, int from, int to)
    Shuffles the entries of the given array in the range [from, to).
    private static void
    swap(boolean[] array, int i, int j)
    Swaps the two specified elements in the array.
    private static void
    swap(byte[] array, int i, int j)
    Swaps the two specified elements in the array.
    private static void
    swap(char[] array, int i, int j)
    Swaps the two specified elements in the array.
    private static void
    swap(double[] array, int i, int j)
    Swaps the two specified elements in the array.
    private static void
    swap(float[] array, int i, int j)
    Swaps the two specified elements in the array.
    private static void
    swap(int[] array, int i, int j)
    Swaps the two specified elements in the array.
    private static void
    swap(long[] array, int i, int j)
    Swaps the two specified elements in the array.
    private static void
    swap(short[] array, int i, int j)
    Swaps the two specified elements in the array.
    private static void
    swap(Object[] array, int i, int j)
    Swaps the two specified elements in the array.
    private static <T> void
    swap(List<T> list, int i, int j)
    Swaps the two specified elements in the list.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • MASK_32

      private static final long MASK_32
      Mask the lower 32-bit of a long.
      See Also:

    • POW_32

      private static final long POW_32
      2^32. Used for the bounded random algorithm. This is required as the original method used (-bound % bound) for (2^L % bound) which only works for unsigned integer modulus.
      See Also:

    • BATCH_2

      private static final int BATCH_2
      Length threshold to sample 2 integers from a random 32-bit value. The threshold provided in the Brackett-Rozinsky and Lemire paper is the power of 2 below 20724. Note that the product 2^15*2^15 is representable using signed integers.
      See Also:

  • Constructor Details

    • ArraySampler

      private ArraySampler()
      Class contains only static methods.

  • Method Details

    • shuffle

      public static boolean[] shuffle(UniformRandomProvider rng, boolean[] array)
      Shuffles the entries of the given array.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      Returns:
      a reference to the given array

    • shuffle

      public static byte[] shuffle(UniformRandomProvider rng, byte[] array)
      Shuffles the entries of the given array.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      Returns:
      a reference to the given array

    • shuffle

      public static char[] shuffle(UniformRandomProvider rng, char[] array)
      Shuffles the entries of the given array.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      Returns:
      a reference to the given array

    • shuffle

      public static double[] shuffle(UniformRandomProvider rng, double[] array)
      Shuffles the entries of the given array.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      Returns:
      a reference to the given array

    • shuffle

      public static float[] shuffle(UniformRandomProvider rng, float[] array)
      Shuffles the entries of the given array.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      Returns:
      a reference to the given array

    • shuffle

      public static int[] shuffle(UniformRandomProvider rng, int[] array)
      Shuffles the entries of the given array.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      Returns:
      a reference to the given array

    • shuffle

      public static long[] shuffle(UniformRandomProvider rng, long[] array)
      Shuffles the entries of the given array.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      Returns:
      a reference to the given array

    • shuffle

      public static short[] shuffle(UniformRandomProvider rng, short[] array)
      Shuffles the entries of the given array.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      Returns:
      a reference to the given array

    • shuffle

      public static <T> T[] shuffle(UniformRandomProvider rng, T[] array)
      Shuffles the entries of the given array.
      Type Parameters:
      T - Type of the items.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      Returns:
      a reference to the given array

    • shuffle

      static <T> void shuffle(UniformRandomProvider rng, List<T> array)
      Shuffles the entries of the given list.

      Note: This method is intentionally package-private.

      This method exists to allow the shuffle performed by the ListSampler to match the PermutationSampler and ArraySampler.

      Type Parameters:
      T - Type of the items.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).

    • shuffle

      public static boolean[] shuffle(UniformRandomProvider rng, boolean[] array, int from, int to)
      Shuffles the entries of the given array in the range [from, to).
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      from - Lower-bound (inclusive) of the sub-range.
      to - Upper-bound (exclusive) of the sub-range.
      Returns:
      a reference to the given array
      Throws:
      IndexOutOfBoundsException - if the sub-range is out of bounds

    • shuffle

      public static byte[] shuffle(UniformRandomProvider rng, byte[] array, int from, int to)
      Shuffles the entries of the given array in the range [from, to).
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      from - Lower-bound (inclusive) of the sub-range.
      to - Upper-bound (exclusive) of the sub-range.
      Returns:
      a reference to the given array
      Throws:
      IndexOutOfBoundsException - if the sub-range is out of bounds

    • shuffle

      public static char[] shuffle(UniformRandomProvider rng, char[] array, int from, int to)
      Shuffles the entries of the given array in the range [from, to).
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      from - Lower-bound (inclusive) of the sub-range.
      to - Upper-bound (exclusive) of the sub-range.
      Returns:
      a reference to the given array
      Throws:
      IndexOutOfBoundsException - if the sub-range is out of bounds

    • shuffle

      public static double[] shuffle(UniformRandomProvider rng, double[] array, int from, int to)
      Shuffles the entries of the given array in the range [from, to).
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      from - Lower-bound (inclusive) of the sub-range.
      to - Upper-bound (exclusive) of the sub-range.
      Returns:
      a reference to the given array
      Throws:
      IndexOutOfBoundsException - if the sub-range is out of bounds

    • shuffle

      public static float[] shuffle(UniformRandomProvider rng, float[] array, int from, int to)
      Shuffles the entries of the given array in the range [from, to).
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      from - Lower-bound (inclusive) of the sub-range.
      to - Upper-bound (exclusive) of the sub-range.
      Returns:
      a reference to the given array
      Throws:
      IndexOutOfBoundsException - if the sub-range is out of bounds

    • shuffle

      public static int[] shuffle(UniformRandomProvider rng, int[] array, int from, int to)
      Shuffles the entries of the given array in the range [from, to).
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      from - Lower-bound (inclusive) of the sub-range.
      to - Upper-bound (exclusive) of the sub-range.
      Returns:
      a reference to the given array
      Throws:
      IndexOutOfBoundsException - if the sub-range is out of bounds

    • shuffle

      public static long[] shuffle(UniformRandomProvider rng, long[] array, int from, int to)
      Shuffles the entries of the given array in the range [from, to).
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      from - Lower-bound (inclusive) of the sub-range.
      to - Upper-bound (exclusive) of the sub-range.
      Returns:
      a reference to the given array
      Throws:
      IndexOutOfBoundsException - if the sub-range is out of bounds

    • shuffle

      public static short[] shuffle(UniformRandomProvider rng, short[] array, int from, int to)
      Shuffles the entries of the given array in the range [from, to).
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      from - Lower-bound (inclusive) of the sub-range.
      to - Upper-bound (exclusive) of the sub-range.
      Returns:
      a reference to the given array
      Throws:
      IndexOutOfBoundsException - if the sub-range is out of bounds

    • shuffle

      public static <T> T[] shuffle(UniformRandomProvider rng, T[] array, int from, int to)
      Shuffles the entries of the given array in the range [from, to).
      Type Parameters:
      T - Type of the items.
      Parameters:
      rng - Source of randomness.
      array - Array whose entries will be shuffled (in-place).
      from - Lower-bound (inclusive) of the sub-range.
      to - Upper-bound (exclusive) of the sub-range.
      Returns:
      a reference to the given array
      Throws:
      IndexOutOfBoundsException - if the sub-range is out of bounds

    • swap

      private static void swap(boolean[] array, int i, int j)
      Swaps the two specified elements in the array.
      Parameters:
      array - Array.
      i - First index.
      j - Second index.

    • swap

      private static void swap(byte[] array, int i, int j)
      Swaps the two specified elements in the array.
      Parameters:
      array - Array.
      i - First index.
      j - Second index.

    • swap

      private static void swap(char[] array, int i, int j)
      Swaps the two specified elements in the array.
      Parameters:
      array - Array.
      i - First index.
      j - Second index.

    • swap

      private static void swap(double[] array, int i, int j)
      Swaps the two specified elements in the array.
      Parameters:
      array - Array.
      i - First index.
      j - Second index.

    • swap

      private static void swap(float[] array, int i, int j)
      Swaps the two specified elements in the array.
      Parameters:
      array - Array.
      i - First index.
      j - Second index.

    • swap

      private static void swap(int[] array, int i, int j)
      Swaps the two specified elements in the array.
      Parameters:
      array - Array.
      i - First index.
      j - Second index.

    • swap

      private static void swap(long[] array, int i, int j)
      Swaps the two specified elements in the array.
      Parameters:
      array - Array.
      i - First index.
      j - Second index.

    • swap

      private static void swap(short[] array, int i, int j)
      Swaps the two specified elements in the array.
      Parameters:
      array - Array.
      i - First index.
      j - Second index.

    • swap

      private static void swap(Object[] array, int i, int j)
      Swaps the two specified elements in the array.
      Parameters:
      array - Array.
      i - First index.
      j - Second index.

    • swap

      private static <T> void swap(List<T> list, int i, int j)
      Swaps the two specified elements in the list.
      Type Parameters:
      T - Type of the list items.
      Parameters:
      list - List.
      i - First index.
      j - Second index.

    • randomBounded2

      static int[] randomBounded2(int range1, int range2, int[] productBound, UniformRandomProvider rng)
      Return two random values in [0, range1) and [0, range2). The product bound is used for the reject algorithm. See Brackett-Rozinsky and Lemire.

      The product bound can be any positive integer >= range1*range2. It may be updated to become range1*range2.

      Parameters:
      range1 - Range 1.
      range2 - Range 2.
      productBound - Product bound.
      rng - Source of randomness.
      Returns:
      [index1, index2]

    • checkFromToIndex

      private static int checkFromToIndex(int fromIndex, int toIndex, int length)
      Checks if the sub-range from fromIndex (inclusive) to toIndex (exclusive) is within the bounds of range from 0 (inclusive) to length (exclusive).

      This function provides the functionality of java.utils.Objects.checkFromToIndex introduced in JDK 9. The Objects javadoc has been reproduced for reference.

      The sub-range is defined to be out of bounds if any of the following inequalities is true:

      • fromIndex < 0
      • fromIndex > toIndex
      • toIndex > length
      • length < 0, which is implied from the former inequalities
      Parameters:
      fromIndex - Lower-bound (inclusive) of the sub-range.
      toIndex - Upper-bound (exclusive) of the sub-range.
      length - Upper-bound (exclusive) of the range
      Returns:
      fromIndex if the sub-range is within the bounds of the range
      Throws:
      IndexOutOfBoundsException - if the sub-range is out of bounds