Reservoir sampling

Draws a uniform sample of fixed size from a stream of unknown length in a single pass, using Algorithm L (Li 1994), which skips ahead geometrically instead of drawing a random number for every item (Vitter 1985).

Usage

design_reservoir(n, max_items = Inf)

Arguments

n

Reservoir size. Fewer items come back if the stream is shorter; the result is never padded.

max_items

Stop after reading this many items. Rows past it are never read, so inclusion_prob() gives them 0 and gives the rows before it n / max_items rather than n / N. Inf reads the whole stream. Warns when the cap actually truncates.

Value

A design object, for use with draw().

Details

A data frame is not a stream: its length is already known and it already fits in memory, so draw() takes a direct vectorised path for one. Reach for the streaming path when the data genuinely does not fit — pass a connection, or a function that returns the next item and NULL at end of stream. For those, draw() returns a list rather than a data frame.

References

Vitter, J. S. (1985). Random sampling with a reservoir. ACM Transactions on Mathematical Software, 11, 37–57.

Li, K.-H. (1994). Reservoir-sampling algorithms of time complexity O(n(1 + log(N/n))). ACM Transactions on Mathematical Software, 20, 481–493.

See also

draw()

Other designs: design_bootstrap(), design_certainty(), design_cluster(), design_multistage(), design_simple(), design_spatial(), design_spread(), design_stratified(), design_systematic(), design_temporal(), design_weighted()

Examples

nrow(draw(data.frame(id = 1:1000), design_reservoir(n = 10), seed = 1))
#> [1] 10

# A real stream: a generator that yields 1..50 then stops
i <- 0
gen <- function() {
  i <<- i + 1
  if (i > 50) NULL else i
}
unlist(draw(gen, design_reservoir(n = 5), seed = 1))
#> [1] 46 14 11  4 32