Message373857
Julia's randsubseq() doesn't allow to specify the _size_ of the output desired. It picks each input element independently with probability p, and the output can be of any size from 0 through the input's size (with mean output length p*length(A)). Reservoir sampling is simply irrelevant to that, although they almost certainly use a form of skip-generation internally.
The quoted docs don't make much sense: for any given p, O(p*N) = O(N). I'm guessing they're trying to say that the mean of the number of times the RNG is called is p*N. |
|
Date |
User |
Action |
Args |
2020-07-17 20:58:14 | tim.peters | set | recipients:
+ tim.peters, rhettinger, mark.dickinson, oscarbenjamin |
2020-07-17 20:58:14 | tim.peters | set | messageid: <1595019494.19.0.995620150454.issue41311@roundup.psfhosted.org> |
2020-07-17 20:58:14 | tim.peters | link | issue41311 messages |
2020-07-17 20:58:14 | tim.peters | create | |
|