[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