sample#

template<class _PopulationIterator, class _PopulationSent, class _SampleIterator, class _Distance, class _UniformRandomNumberGenerator>
inline _SampleIterator cuda::sample(
_PopulationIterator __first,
_PopulationSent __last,
_SampleIterator __output_iter,
_Distance __n,
_UniformRandomNumberGenerator &&__g
)#

Selects __n elements from [__first, __last) without replacement, in population order.

Implements Vitter’s Method D, “An Efficient Algorithm for Sequential Random Sampling”, ACM Transactions on Mathematical Software, Vol. 13, No. 1, March 1987, pages 58-67 (https://www.ittc.ku.edu/~jsv/Papers/Vit87.RandomSampling.pdf).

Unlike cuda::std::sample, which reads every population element, this algorithm reads exactly the min(__n, __last - __first) selected elements and draws O(__n) random numbers. It requires a random access population iterator so that skipped elements are never touched. Each selected element is written in increasing population order, so the result is stable.

The gap distribution is computed in double. The population size must therefore be exactly representable as a double, that is, at most 2^53.

Parameters:

  • __first – [in] Beginning of the population

  • __last – [in] End of the population

  • __output_iter – [out] Beginning of the destination range

  • __n – [in] Number of elements to select

  • __g – [inout] Uniform random number generator

Returns:

The end of the written destination range

On this page