reservoirSample

reservoirSample(iterable, k, randomSource?): any[]

Defined in: src/reservoir_sample.js:27

Reservoir sampling takes k items uniformly at random from an input of unknown length, in a single pass and using O(k) memory. This makes it useful for sampling from streams, generators, or other iterables that are too large to load into an array first.

This implements Algorithm L, from Li, Kim-Hung. “Reservoir-sampling algorithms of time complexity O(n(1+log(N/n))).” ACM Transactions on Mathematical Software (TOMS) 20.4 (1994): 481-493.

Parameters

iterable

Iterable<any, any, any>

a stream, generator or other iterable

k

number

count of how many elements to take

randomSource?

Function = Math.random

an optional entropy source that returns numbers between 0 inclusive and 1 exclusive: the range [0, 1)

Returns

any[]

k sampled items from the iterable

Example

function* naturalNumbers() {
    let i = 1;
    while (true) {
        yield i++;
    }
}
reservoirSample(naturalNumbers(), 3); // => [482, 1913, 7006]