4 ms·
I don't understand the section on the coupon collector's problem and its relevance to beartype. The coupon collector problem is talking about the expected numbe
by dwohnitmok 5y ago
I don't understand the section on the coupon collector's problem and its relevance to beartype. The coupon collector problem is talking about the expected number of random beartype-style checks it would take to fully check every element in a collection (basically how long on average it would take to do the same thing typeguard does).
But I fail to see how that's relevant to beartype. Beartype's constant-time runtime has nothing to do with the coupon collector problem. It has to do with the simple fact that no matter how large the container beartype will only sample one random element from that container.
Likewise, when the README mentions
> Since h ≥ 1, beartype samples at least as many items each call as assumed in the usual coupon collector's problem and thus paradoxically takes a fewer number of calls on average to check all items of a container containing arbitrarily many subcontainers as it does to check all items of a container containing no subcontainers.
that's just because beartype happens to check one element from each level of nesting of a container so a deeply nested container just gets more checks in a single call than a non-nested container right? If I compare a list with 50 elements and a list with 50 levels of nesting in beartype but a single element underneath all that nesting, clearly the latter only requires a single call to fully type-check while the former takes 225 calls to fully check on average. But that's just because beartype is doing a different amount of work in each case, since in the latter case beartype samples all 50 levels all at once.
Unless I'm missing something the entire discussion on the coupon collector problem seems irrelevant.
- spicybright 5y agoOof, if it really picked elements at random to type check, I'd actually say that'd be "unbearable"
- zbentley 5y agoThat's what it does.