Test iOS reservoir sampling on a cloud Mac

After building a log filter on Windows, you need to retain a small random sample from an event stream of unknown length. Loading every record into an array and shuffling it makes memory usage grow with the input. On a cloud Mac, you can validate reservoir sampling in Swift before integrating the same implementation into an iOS project. The goal is not to judge whether the results “look random,” but to turn the selection rules into a contract you can check repeatedly.

Define the sampling unit and capacity contract

This article uses Algorithm R: keep the first k items, then, for the t-th item, draw an integer j uniformly from zero through t−1. Replace the corresponding slot only if j is less than k. Once traversal is complete, every input position has an inclusion probability of k/n. The algorithm uses O(k) extra storage and takes O(n) time.

That result requires every draw to remain uniform conditional on the preceding history. Merely keeping random numbers within the correct range does not guarantee fairness.

Set four boundary rules first: capacity cannot be negative; zero capacity returns an empty sample without consuming the input; inputs shorter than capacity are retained in full; and duplicate values participate separately according to their positions. The output slots are neither a random permutation nor guaranteed to preserve input order.

Fair sampling does not mean getting a different result every time. A test that requires two consecutive results to differ turns a valid random outcome into an intermittent failure.

Separate the random source from the selection logic

After logging in to an OSXMesh cloud Mac, run xcrun swift --version in Terminal to confirm that the current toolchain can run Swift. Save the following code as ReservoirCheck.swift. The closure takes an exclusive upper bound, allowing the production random source and test scripts to share the same selection logic.

func reservoir<S: Sequence>(
    _ input: S,
    capacity: Int,
    draw: (Int) -> Int
) -> [S.Element] {
    precondition(capacity >= 0)
    guard capacity > 0 else { return [] }

    var sample: [S.Element] = []
    var seen = 0

    for value in input {
        seen += 1
        if sample.count < capacity {
            sample.append(value)
        } else {
            let slot = draw(seen)
            precondition(slot >= 0 && slot < seen)
            if slot < capacity {
                sample[slot] = value
            }
        }
    }
    return sample
}

let empty = reservoir([Int](), capacity: 2) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(empty.isEmpty)

let zero = reservoir([1, 2], capacity: 0) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(zero.isEmpty)

let short = reservoir([1, 2], capacity: 3) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(short == [1, 2])

var counts: [String: Int] = [:]

for first in 0..<3 {
    for second in 0..<4 {
        var script = [first, second].makeIterator()
        var bounds: [Int] = []

        let sample = reservoir(0..<4, capacity: 2) { upper in
            bounds.append(upper)
            guard let next = script.next() else {
                preconditionFailure("Draw script exhausted")
            }
            return next
        }

        precondition(bounds == [3, 4])
        precondition(script.next() == nil)
        precondition(sample.count == 2)
        precondition(Set(sample).count == 2)

        let key = sample.sorted().map { String($0) }
            .joined(separator: ",")
        counts[key, default: 0] += 1
    }
}

let expected = ["0,1", "0,2", "0,3", "1,2", "1,3", "2,3"]
precondition(Set(counts.keys) == Set(expected))
precondition(counts.values.allSatisfy { $0 == 2 })

Run xcrun swift ReservoirCheck.swift. A passing run produces no output; a failure exits with a nonzero status. The script relies on precondition checks, so do not run it with optimization options that disable safety checks. In an actual application, validate externally supplied capacity values before calling the algorithm rather than letting invalid input terminate the process.

Enumerate all twelve paths to verify the selection rules

When selecting two of four candidate positions, the third item has three possible draws and the fourth has four, giving twelve paths in total. Under the random-source assumption above, each path has a probability of one in twelve, so each of the six unordered position combinations should appear twice.

This checks the distribution of combinations, not just how often each position appears. Some incorrect implementations can produce nearly equal marginal frequencies for individual items while consistently omitting certain combinations.

The script also verifies that the random source receives upper bounds of three and four and that the scripted draws are exhausted exactly. One missing call, one extra call, or an upper bound mistakenly set to the current number of slots will cause a failure. Sorting is used only to generate comparison keys; it must not silently change the production function’s return contract.

This example is large enough to catch common mistakes in the replacement condition, but it is not a mathematical proof for arbitrary input sizes. Before merging, review the conditions required by the inductive argument and add exhaustive cases for other small input sizes and capacities.

Cover duplicate values and streaming-input pitfalls

Test duplicate values with records that carry unique sequence numbers. For example, label two events with identical content as position zero and position one. Assert that selected positions are distinct, rather than simply asserting that the sample contains unique business values. Deduplicating before sampling changes the weight of each event category and introduces extra storage.

With a capacity of one, test both forced replacement and forced skipping. When capacity equals the input length, the random source should never be called. When capacity exceeds the input length, the output length should equal the input length.

For a sequence that can be consumed only once, add an iterator that counts reads. Zero capacity must cause zero reads; a positive capacity must traverse the input only once. Do not call Array(input) to obtain the length in advance: even if the selected sample is correct, that would defeat the streaming memory requirement.

The counter also requires the number of input items to fit in Int. For an unbounded event stream, finish sampling when a window closes; do not expect this synchronous function to return on its own. Cancellation and window closure belong in the calling layer.

Keep reproducible evidence when integrating

Production code can supply integers with Int.random(in: 0..<upper). Do not force random integers into range with a modulo operation, and do not ship a fixed test script as the production random source. This sampling approach is intended for general data processing, not direct use in security-sensitive drawings.

Commit the script to the repository and run it in the cloud Mac build steps before the project’s tests. For each failure, retain at least the input positions, capacity, sequence of draws, and toolchain version. Do not log the contents of real user events for debugging.

Finally, split validation into three layers: deterministic boundary cases, exhaustive paths for small examples, and independent statistical observation. Statistical observation is useful for detecting incorrectly wired random sources, but overly narrow frequency thresholds should not block every commit. Regressions should be established by explicit, replayable failure paths—not by a sample that happened to defy intuition.

Frequently asked questions