reservoir-sample ( obj sampler -- )
Reservoir Sampling

Prev:	<reservoir-sampler> ( k -- sampler )
Next:	reservoir-sample-iteration ( iteration k obj sampled -- sampled' )

Vocabulary
reservoir-sampling

Inputs

obj	an object
sampler	an object

Outputs
None

Word description
Feeds a sample to a reservoir-sampler which will maintain a vector of samples with equal probability. This word is especially useful when you do not know how many objects will appear but wish to sample them with equal probability, such as in a stream with unknown length.

An example where characters from a string are sampled:

USING: prettyprint io strings math reservoir-sampling kernel accessors io.streams.string ; "Nothing will fundamentally change." [ 10 <reservoir-sampler> [ [ read1 ] swap '[ dup 1string . _ reservoir-sample ] while* ] keep sampled>> >string . ] with-string-reader

Definition

USING: accessors kernel math random sequences ;

IN: reservoir-sampling

: reservoir-sample ( obj sampler -- )
    [ sampled>> length ] [ k>> ]
    [ [ 1 + ] change-iteration -rot ] tri <
    [ sampled>> push ] [
        [ ] [ iteration>> random dup ] [ k>> ] tri <
        [ swap sampled>> set-nth ] [ 3drop ] if
    ] if ;