proposal: Go 2: math/rand: Add Rand.choose(from int, choose int, replace bool) []int

[wking]

This generalizes the current Perm, which could be implemented as:

func (r *Rand) Perm(n int) []int {
  choices, err := r.Choose(n, n, false)
  if err != nil {
    panic(err)
  }
  return choices
}

(although see here for replacing Perm with Shuffle).

A Choose method could also replace Intn:

func (r *Rand) Intn(n int) int {
  choices, err := r.Choose(n, 1, true)
  if err != nil {
    panic(err)
  }
  return choices[0]
}

It would also allow for optimizing situations where you would currently use multiple Intn calls. For example, if n was 256, you could calculate up to eight draws from one Uint64 call. The token-generation use case from here would be:

charset := "1234567890abcdefghijklmnopqrstuvwxyz"
token := make([]byte, 22)
choices, err := r.Choose(len(charset), len(token), true)
if err != nil {
  return err
}
for i, choice := range choices {
  token[i] = choice
}

although you'd want something like #25531 to get a crypographically secure source behind those choices. That seems both more efficient and more readable than other approaches I've seen to generating random tokens in bases that are not powers of two.

[ianlancetaylor]

Could you write a sample doc comment for the new function? Thanks.

[wking]

Could you write a sample doc comment for the new function?

Here's a play with the docs and a first pass at an implementation. I'll inline the doc here for folks who want to make inline comments:

// Choose draws choose times from the range [0,from) with(out)
// replacement.  For example, r.Choose(10, 3, true) draws 3 times from
// [0,10) with replacement, which is equivalent to []int{r.Intn(10),
// r.Intn(10), r.Intn(10)}.  And r.Choose(10, 10, false) draws 10
// times from [0,10) without replacement, which is equivalent to
// r.Perm(10).
//
// Choose will return an error if choose > from and replace is false,
// or if from < 1.
func (r Rand) Choose(from int, choose int, replace bool) ([]int, error) {

[ianlancetaylor]

Thanks. That seems possible to write outside the standard library, in a go-gettable package. Is it widely used enough that it ought to be in the standard library? Consider https://golang.org/doc/faq#x_in_std .

[wking]

That seems possible to write outside the standard library, in a go-gettable package. Is it widely used enough that it ought to be in the standard library? Consider https://golang.org/doc/faq#x_in_std .

Moving all of math/rand out of the stdlib has been suggested before in #24800, although if you went that route you'd need to vendor it for these:

$ git grep math/rand go1.10.2 -- src
go1.10.2:src/archive/zip/writer_test.go
go1.10.2:src/bytes/buffer_test.go
go1.10.2:src/bytes/bytes_test.go
go1.10.2:src/cmd/compile/internal/gc/pgen.go
...

But it looks like we already vendor x/crypto, x/net, and x/text, so that's probably not a blocker. But wherever the rand package lives, I think the goal should be to provide flexible primitives for consumers.

By adding Choose we can deprecate (and, with Go 2, drop) the current Rand.Intn and Rand.Perm, while also enabling more efficient approaches to random token generation and similar cases (as I outlined in my initial post here). And even looking only within math/rand, the implementation I've mocked up seems more efficient than the current Perm. For example, see this updated play, which shows:

drawing an int63
Choose emulating multiple Intn: [5 0 5 5 6]
drawing an int63
Choose emulating Perm: [2 4 7 8 6 1 0 5 9 3]
drawing an int63
drawing an int63
drawing an int63
drawing an int63
drawing an int63
drawing an int63
drawing an int63
drawing an int63
drawing an int63
drawing an int63
rand.Perm: [7 0 4 6 2 5 8 9 1 3]

where rand.Perm(10) draws 10 int63s while Choose(10, 10, false) only draws one. If this is useful enough for math/rand to want it internally, do I need to collect more evidence to argue for making it public?

[ianlancetaylor]

If this is useful enough for math/rand to want it internally, do I need to collect more evidence to argue for making it public?

Well, yes, I think so. Intn and Perm are simple APIs, easy to understand and to use. I don't think we would drop them even if we added Choose. Every additional API carries a cost. Adding an internal version of choose and using it to implement Perm may be an easy win with relatively little cost. Adding an external API Choose means documenting it and carrying it forward forever. The fact that Chose might be useful for implementing Perm isn't especially relevant to whether it should be added to the public API.

[wking]

Adding an internal version of choose and using it to implement Perm may be an easy win with relatively little cost.

I've retitled this issue to use rand.choose. Can we re-scope the issue to be about adding an internal choose helper? If/when that lands in Go, we can revisit whether or not it deserves to be made public?

[deanveloper]

// Choose draws choose times from the range [0,from) with(out)
// replacement. For example, r.Choose(10, 3, true) draws 3 times from
// [0,10) with replacement, which is equivalent to []int{r.Intn(10),
// r.Intn(10), r.Intn(10)}. And r.Choose(10, 10, false) draws 10
// times from [0,10) without replacement, which is equivalent to
// r.Perm(10).

So what you're saying is this would be easy to implement on our own? Isn't the whole purpose of the Go stdlib to have minimal tooling?

Can we re-scope the issue to be about adding an internal choose helper? If/when that lands in Go, we can revisit whether or not it deserves to be made public?

It would be good to have an alternative to rand.Perm(100)[:5]. Creating large permutations may take up a lot of memory, so having an option to have a partial permutation may be good. rand.Choose(100, 5) may be good, and rand.Perm(100) could perhaps be completely replaced with rand.Choose(100, 100) in Go 2.

Essentially, using rand.Choose with replacement is stupid. Just initialize an array with a for loop. Ain't that hard. Also, boolean flags on functions are bad ideas. Just make two functions and name them accordingly. Once you make a separate function for ChooseWithReplace:

// n: the limit for Intn
// m: the size of the slice
func ChooseWithReplace(n, m int) []int {
    slice := make([]int, m)
    for i := range slice {
        slice[i] = Intn(n)
    }
    return slice
}

You realize that a function like this shouldn't be in the standard library anyway.

TL;DR: Remove the boolean flag, don't implement choosing with replacement. Create a function that creates partial permutations, have rand.Perm() either use the new function, or remove rand.Perm() entirely in favor of this one

[wking]

So what you're saying is this would be easy to implement on our own? Isn't the whole purpose of the Go stdlib to have minimal tooling?

I'm having trouble parsing this. Are you saying "why keep Intn and Perm one you have Choose?"? I'd be fine dropping them, but @ianlancetaylor wants to keep them. If there is stdlib-maintainer appetite for Perm and Intn as shims around a public Choose, I'm fine with that.

It would be good to have an alternative to rand.Perm(100)[:5]...

This argument for a public Choose (without replacement) makes sense to me. But for the first stage of this I'm fine with a private choose, and we can return to discussing public APIs if/when that succeeds.

Essentially, using rand.Choose with replacement is stupid. Just initialize an array with a for loop. Ain't that hard.

I agree that it's not hard, but it is inefficient (just like Perm(100)[:5]). For example, one 64-bit draw has enough data for four 16-bit ints. But the current Intn backend will make four int63 draws for four successive Intn(65535) calls anyway. You could work around that with a rand backend that saved leftover bits for future calls, or you could expose Choose (with replacement) to give callers a way to tell the library "don't stop after generating one of these, I'll need 100", etc. But the current implementation/API gives you no way to do this efficiently. But I'm fine leaving this unresolved while we work out whether we want an internal choose behind Perm.

Also, boolean flags on functions are bad ideas. Just make two functions and name them accordingly. Once you make a separate function for ChooseWithReplace...

I think it's a useful optimization. But I'd be fine with caching unused bits instead. Which approach makes more sense in the API can get sorted out if/when we have an internal choose. And I'm fine with two functions to avoid a boolean argument, but again, I think we can punt on that until we have a backing implementation to expose.

[deanveloper]

I'm having trouble parsing this. Are you saying "why keep Intn and Perm one you have Choose?"? I'd be fine dropping them, but @ianlancetaylor wants to keep them. If there is stdlib-maintainer appetite for Perm and Intn as shims around a public Choose, I'm fine with that.

I was saying "why use Choose (with replacement) if it's easily implementable by successive Intn calls"

But the current Intn backend will make four int63 draws for four successive Intn(65535) calls anyway.

Then don't use Intn, use Read. If you're optimized to the point of using an int16 then I feel that you should be at the low-level of using Read.

[wking]

If you're optimized to the point of using an int16 then I feel that you should be at the low-level of using Read.

That's a valid position, but see the token-generation discussion in #25531 for how it's not always trivial. I think getting an efficient implementation into the stdlib, where everyone can share the benefits, is useful. Especially if we deprecate less-general APIs as part of that, since fewer API methods seems like a win for stdlib maintainers. But if the stdlib is not interested in facilitating efficient token generation, that's a maintainer call, and this can all live in an external library.

[rsc]

Even though we are not moving math/rand outside the standard library, this specific function can easily be implemented outside the standard library and seems too special-purpose to warrant adding to the core math/rand.

[wking]

Even though we are not moving math/rand outside the standard library, this specific function can easily be implemented outside the standard library and seems too special-purpose to warrant adding to the core math/rand.

That addresses the API portion of this. Is there interest in improving the over-drawing in Intn and Perm's current implemtations without changing the public API?

[rsc]

Not particularly, no. We try not to change the output of these functions from release to release.

[wking]

Not particularly, no. We try not to change the output of these functions from release to release.

Right, but for Go 2 (as this issue is should be tagged)?