中文
devexamples

Reservoir Sampling For Streams

Uniformly sample a fixed number of items from arrays or one-pass iterables using reservoir sampling with an injectable random source.

JavascriptData Integrity

Code

snippet
export function reservoirSample(items, size, random = Math.random) {
  if (!Number.isInteger(size) || size < 0) {
    throw new RangeError("size must be a non-negative integer");
  }
  if (size === 0) return [];
  const reservoir = items.slice(0, size);
  for (let index = size; index < items.length; index += 1) {
    const candidate = Math.floor(random() * (index + 1));
    if (candidate < size) reservoir[candidate] = items[index];
  }
  return reservoir;
}

export function* reservoirStream(iterable, size, random = Math.random) {
  if (!Number.isInteger(size) || size < 0) {
    throw new RangeError("size must be a non-negative integer");
  }
  if (size === 0) return;
  const reservoir = [];
  let seen = 0;
  for (const item of iterable) {
    if (seen < size) {
      reservoir.push(item);
    } else {
      const candidate = Math.floor(random() * (seen + 1));
      if (candidate < size) reservoir[candidate] = item;
    }
    seen += 1;
  }
  yield* reservoir;
}

Related Examples