Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ReservoirSamplingFast< Type, RNG > Class Template Reference

Detailed Description

template<typename Type, typename RNG = std::default_random_engine>
class thrill::common::ReservoirSamplingFast< Type, RNG >

Fast exact implementation of reservoir sampling using skip values.

Algorithm L from Kim-Hung Li: Reservoir Sampling Algorithms of Time Complexity O(n(1+log(N/n))), ACM TOMS 1994. The reservoir size is fixed, new items replace old ones such that all items in the stream are sampled with the same uniform probability.

Definition at line 84 of file reservoir_sampling.hpp.

+ Inheritance diagram for ReservoirSamplingFast< Type, RNG >:

#include <reservoir_sampling.hpp>

Public Member Functions

 ReservoirSamplingFast (size_t size, std::vector< Type > &samples, RNG &rng)
 initialize reservoir sampler More...
void add (const Type &item)
 visit item, maybe add it to the sample. More...
size_t count () const
 number of items seen More...
const std::vector< Type > & samples () const
 access to samples More...
size_t size () const
 size of reservoir More...

Private Member Functions

void calc_next_gap ()
 draw gap size from geometric distribution with p = size_ / count_ More...

Private Attributes

size_t count_ = 0
 number of items seen More...
size_t gap_
 number of items to skip until next sample More...
RNG & rng_
 source of randomness More...
std::vector< Type > & samples_
 reservoir More...
size_t size_
 size of reservoir More...
< double > 
 uniform [0.0, 1.0) distribution More...
double W_

Constructor & Destructor Documentation

ReservoirSamplingFast ( size_t  size,
std::vector< Type > &  samples,
RNG &  rng 

initialize reservoir sampler

Definition at line 88 of file reservoir_sampling.hpp.

Member Function Documentation

void add ( const Type &  item)

visit item, maybe add it to the sample.

Definition at line 97 of file reservoir_sampling.hpp.

void calc_next_gap ( )

draw gap size from geometric distribution with p = size_ / count_

Definition at line 155 of file reservoir_sampling.hpp.

Referenced by ReservoirSamplingFast< ValueType, decltype(rng_)>::add().

size_t count ( ) const

number of items seen

Definition at line 132 of file reservoir_sampling.hpp.

const std::vector<Type>& samples ( ) const

access to samples

Definition at line 135 of file reservoir_sampling.hpp.

size_t size ( ) const

size of reservoir

Definition at line 129 of file reservoir_sampling.hpp.

Member Data Documentation

size_t count_ = 0
double W_

random value for gap calculation, distribution: largest value in a sample of Uniform(0, old_W) of size size_, where old_W is 1 initially

Definition at line 146 of file reservoir_sampling.hpp.

Referenced by ReservoirSamplingFast< ValueType, decltype(rng_)>::calc_next_gap(), and ReservoirSamplingFast< ValueType, decltype(rng_)>::ReservoirSamplingFast().

The documentation for this class was generated from the following file: