sampling arbitrary iterables

[bakkot]

This has Random.pickFromList, which is a good and useful function when your list is of known length (though a bad name). But when it's not, you can still usefully sample from it (although it's O(n) to do so). Should we expose that functionality?

[tabatkins]

Yeah, some ability to reservoir sample would be interesting (and very non-trivial to do by hand!)

[tabatkins]

So, hm, doing this is a bit different from the other methods - rather than a one-and-done random choice, it's a stateful object that knows ahead of time how many values it's going to produce, and then you just feed it values as desired, and at any point can ask it for its current "random" choices (chosen uniformly across all values seen so far).

So I guess this would be something like:

namespace Random {
  class Sampler {
    #n;
    #currentSamples;
    constructor(n) { this.#n = n; this.#currentSamples = Array.of(n); }
    show(item) {...}
    samples() { return [...this.#currentSamples]; }
  }
}

Possibly a WeightedSampler variant as well, since there are different optimal algorithms for uniform and weighted samples.

[ljharb]

Couldn't it just spit out an iterator, instead of having a class?

[bakkot]

@tabatkins That would also be useful, but is more complicated than I was thinking - I was imagining taking an iterable and returning either an array (in the case that you want multiple items) or a single item (in the case that you just want one). I.e., just a cheaper (but equivalent) alternative converting your whole iterable to an array and then sampling from it, not something stateful where you might want to sample the current state.

@ljharb No, because earlier samples can change as more items come in.

[tabatkins]

I was imagining taking an iterable and returning either an array

Hm, if we already have the full iterable, couldn't you just automatically use a reservoir algorithm when you see an iterable (instead of a static collection or array-like)? That lets you avoid materializing an Array, and with the "optimal" algorithm you're still using a reasonable amount of randomness. I don't think we need to do a special function just for a reservoir strategy.

[tabatkins]

(Notably, I think all these methods need a precise definition so we know exactly how many bytes are pulled off of the PRNG; we'll need it for SeededPRNG anyway and I want to just reuse that here. So I'm happy to specify that iterables use reservoir sampling to generate it, it's just something that'll be observable so it does need to be specified.)

[bakkot]

Yeah, you could just overload take. I don't love that it would be O(1) on an array and O(n) on any other iterable, but I guess that's OK.

[tabatkins]

It would be O(k) on an array (and Map/Set), and O(k * (1 + log(n/k))) (where n is the size of the iterable and k is how many selections you're making) for other iterables, a lot less than O(n) for large collections and smallish selections. In the single-item case, that's just O(1+log(n)).

(I've gotten a handle on the equal-weighted optimal reservoir algorithm, but don't quite get the math behind the optimal weighted one. But it looks plausible, and has essentially the same runtime O(k * log(n/k)).)

[bakkot]

You can't consume an arbitrary iterator in less than O(n). You can only do better than O(n) if you can skip ahead in constant time, which you can't for iterators.

[tabatkins]

Oh yeah, duh, we're talking different resources, my bad. My numbers were the number of random samplings needed.

The O(1) for Arrays/etc and O(n) for iterables is inherent, unless we intentionally use only iterables just to slow down random-access collections. So I'm a little confused what exactly you "don't love" about this.

[bakkot]

When a method's runtime depends on its input type, that makes it very hard to look at code using that method and notice that it's quadratic or whatever. Having different methods for sampling from arrays vs iterables makes it obvious at a glance when you're doing something expensive.

[tabatkins]

Hm, that's a fair critique. I'm just a little weirded out by the idea of putting in two exactly identical methods whose only difference is one is limited to Arrays/array-likes and works faster.

[bakkot]

"Working faster" is a pretty significant difference IMO.

[tabatkins]

Well, naming suggestions welcome, I guess.

[tabatkins]

Maybe just sampleArray() and takeArray() for the ones that only work on array-likes?