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

Detailed Description

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

Implementation of a fast approximation of adaptive reservoir sampling using http://erikerlandson.github.io/blog/2015/11/20/very-fast-reservoir-sampling/ The reservoir size grows logarithmically with the number given to the sampler, new items replace old ones such that all items in the stream are sampled with the same approximately uniform probability.

Growing of the reservoir is implemented trivially by selecting any current item to expand the array. This works well enough if growing steps become rarer for larger streams.

Definition at line 173 of file reservoir_sampling.hpp.

+ Inheritance diagram for ReservoirSamplingGrow< Type, RNG >:

#include <reservoir_sampling.hpp>

Public Member Functions

 ReservoirSamplingGrow (std::vector< Type > &samples, RNG &rng, double desired_imbalance=0.05)
 initialize reservoir sampler More...
 
void add (const Type &item)
 visit item, maybe add it to the sample. More...
 
size_t calc_sample_size (size_t count) const
 calculate desired sample size More...
 
size_t calc_sample_size () const
 calculate desired sample size More...
 
size_t count () const
 number of items seen More...
 
double desired_imbalance () const
 desired imbalance More...
 
const std::vector< Type > & samples () const
 access to samples More...
 
size_t size () const
 size of reservoir More...
 

Private Member Functions

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

Private Attributes

size_t count_ = 0
 number of items seen More...
 
const double desired_imbalance_
 
size_t gap_ = 0
 items to skip until next sample (used in gap algorithm) More...
 
RNG & rng_
 source of randomness More...
 
std::vector< Type > & samples_
 reservoir More...
 
size_t size_ = 0
 size of reservoir More...
 
size_t steps_to_resize = 0
 items to process prior to checking for reservoir resize More...
 

Static Private Attributes

static constexpr bool debug = false
 

Constructor & Destructor Documentation

ReservoirSamplingGrow ( std::vector< Type > &  samples,
RNG &  rng,
double  desired_imbalance = 0.05 
)
inline

initialize reservoir sampler

Definition at line 179 of file reservoir_sampling.hpp.

Member Function Documentation

void add ( const Type &  item)
inline

visit item, maybe add it to the sample.

Definition at line 186 of file reservoir_sampling.hpp.

size_t calc_next_gap ( )
inlineprivate

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

Definition at line 301 of file reservoir_sampling.hpp.

Referenced by ReservoirSamplingGrow< SampleIndexPair >::add().

size_t calc_sample_size ( size_t  count) const
inline

calculate desired sample size

Definition at line 269 of file reservoir_sampling.hpp.

Referenced by SortNode< ValueType, CompareFunction, SortAlgorithm >::wanted_sample_size().

size_t calc_sample_size ( ) const
inline
size_t calc_steps_to_next_resize ( ) const
inlineprivate

calculate number of items/steps to process without checking for sample resize

Definition at line 317 of file reservoir_sampling.hpp.

Referenced by ReservoirSamplingGrow< SampleIndexPair >::add().

size_t count ( ) const
inline

number of items seen

Definition at line 260 of file reservoir_sampling.hpp.

double desired_imbalance ( ) const
inline

desired imbalance

Definition at line 266 of file reservoir_sampling.hpp.

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

access to samples

Definition at line 263 of file reservoir_sampling.hpp.

size_t size ( ) const
inline

size of reservoir

Definition at line 257 of file reservoir_sampling.hpp.

Member Data Documentation

constexpr bool debug = false
staticprivate
const double desired_imbalance_
private

epsilon imbalance: this reservoir sampling works well for the range 0.5 to 0.01. Imbalance 0.5 results in 79 samples for 1 million items, 0.1 in 1992, 0.05 in 6643, 0.02 in 49828, and 0.01 in 199315.

Definition at line 298 of file reservoir_sampling.hpp.

Referenced by ReservoirSamplingGrow< SampleIndexPair >::calc_sample_size(), ReservoirSamplingGrow< SampleIndexPair >::calc_steps_to_next_resize(), and ReservoirSamplingGrow< SampleIndexPair >::desired_imbalance().

size_t gap_ = 0
private

items to skip until next sample (used in gap algorithm)

Definition at line 287 of file reservoir_sampling.hpp.

Referenced by ReservoirSamplingGrow< SampleIndexPair >::add().

RNG& rng_
private
std::vector<Type>& samples_
private
size_t steps_to_resize = 0
private

items to process prior to checking for reservoir resize

Definition at line 289 of file reservoir_sampling.hpp.

Referenced by ReservoirSamplingGrow< SampleIndexPair >::add().


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