reservoir-sampling.H File Reference

Reservoir sampling for random selection from data streams. More...

#include <chrono>
#include <cstdint>
#include <limits>
#include <memory>
#include <iterator>
#include <gsl/gsl_rng.h>
#include <ah-errors.H>
#include <tpl_array.H>

Include dependency graph for reservoir-sampling.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Reservoir_Sampler< T >
	Incremental reservoir sampler (Algorithm R). More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<std::input_iterator Itor, std::sentinel_for< Itor > Sent>
auto	Aleph::reservoir_sample (Itor beg, Sent end, size_t k, unsigned long seed=static_cast< unsigned long >(std::chrono::high_resolution_clock::now().time_since_epoch().count()))
	Convenience function to sample k elements from a range.

Detailed Description

Reservoir sampling for random selection from data streams.

Provides the Reservoir_Sampler class and convenience functions to randomly select k elements from a sequence of unknown length in a single pass (O(n) time, O(k) space).

Author

Leandro Rabindranath León

Definition in file reservoir-sampling.H.