[Rd] uniform sampling without replacement algorithm

Pavel S. Ruzankin ruzankin at math.nsc.ru
Tue Oct 17 19:55:01 CEST 2017

Let us consider the current uniform sampling without replacement 
algorithm. It resides in function do_sample in
Its complexity is obviously O(n), where the sample is selected from 
1...n, since the algorithm has to create a vector of length n. So when 
the sample size is much lesser than n, the algorithm is not effective. 
Algorithms with average complexity O(s log s), were s is the sample 
size, were described long ago. E.g. see
Here the Tree algorithm has complexity O(s log s). I suppose that there 
may be algorithms with complexity close to s. Is somebody planning to 
implement some more effective algorithm?

More information about the R-devel mailing list