System.Random.Reservoir

Unweighted reservoir algorithm suitable for sampling from data streams of large or unknown size.

Documentation

data Res g a

Wrapper for the state kept by algorithm R. Keeps the sample as an IntMap, the number of elements seen, and the random seed.

Constructors

Res

Fields

• resSample :: !(IntMap a)

  The current sample. Should usually not be modified by hand.

• numSeen :: !Int

  The number of elements seen. Should almost never be modified by hand.

• resSeed :: !g

  The random seed for the sample

Instances

Functor (Res g)

Methods

fmap :: (a -> b) -> Res g a -> Res g b

(<$) :: a -> Res g b -> Res g a

(Show g, Show a) => Show (Res g a)

Methods

showsPrec :: Int -> Res g a -> ShowS

show :: Res g a -> String

showList :: [Res g a] -> ShowS

getSample :: Res g a -> [a]

Extracts the sample as a list.

emptyRes :: RandomGen g => g -> Res g a

Creates a Res with nothing in the sample and with the counter at zero.

reservoirSample

Arguments

:: RandomGen g

=> Int

The maximum number of elements to be in the sample.

-> a

The next element to be considered

-> Res g a

The current wrapped sample

-> Res g a

Jeffrey Vitter's "Algorithm R" for randomly choosing a fixed-size sample from a stream of possibly very large or unknown length. At any point in the sampling, all streamed elements have equal probability of appearing in the sample. Intended to be partially applied on the sample size and used with fold-like functions.