README.md
1# weightedrand :balance_scale:
2
3[](https://pkg.go.dev/github.com/mroth/weightedrand)
4[](https://www.codefactor.io/repository/github/mroth/weightedrand)
5[](https://github.com/mroth/weightedrand/actions)
6[](https://codecov.io/gh/mroth/weightedrand)
7
8> Fast weighted random selection for Go.
9
10Randomly selects an element from some kind of list, where the chances of each
11element to be selected are not equal, but rather defined by relative "weights"
12(or probabilities). This is called weighted random selection.
13
14## Usage
15
16```go
17import (
18 /* ...snip... */
19 wr "github.com/mroth/weightedrand"
20)
21
22func main() {
23 rand.Seed(time.Now().UTC().UnixNano()) // always seed random!
24
25 chooser, _ := wr.NewChooser(
26 wr.Choice{Item: "��", Weight: 0},
27 wr.Choice{Item: "��", Weight: 1},
28 wr.Choice{Item: "��", Weight: 1},
29 wr.Choice{Item: "��", Weight: 3},
30 wr.Choice{Item: "��", Weight: 5},
31 )
32 /* The following will print �� and �� with 0.1 probability, �� with 0.3
33 probability, and �� with 0.5 probability. �� will never be printed. (Note
34 the weights don't have to add up to 10, that was just done here to make the
35 example easier to read.) */
36 result := chooser.Pick().(string)
37 fmt.Println(result)
38}
39```
40
41## Performance
42
43The existing Go library that has a comparable implementation of this is
44[`github.com/jmcvetta/randutil`][1], which optimizes for the single operation
45case. In contrast, this library creates a presorted cache optimized for binary
46search, allowing repeated selections from the same set to be significantly
47faster, especially for large data sets.
48
49[1]: https://github.com/jmcvetta/randutil
50
51Comparison of this library versus `randutil.ChooseWeighted` on my workstation.
52For repeated samplings from large collections, `weightedrand` will be much
53quicker:
54
55| Num choices | `randutil` | `weightedrand` | `weightedrand -cpu=8`* |
56| ----------: | -------------: | -------------: | ---------------------: |
57| 10 | 201 ns/op | 38 ns/op | 2.9 ns/op |
58| 100 | 267 ns/op | 51 ns/op | 4.1 ns/op |
59| 1,000 | 1012 ns/op | 67 ns/op | 5.4 ns/op |
60| 10,000 | 8683 ns/op | 83 ns/op | 6.9 ns/op |
61| 100,000 | 123500 ns/op | 105 ns/op | 12.0 ns/op |
62| 1,000,000 | 2399614 ns/op | 218 ns/op | 17.2 ns/op |
63| 10,000,000 | 26804440 ns/op | 432 ns/op | 35.1 ns/op |
64
65**: Since `v0.3.0` weightedrand can efficiently utilize a single Chooser across
66multiple CPU cores in parallel, making it even faster in overall throughput. See
67[PR#2](https://github.com/mroth/weightedrand/pull/2) for details. Informal
68benchmarks conducted on an Intel Xeon W-2140B CPU (8 core @ 3.2GHz,
69hyperthreading enabled).*
70
71Don't be mislead by these numbers into thinking `weightedrand` is always the
72right choice! If you are only picking from the same distribution once,
73`randutil` will be faster. `weightedrand` optimizes for repeated calls at the
74expense of some initialization time and memory storage.
75
76## Caveats
77
78Note this library utilizes `math/rand` instead of `crypto/rand`, as it is
79optimized for performance, and is not intended to be used for cryptographically
80secure requirements.
81
82## Credits
83
84To better understand the algorithm used in this library (as well as the one used
85in randutil) check out this great blog post: [Weighted random generation in Python](https://eli.thegreenplace.net/2010/01/22/weighted-random-generation-in-python/).
86
){kind=link}
){kind=link}