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". Given the elements in the existing sample and a new element, every element has a equal probability of being selected. Intended to be partially applied on the sample size and used with fold-like functions to sample large streams of data.