Author tim.peters
Recipients mark.dickinson, oscarbenjamin, rhettinger, tim.peters
Date 2020-07-17.20:58:14
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1595019494.19.0.995620150454.issue41311@roundup.psfhosted.org>
In-reply-to
Content
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.
History
Date User Action Args
2020-07-17 20:58:14tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, oscarbenjamin
2020-07-17 20:58:14tim.peterssetmessageid: <1595019494.19.0.995620150454.issue41311@roundup.psfhosted.org>
2020-07-17 20:58:14tim.peterslinkissue41311 messages
2020-07-17 20:58:14tim.peterscreate