vsmc::U01SequenceSorted< RNGType, RealType > Class Template Reference

Generate a fixed length sequence of uniform \([0,1)\) random variates by sorting. More...

#include <vsmc/rng/u01_sequence.hpp>

Public Types
using	result_type = RealType

Public Member Functions
	U01SequenceSorted (std::size_t N, RNGType &rng)
result_type	operator() (std::size_t n)
result_type	operator[] (std::size_t n)

Detailed Description

template<typename RNGType, typename RealType = double>
class vsmc::U01SequenceSorted< RNGType, RealType >

Generate a fixed length sequence of uniform \([0,1)\) random variates by sorting.

This is primarily used in resampling algorithms within the library but can be used for other purposes. It deals with the usage case similar to the following,

const std::size_t N = 1000;
std::mt19937 rng;
std::uniform_real_distribution<double> runif;
std::vector<double> u01(N);
for (std::size_t i = 0; i != N; ++i)
    u01[i] = runif(rng);
std::sort(u01.begin(), u01.end());
for (std::size_t i = 0; i != N; ++i)
    do_something_with_u01(u01[i]);

In the above example, one want N uniform random variates, and having them sorted. The sorted sequence is accessed sequentially. There are two undesired effects. First the program has a runtime cost \(O(N\log N)\). Second, it has a memory cost \(O(N)\). The presented class can be used in place of the temporary vector in the following fashion.

const std::size_t N = 1000;
std::mt19937 rng;
U01SequenceSorted<std::mt19937> u01(N, rng);
for (std::size_t i = 0; i != N; ++i)
    do_something_with_u01(u01[i]);

The above program will has a runtime cost \(O(N)\) and a memory cost \(O(1)\). However, the overloaded operator[] has a few restrictions. Most importantly, it is a forward one-pass operation. More specifically, let n be the calling argument and nlast be the calling argument of the last time it is called.

• n can only be either 0, nlast, or nlast + 1
• n can be at most N - 1.

Definition at line 131 of file u01_sequence.hpp.

Member Typedef Documentation

template<typename RNGType, typename RealType = double>

using vsmc::U01SequenceSorted< RNGType, RealType >::result_type = RealType

Definition at line 134 of file u01_sequence.hpp.

Constructor & Destructor Documentation

template<typename RNGType, typename RealType = double>

vsmc::U01SequenceSorted< RNGType, RealType >::U01SequenceSorted ( std::size_t  N, RNGType &  rng  )

inline

Definition at line 136 of file u01_sequence.hpp.

Member Function Documentation

template<typename RNGType, typename RealType = double>

result_type vsmc::U01SequenceSorted< RNGType, RealType >::operator() ( std::size_t  n )

inline

Definition at line 155 of file u01_sequence.hpp.

template<typename RNGType, typename RealType = double>

result_type vsmc::U01SequenceSorted< RNGType, RealType >::operator[] ( std::size_t  n )

inline

Definition at line 141 of file u01_sequence.hpp.