Seeded reservoir sampling (Algorithm R): Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Keep the first k positions, then consider each later item for a uniformly selected reservoir replacement.

Fill k reservoir slots with the first k items. For each later input index i, draw uniformly from zero through i; replace that reservoir slot only if the draw is below k.

Open the 3D visualization

Seeded reservoir sampling (Algorithm R) example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Seeded reservoir sampling (Algorithm R)

Selecting a fixed-size sample during a single pass without retaining the entire stream.

Choosing an alternative

Fisher-Yates needs the input array available for swaps. Reservoir Algorithm R retains only k sample items and processes each later record once. The view does not implement Vitter Algorithm Z skipping.

Worked example: input and state changes

Example input

1,2,3,4,5,6,7,8 | 3 | 17

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Initialize the reservoir with the first 3 items.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        3
      ],
      "active": [],
      "result": 17,
      "output": [
        1,
        2,
        3
      ]
    }
  2. Step 2: Input index 4 is not selected.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        4
      ],
      "active": [],
      "result": 507111939,
      "output": [
        1,
        2,
        4
      ]
    }
  3. Step 3: Input index 5 replaces reservoir slot 0.

    State at this checkpoint
    {
      "values": [
        6,
        2,
        4
      ],
      "active": [
        0
      ],
      "result": 1815247477,
      "output": [
        6,
        2,
        4
      ]
    }
  4. Step 5: Input index 7 replaces reservoir slot 2.

    State at this checkpoint
    {
      "values": [
        6,
        2,
        8
      ],
      "active": [
        2
      ],
      "result": 122498987,
      "output": [
        6,
        2,
        8
      ]
    }
  5. Step 6: Sample complete; final PRNG state 122498987.

    State at this checkpoint
    {
      "values": [
        6,
        2,
        8
      ],
      "active": [],
      "result": 122498987,
      "output": [
        6,
        2,
        8
      ]
    }

Expected final state

Sample complete; final PRNG state 122498987.

Complexity and input bounds

Family: Randomized. Time complexity: O(n) expected time; O(k) storage.

Implementation detail: Inputs contain at most 24 values, with k from zero through n. The reservoir retains slot order. Reproducible Park-Miller draws use rejection sampling; downloads return final generator state and write the k selected values. k equal to n copies the entire input without drawing.

Space complexity: O(k) sample output and O(1) extra generator state, plus saved visualization frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..24 values 0..99 | sample size k 0..n | seed 1..2147483646. Duplicate values retain distinct input positions.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Draw from the full processed prefix, not only the reservoir size. Equal values at different input positions remain separate items. A zero-size sample consumes no draws in this contract.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
1
2
3
4
5
6
7
8
9
// Reservoir Algorithm R, n 0..24 values 0..99, k 0..n, output capacity at least k. Initial reservoir copies the first k positions. Later input i draws j uniformly in 0..i; replaces slot j only when j<k. Duplicate values retain separate positions. Seed 1..2147483646; Park-Miller with overflow-safe Schrage arithmetic and rejection sampling exactly as shuffle. Returns final PRNG state, or -1 for invalid seed. k=0 consumes no draws; k=n copies all items without draws. Reservoir slot order is retained. O(n) expected time, O(k) output and O(1) auxiliary scratch. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(a, n, k, seed, output) {
    if (seed < 1 || seed > 2147483646) { return -1; }
    let state = seed; let bound = 0; let choice = 0; let accepted = 0; let value = 0; let limit = 0;
    for (let i = 0; i < k; i++) { output[i] = a[i]; }
    if (k == 0) { return state; }
    for (let i = k; i < n; i++) { bound = i+1; limit = 2147483646-(2147483646%bound); accepted = 0; while (accepted == 0) { state = 16807*(state%127773)-2836*(Math.floor(state / 127773)); if (state <= 0) { state += 2147483647; } value = state-1; if (value < limit) { choice = value%bound; accepted = 1; } } if (choice < k) { output[choice] = a[i]; } }
    return state;
}

Source

Vitter discusses Algorithm R and attributes it to Alan Waterman; the playground implements R, not the paper faster Algorithm Z. Park-Miller supplies deterministic pseudorandom draws.