README
¶
minaguib/weightedrandom
A Go (golang) library for efficient weighted random picking
About
Given a theoretical jar of 1,000 marbles, like so:
| Marble color | Count |
|---|---|
| Red | 500 |
| Blue | 250 |
| Green | 125 |
| Yellow | 120 |
| Transparent | 4 |
| Vantablack | 1 |
You want a solution that allows you to simulate picking a random marble while adhering to the above probabilities. You want it to operate as fast as possible, require as little storage as possible, and efficiently handle large weights and large number of items.
About the implementation
This library implements the Alias picking method as further optimized by Michael D. Vose
Ref. Paper: "A Linear Algorithm For Generating Random Numbers With a Given Distribution" by Michael D. Vose
Ref: Darts, Dice, and Coins: Sampling from a Discrete Distribution by Keith Schwarz
Performance characteristics
| Item | Cost |
|---|---|
| Time to initialize | O(n) |
| Data structure storage | O(n) |
| Time to pick an item | O(1) |
Performance benchmarks
On a MacBook Pro, Intel(R) Core(TM) i5-8279U CPU @ 2.40GHz, 2133 MHz LPDDR3 memory:
$ go test -bench .
goos: darwin
goarch: amd64
pkg: github.com/minaguib/weightedrandom
BenchmarkNew/1_weights-8 126366 8967 ns/op
BenchmarkNew/10_weights-8 126315 9015 ns/op
BenchmarkNew/100_weights-8 112978 9985 ns/op
BenchmarkNew/1000_weights-8 58854 19891 ns/op
BenchmarkNew/10000_weights-8 9981 109303 ns/op
BenchmarkNew/100000_weights-8 1029 1001077 ns/op
BenchmarkNew/1000000_weights-8 112 9697761 ns/op
BenchmarkNew/10000000_weights-8 12 89310961 ns/op
BenchmarkPick/from_1_weights-8 76958226 13.8 ns/op
BenchmarkPick/from_10_weights-8 42556176 26.2 ns/op
BenchmarkPick/from_100_weights-8 43152367 26.0 ns/op
BenchmarkPick/from_1000_weights-8 42600124 26.0 ns/op
BenchmarkPick/from_10000_weights-8 39454466 27.1 ns/op
BenchmarkPick/from_100000_weights-8 31104279 32.5 ns/op
BenchmarkPick/from_1000000_weights-8 17665467 69.6 ns/op
BenchmarkPick/from_10000000_weights-8 11770742 104 ns/op
Usage
For usage, examples and documentation, see GoDoc
Documentation
¶
Overview ¶
Package weightedrandom implements extremely efficient weighted random picking
Example (FiftyFifty) ¶
package main
import (
"fmt"
"math/rand"
"github.com/minaguib/weightedrandom"
)
func main() {
weights := []float64{50, 50}
wr, err := weightedrandom.New(weights)
if err != nil {
return
}
// For example/test purposes only, override internal randomizer with a deterministic one:
wr.Rand = rand.New(rand.NewSource(99))
// Pick 100,000 times and summarize
picked := []uint{0, 0}
for i := 0; i < 100000; i++ {
idx := wr.Pick()
picked[idx]++
}
fmt.Printf("Picked: %v\n", picked)
}
Output: Picked: [50070 49930]
Example (JarOfMarbles) ¶
package main
import (
"fmt"
"math/rand"
"github.com/minaguib/weightedrandom"
)
func main() {
marbles := []struct {
color string
weight uint
picked uint
}{
{"Red", 500, 0},
{"Blue", 250, 0},
{"Green", 125, 0},
{"Yellow", 120, 0},
{"Transparent", 4, 0},
{"Vantablack", 1, 0},
}
// Calculate slice of weights
weights := make([]float64, len(marbles))
for i, info := range marbles {
weights[i] = float64(info.weight)
}
// Initialize a new *WeightedRandom
wr, err := weightedrandom.New(weights)
if err != nil {
return
}
// For example/test purposes only, override internal randomizer with a deterministic one:
wr.Rand = rand.New(rand.NewSource(99))
// Pick 100,000 times and summarize
for i := 0; i < 100000; i++ {
idx := wr.Pick()
marbles[idx].picked++
//fmt.Printf("Picked: %v\n", marbles[idx].color)
}
// Output report
for _, info := range marbles {
fmt.Printf("Color %-11s weight=%3d picked=%5d times\n", info.color, info.weight, info.picked)
}
}
Output: Color Red weight=500 picked=49999 times Color Blue weight=250 picked=24991 times Color Green weight=125 picked=12559 times Color Yellow weight=120 picked=11932 times Color Transparent weight= 4 picked= 415 times Color Vantablack weight= 1 picked= 104 times
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrNoWeights indicates New was called with nil or empty weights ErrNoWeights = fmt.Errorf("Supplied weights can not be empty") )
Functions ¶
This section is empty.
Types ¶
type WeightedRandom ¶
WeightedRandom stores the initialized probability and alias table produced by New
func New ¶
func New(weights []float64) (*WeightedRandom, error)
New accepts as input a slice of float64 weights. At least 1 weight must be given otherwise error ErrNoWeights is returned It computes an internal alias table and returns a *WeightedRandom which is then suitable for calling .Pick() on
func (*WeightedRandom) Pick ¶
func (wr *WeightedRandom) Pick() int
Pick picks a random element and returns its index (as per the order supplied when New was called)
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package jar provides a convenience container API wrapping the underlying weightedrandom library Use Jar if: * You don't want to maintain your own slice/array to use the underlying weightedrandom library's index-based methods * You don't mind the performance overhead of casting your item to/from generic interface{}
|
Package jar provides a convenience container API wrapping the underlying weightedrandom library Use Jar if: * You don't want to maintain your own slice/array to use the underlying weightedrandom library's index-based methods * You don't mind the performance overhead of casting your item to/from generic interface{} |