public class RandomSample
extends java.lang.Object
Constructor and Description |
---|
RandomSample() |
Modifier and Type | Method and Description |
---|---|
static int[] |
drawSortedDenseSample(int n,
int N,
java.util.Random r)
Draws a sorted list of n distinct integers from 0, 1, ..., N - 1 based on the simple Algorithm A in
|
static int[] |
drawSortedSample(int n,
int N,
java.util.Random r)
Returns a sorted list of n distinct integers that are randomly chosen from 0, 1, ..., N - 1.
|
static int[] |
drawSortedSparseSample(int n,
int N,
java.util.Random r)
Draws a sorted list of n distinct integers from 0, 1, ..., N - 1 based on drawSparseSample() followed
by radix sort.
|
static int[] |
drawSparseSample(int n,
int N,
java.util.Random r)
Draws n distinct integers from 0, 1, ..., N - 1, randomly ordered, using a partial Fisher-Yates shuffle
and a hash map.
|
static int[] |
radixSortOfPositiveIntegers(int[] a)
Sorts the given array of non-negative integers in ascending order using LSD radix sort.
|
public static int[] drawSortedSample(int n, int N, java.util.Random r) throws java.lang.IllegalArgumentException
n
- the number of samples to takeN
- one greater than the largest integer that can possibly be included in the sampler
- the random number generator to usejava.lang.IllegalArgumentException
- if a sample cannot be taken based on the given parameterspublic static int[] drawSortedDenseSample(int n, int N, java.util.Random r) throws java.lang.IllegalArgumentException
J.S. Vitter (1987) "An Efficient Algorithm for Sequential Random Sampling". ACM Trans Math Software, 13(1).
This algorithm has time complexity O(N) but only requires O(n) random numbers to be generated. Space complexity is O(n). Useful if 0 << n / N.
java.lang.IllegalArgumentException
public static int[] drawSortedSparseSample(int n, int N, java.util.Random r) throws java.lang.IllegalArgumentException
java.lang.IllegalArgumentException
public static int[] radixSortOfPositiveIntegers(int[] a)
a
- the array to be sortedpublic static int[] drawSparseSample(int n, int N, java.util.Random r) throws java.lang.IllegalArgumentException
D.N. Bui (2015) "CacheDiff: Fast Random Sampling" https://arxiv.org/abs/1512.00501
This algorithm has time and space complexity O(n). Useful if n << N.
java.lang.IllegalArgumentException