sampling

README

Reservoir Sampling Algorithms

Comparison of reservoir sampling algorithms.

Results

go test -run='^$' -bench=. -count=10 > results.txt && benchstat results.txt

goos: linux
goarch: amd64
pkg: github.com/MrAlias/reservoir-sampling
cpu: Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
              │ results.txt │
              │   sec/op    │
RNG/Int63-8     3.347n ± 2%
RNG/Float64-8   3.923n ± 5%
Sampler/R-8     22.08n ± 2%
Sampler/L-8     2.312n ± 5%
Sampler/X-8     3.338n ± 7%
Sampler/Z-8     2.372n ± 8%
geomean         4.176n

References

• Reservoir Sampling Wiki
• Vitter, Jeffrey S. (1 March 1985). "Random sampling with a reservoir"
• Java implementation version

Documentation

Index

• type L
  • func NewL(n int) *L
  • func (l *L) Offer(value float64)
• type R
  • func NewR(n int) *R
  • func (r *R) Offer(value float64)
• type X
  • func NewX(n int) *X
  • func (x *X) Offer(value float64)
• type Z
  • func NewZ(n, threshold int) *Z
  • func (z *Z) Offer(value float64)

Types

type L

type L struct {
	// contains filtered or unexported fields
}

func NewL

func NewL(n int) *L

func (*L) Offer

func (l *L) Offer(value float64)

type R

type R struct {
	// contains filtered or unexported fields
}

func NewR

func NewR(n int) *R

func (*R) Offer

func (r *R) Offer(value float64)

type X

type X struct {
	// contains filtered or unexported fields
}

func NewX

func NewX(n int) *X

func (*X) Offer

func (x *X) Offer(value float64)

type Z

type Z struct {
	// contains filtered or unexported fields
}

func NewZ

func NewZ(n, threshold int) *Z

func (*Z) Offer

func (z *Z) Offer(value float64)