sample

README

sample

Sampling with weights

Usage

package main

import (
	"fmt"

	"github.com/LK4D4/sample"
)

type weightedInt struct {
	elt    int
	weight float64
}

func (w weightedInt) Weight() float64 {
	return w.weight
}

func SampleInt(w []sample.Weighted, k int) ([]int, error) {
	s, err := sample.Sample(w, k)
	if err != nil {
		return nil, err
	}
	var res []int
	for _, wi := range s {
		res = append(res, wi.(weightedInt).elt)
	}
	return res, nil
}

func main() {
	var wl []sample.Weighted
	for i := 1; i < 32; i++ {
		wl = append(wl, weightedInt{i, float64(i)})
	}
	n, err := SampleInt(wl, 3)
	if err != nil {
		panic(err)
	}
	fmt.Println(n)
}

Documentation

Overview

Package sample solves problem of choosing k random elements with weights from some(potentially big) sequence. Such problem is called Reservoir Sampling.

Index

• Variables
• type Weighted
  • func Choice(input []Weighted) (Weighted, error)
  • func Sample(input []Weighted, k int) ([]Weighted, error)

Variables

var (
	// ErrEmptyInput used when input sequence is empty - nothing to sample.
	ErrEmptyInput = errors.New("input sequence empty")
	// ErrTooBigSample returned when requested sample is bigger than input sequence.
	ErrTooBigSample = errors.New("requested sample size exceeds size of sequence")
)

Types

type Weighted

type Weighted interface {
	Weight() float64
}

Weighted is interface for "weighted" elements in sequence.

func Choice

func Choice(input []Weighted) (Weighted, error)

Choice returns Weighted element with respect to its weight from slice of Weighted elements.

Complexity is O(n), memory usage is O(1).

func Sample

func Sample(input []Weighted, k int) ([]Weighted, error)

Sample samples random k elements with respect to their weights from slice of Weighted elements.

Complexity is O(n*log(k)), O(k) memory is used.