A Go (golang) library for efficient weighted random picking
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.
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
| Item | Cost |
|---|---|
| Time to initialize | O(n) |
| Data structure storage | O(n) |
| Time to pick an item | O(1) |
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
For usage, examples and documentation, see GoDoc