weka.core

Class RandomSample

java.lang.Object

weka.core.RandomSample

public class RandomSample
extends java.lang.Object

Class holding static utility methods for drawing random samples.

Version:

$Revision: 0$

Author:

eibe@cs.waikato.ac.nz

Constructor Summary

Constructors

Constructor and Description
RandomSample()

Method Summary

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.

Methods inherited from class java.lang.Object

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

Constructor Detail

RandomSample

public RandomSample()

Method Detail

drawSortedSample

public static int[] drawSortedSample(int n,
                                     int N,
                                     java.util.Random r)
                              throws java.lang.IllegalArgumentException

Returns a sorted list of n distinct integers that are randomly chosen from 0, 1, ..., N - 1. It uses the drawSortedDenseSample() in this class if n > (int)(0.2 * N), which has complexity O(N). Otherwise, it uses drawSortedSparseSample(), which has complexity O(n).

Parameters:

n - the number of samples to take

N - one greater than the largest integer that can possibly be included in the sample

r - the random number generator to use

Returns:

Throws:

java.lang.IllegalArgumentException - if a sample cannot be taken based on the given parameters

drawSortedDenseSample

public static int[] drawSortedDenseSample(int n,
                                          int N,
                                          java.util.Random r)
                                   throws java.lang.IllegalArgumentException

Draws a sorted list of n distinct integers from 0, 1, ..., N - 1 based on the simple Algorithm A in

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.

Throws:

java.lang.IllegalArgumentException

drawSortedSparseSample

public static int[] drawSortedSparseSample(int n,
                                           int N,
                                           java.util.Random r)
                                    throws java.lang.IllegalArgumentException

Draws a sorted list of n distinct integers from 0, 1, ..., N - 1 based on drawSparseSample() followed by radix sort. The time complexity of this method is O(n). Useful if n << N.

Throws:

java.lang.IllegalArgumentException

radixSortOfPositiveIntegers

public static int[] radixSortOfPositiveIntegers(int[] a)

Sorts the given array of non-negative integers in ascending order using LSD radix sort. The result will be undefined if negative integers are included in the input.

Parameters:

a - the array to be sorted

Returns:

the array with the result;

drawSparseSample

public static int[] drawSparseSample(int n,
                                     int N,
                                     java.util.Random r)
                              throws java.lang.IllegalArgumentException

Draws n distinct integers from 0, 1, ..., N - 1, randomly ordered, using a partial Fisher-Yates shuffle and a hash map. The idea of using a hash map is from

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.

Throws:

java.lang.IllegalArgumentException