Reservoir Sampling für iOS auf dem Cloud-Mac testen

Nach der Entwicklung einer Logfilterfunktion unter Windows sollen aus einem Ereignisstrom unbekannter Länge einige wenige Einträge zufällig ausgewählt werden. Alle Einträge zunächst in ein Array zu laden und anschließend zu mischen, würde den Speicherbedarf mit der Eingabemenge wachsen lassen. Auf einem Cloud-Mac lässt sich Reservoir Sampling zunächst mit Swift prüfen und dieselbe Implementierung anschließend in das iOS-Projekt übernehmen. Entscheidend ist nicht, ob das Ergebnis „zufällig aussieht“, sondern ob sich die Auswahlregeln als reproduzierbar prüfbarer Vertrag formulieren lassen.

Stichprobeneinheit und Kapazitätsvertrag festlegen

Dieser Beitrag verwendet Algorithm R: Zunächst werden die ersten k Elemente behalten. Beim t-ten Element wird eine ganze Zahl j gleichverteilt zwischen null und t−1 gezogen. Nur wenn j kleiner als k ist, wird der entsprechende Speicherplatz ersetzt. Nach dem Durchlauf beträgt die Auswahlwahrscheinlichkeit jeder Eingabeposition k/n. Der zusätzliche Speicherbedarf liegt bei O(k), die Laufzeit bei O(n).

Diese Aussage setzt voraus, dass jede Ziehung auch bedingt auf die bisherige Historie gleichverteilt bleibt. Dass die Zufallszahlen lediglich im richtigen Wertebereich liegen, reicht für eine faire Auswahl nicht aus.

Zunächst gelten vier Randbedingungen: Die Kapazität darf nicht negativ sein; bei Kapazität null wird eine leere Stichprobe zurückgegeben, ohne die Eingabe zu konsumieren; enthält die Eingabe weniger Elemente als die Kapazität, werden alle behalten; gleiche Werte nehmen entsprechend ihrer jeweiligen Position getrennt an der Auswahl teil. Die Reihenfolge der Ausgabeelemente ist weder eine zufällige Permutation noch wird die ursprüngliche Reihenfolge garantiert.

Eine faire Auswahl bedeutet nicht, dass jedes Ergebnis anders ausfällt. Wer im Test fordert, dass „zwei aufeinanderfolgende Ergebnisse nicht gleich sein dürfen“, macht ein normales Zufallsergebnis zu einem sporadischen Testfehler.

Zufallsquelle und Auswahllogik trennen

Melden Sie sich am Cloud-Mac von OSXMesh an und führen Sie im Terminal xcrun swift --version aus, um zu prüfen, ob die aktuelle Toolchain Swift ausführen kann. Speichern Sie den folgenden Code als ReservoirCheck.swift. Die Closure erhält eine exklusive Obergrenze. Dadurch verwenden die produktive Zufallsquelle und die vorgegebenen Testziehungen dieselbe Auswahllogik.

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 })

Führen Sie xcrun swift ReservoirCheck.swift aus. Bei Erfolg gibt das Skript nichts aus, bei einem Fehler endet es mit einem Exit-Status ungleich null. Das Skript prüft Vorbedingungen und darf deshalb nicht mit Optimierungsoptionen ausgeführt werden, die Sicherheitsprüfungen abschalten. In der Anwendung müssen extern übergebene Kapazitätswerte vor dem Aufruf des Algorithmus validiert werden, statt bei ungültigen Eingaben den Prozess abbrechen zu lassen.

Die Auswahlregel anhand aller zwölf Pfade prüfen

Werden zwei aus vier möglichen Positionen ausgewählt, gibt es für das dritte Element drei mögliche Ziehungen und für das vierte vier. Insgesamt entstehen damit zwölf Pfade. Unter der oben genannten Annahme zur Zufallsquelle hat jeder Pfad eine Wahrscheinlichkeit von einem Zwölftel. Jede der sechs ungeordneten Positionskombinationen muss daher zweimal auftreten.

Geprüft wird hier die Verteilung der Kombinationen, nicht nur die Häufigkeit einzelner Positionen. Manche fehlerhaften Implementierungen können für alle Elemente annähernd gleiche Randhäufigkeiten liefern und dennoch bestimmte Kombinationen grundsätzlich auslassen.

Das Skript prüft außerdem, dass die Zufallsquelle die Obergrenzen drei und vier erhält und die vorgegebene Ziehungsfolge exakt aufgebraucht wird. Ein Aufruf zu wenig, ein zusätzlicher Aufruf oder die irrtümliche Verwendung der aktuellen Anzahl an Speicherplätzen als Obergrenze führt zum Fehlschlag. Das Sortieren dient ausschließlich dazu, einen Vergleichsschlüssel zu erzeugen. Es darf nicht stillschweigend den Rückgabevertrag der produktiven Funktion verändern.

Dieses kleine Beispiel deckt typische Fehler in der Ersetzungsbedingung auf, ist aber kein mathematischer Beweis für beliebige Eingabegrößen. Vor dem Zusammenführen des Codes müssen weiterhin die Voraussetzungen des Induktionsbeweises geprüft und vollständige Fallprüfungen für weitere kleine Kapazitäten ergänzt werden.

Gleiche Werte und Fallstricke bei Streaming-Eingaben abdecken

Verwenden Sie für Tests mit gleichen Werten Datensätze mit eindeutigen Positionsnummern. Kennzeichnen Sie beispielsweise zwei inhaltlich identische Ereignisse als Position null und Position eins und prüfen Sie, dass keine Position mehrfach ausgewählt wird. Es wäre falsch, einfach die Eindeutigkeit der fachlichen Werte in der Stichprobe zu verlangen. Eine Deduplizierung vor der Auswahl würde das Gewicht der einzelnen Ereigniskategorien verändern und zusätzlichen Speicher benötigen.

Bei Kapazität eins müssen sowohl das Ersetzen als auch das Überspringen gezielt erzwungen werden. Entspricht die Kapazität der Eingabelänge, darf die Zufallsquelle nicht aufgerufen werden. Ist die Kapazität größer als die Eingabelänge, muss die Ausgabelänge der Eingabelänge entsprechen.

Ergänzen Sie für eine nur einmal konsumierbare Sequenz einen Iterator, der die Lesezugriffe zählt. Bei Kapazität null muss die Anzahl der Lesezugriffe null sein; bei positiver Kapazität darf die Eingabe nur einmal durchlaufen werden. Rufen Sie nicht Array(input) auf, um vorab die Länge zu ermitteln. Selbst wenn die Auswahl danach korrekt wäre, wäre das Speicherziel der Streaming-Verarbeitung bereits verfehlt.

Der Zähler setzt außerdem voraus, dass sich die Anzahl der Eingabeelemente durch Int darstellen lässt. Bei einem endlosen Ereignisstrom muss die Stichprobenziehung mit dem Ende eines Zeitfensters abgeschlossen werden. Diese synchrone Funktion kehrt nicht von selbst zurück. Abbruch und Schließen des Fensters müssen von der übergeordneten Ebene gesteuert werden.

Bei der Integration reproduzierbare Nachweise sichern

Im Produktivbetrieb kann Int.random(in: 0..<upper) die ganzen Zahlen liefern. Verwenden Sie nicht den Modulo einer Zufallszahl, um den gewünschten Wertebereich herzustellen, und übernehmen Sie die feste Ziehungsfolge aus dem Test nicht in die produktive Funktion. Das hier beschriebene Sampling dient der allgemeinen Datenverarbeitung und sollte nicht unmittelbar für sicherheitskritische Ziehungen eingesetzt werden.

Nehmen Sie das Skript in das Repository auf und führen Sie es im Build-Ablauf auf dem Cloud-Mac vor den Projekttests aus. Halten Sie bei einem Fehler mindestens die Eingabepositionen, die Kapazität, die Ziehungsfolge und die Toolchain-Version fest. Protokollieren Sie zur Fehlersuche keine tatsächlichen Ereignisinhalte von Nutzern.

Gliedern Sie die Abnahme abschließend in drei Ebenen: deterministische Randfalltests, die vollständige Prüfung aller Pfade für kleine Beispiele und unabhängige statistische Beobachtungen. Statistische Beobachtungen können eine fehlerhafte Anbindung der Zufallsquelle aufdecken. Zu enge Häufigkeitsschwellen sollten jedoch nicht jeden Commit blockieren. Grundlage einer Regressionsprüfung sollte ein eindeutig beschriebener, reproduzierbarer Fehlerpfad sein – nicht eine einzelne Stichprobe, die zufällig der Intuition widerspricht.

Häufig gestellte Fragen