Reservoir<T> structv0.1.0

pub struct Reservoir<T> {
    // private fields
}

Offer every item of the stream in turn and the reservoir ends holding a uniformly chosen subset of whatever arrived, each subset of that size equally likely. The caller owns the storage, and its length is the sample size.

Type parameters

Constructors

Reservoir

pub func Reservoir(room: var T[..]) -> Reservoir<T>

A reservoir that will fill room.

Returns: an empty reservoir that will keep room items

Source

Methods

Length

pub func Length(self: &Reservoir<T>) -> uint

How many items the reservoir currently holds, which is the smaller of the sample size and the number offered.

Returns: how many items it currently holds

Source

Seen

pub func Seen(self: &Reservoir<T>) -> uint

How many items have been offered.

Returns: how many items have been offered to it in total

Source

Related

Offer<G, T>

pub func Offer<G: RandomGenerator, T>(
    generator: &var G,
    reservoir: &var Reservoir<T>,
    item: T
)

Offers item to reservoir. Algorithm R: while the reservoir has room the item is kept outright, and afterwards the item replaces a uniformly chosen existing entry with probability equal to the sample size over the number seen. That is what keeps every subset equally likely at every moment, not merely at the end — so a stream can be cut short and the sample is still uniform over what arrived.

Source

Type parameters

Parameters