reservoir

README

Package reservoir samples values uniformly at random
from an unbounded sequence of inputs.

import "kr.dev/reservoir"

For instance, errors. If you have more errors than
you know what to do with, and you can't read them all
or even store them all, and you want to get a rough
idea of what is going on, here's how you could do it:

	rs := reservoir.New[error](100)
	...
	rs.Add(err) // add errors
	...
	rs.Add(err) // unlimited amount of errors
	...
	errs := make([]error, rs.Cap())
	n := rs.Read(errs)
	fmt.Println("sampled:", errs[:n])

This will print up to 100 error values, sampled
uniformly, without replacement, from the sequence
of all errors that have been added to rs so far.

Documentation

Overview

Package reservoir samples values uniformly at random, without replacement, from an unbounded sequence of inputs. It provides a representative sample when the sequence has unknown length or is too big to store in its entirety.

Example (Errors)

package main

import (
	"errors"
	"fmt"

	"kr.dev/reservoir"
)

func main() {
	// Make & populate a new reservoir of errors with capacity 5.
	rs := reservoir.New[error](5)
	rs.Add(errors.New("first"))
	rs.Add(errors.New("second"))
	rs.Add(errors.New("third"))

	// Read a sample into errs.
	errs := make([]error, rs.Cap())
	n := rs.Read(errs)

	fmt.Println("our sample:", errs[:n])
}

Output:

our sample: [first second third]

Example (Many)

package main

import (
	"fmt"
	"math/rand"

	"kr.dev/reservoir"
)

func main() {
	rand.Seed(0)
	// Make & populate a new reservoir of ints with capacity 3.
	rs := reservoir.New[int](3)
	for i := 0; i < 10_000; i++ {
		rs.Add(i)
	}

	// Read a sample into ints.
	ints := make([]int, rs.Cap())
	n := rs.Read(ints)

	fmt.Println("our sample:", ints[:n])
}

Output:

our sample: [9539 5555 7160]

Index

• type Sample
  • func New[T any](cap int) *Sample[T]
  • func (s *Sample[T]) Add(v T)
  • func (s *Sample[T]) Added() int
  • func (s *Sample[T]) Cap() int
  • func (s *Sample[T]) Read(p []T) int
  • func (s *Sample[T]) Reset()

Examples

• Package (Errors)
• Package (Many)

Types

type Sample

type Sample[T any] struct {
	// contains filtered or unexported fields
}

A Sample collects a fixed number of items, chosen uniformly at random, from an unbounded input sequence. The number of items collected is its capacity.

The zero value is a valid Sample with a capacity of 0. (It will not sample any items.)

func New

func New[T any](cap int) *Sample[T]

New returns a new Sample with capacity cap.

func (*Sample[T]) Add

func (s *Sample[T]) Add(v T)

Add adds v to s with a probability adjusted so that the contents of s at any time are chosen uniformly at random from the inputs so far.

func (*Sample[T]) Added

func (s *Sample[T]) Added() int

Added returns the number of calls to Add.

func (*Sample[T]) Cap

func (s *Sample[T]) Cap() int

Cap returns the capacity of s.

func (*Sample[T]) Read

func (s *Sample[T]) Read(p []T) int

Read reads the current contents of s into p. It returns the number of values read, at most the capacity of s.

func (*Sample[T]) Reset

func (s *Sample[T]) Reset()

Reset empties s.