Tester un échantillonnage réservoir iOS sur un Mac cloud

Après avoir développé sous Windows une fonction de filtrage des journaux, il faut conserver aléatoirement un petit nombre d’enregistrements issus d’un flux d’événements de taille inconnue. Charger tous les enregistrements dans un tableau avant de les mélanger ferait croître la consommation mémoire avec le volume d’entrée. Sur un Mac cloud, on peut d’abord valider l’échantillonnage réservoir en Swift, puis intégrer cette même implémentation au projet iOS. L’essentiel n’est pas de juger si le résultat « a l’air aléatoire », mais de transformer les règles de sélection en un contrat vérifiable de manière reproductible.

Définir l’unité d’échantillonnage et le contrat de capacité

Nous utilisons ici Algorithm R : conserver les k premiers éléments ; à l’arrivée du t-ième élément, tirer uniformément un entier j entre zéro et t−1, puis remplacer l’élément à l’indice j uniquement si j est inférieur à k. À la fin du parcours, chaque position d’entrée a une probabilité k/n d’être retenue. L’espace supplémentaire est de O(k) et le temps de parcours de O(n).

Ce résultat suppose que chaque tirage reste uniforme conditionnellement à l’historique des tirages précédents. Le simple fait de produire des nombres aléatoires dans le bon intervalle ne suffit pas à garantir une sélection équitable.

Fixons d’abord quatre cas limites : la capacité ne peut pas être négative ; une capacité nulle doit renvoyer un échantillon vide sans consommer l’entrée ; si l’entrée contient moins d’éléments que la capacité, tous sont conservés ; les valeurs identiques participent séparément, selon leur position. L’ordre des éléments dans les emplacements de sortie n’est pas une permutation aléatoire et ne garantit pas non plus le respect de l’ordre d’origine.

Une sélection équitable n’implique pas un résultat différent à chaque exécution. Exiger dans un test que « deux résultats consécutifs soient différents » transforme un résultat aléatoire parfaitement normal en échec intermittent.

Séparer la source aléatoire de la logique de sélection

Après vous être connecté au Mac cloud OSXMesh, exécutez xcrun swift --version dans le terminal pour vérifier que la chaîne d’outils actuelle permet d’exécuter Swift. Enregistrez le code suivant dans ReservoirCheck.swift. La closure reçoit une borne supérieure exclusive, ce qui permet à la source aléatoire de production et aux scénarios de test d’utiliser la même logique de sélection.

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

Exécutez xcrun swift ReservoirCheck.swift. En cas de succès, le script ne produit aucune sortie ; en cas d’échec, il se termine avec un code de sortie non nul. Comme il vérifie des préconditions, il ne faut pas l’exécuter avec des options d’optimisation qui désactivent les contrôles de sécurité. Dans une application réelle, validez les paramètres de capacité provenant de l’extérieur avant d’appeler l’algorithme, plutôt que de laisser une entrée invalide provoquer l’arrêt du processus.

Vérifier la règle de sélection en énumérant les douze parcours

Pour retenir deux positions parmi quatre, le troisième élément donne lieu à trois tirages possibles et le quatrième à quatre, soit douze parcours au total. Avec les hypothèses formulées plus haut sur la source aléatoire, chaque parcours a une probabilité d’un douzième. Chacune des six combinaisons non ordonnées de positions doit donc apparaître deux fois.

On vérifie ici la distribution des combinaisons, et pas seulement le nombre d’apparitions de chaque position. Certaines implémentations incorrectes peuvent produire des fréquences marginales presque identiques pour tous les éléments tout en excluant systématiquement certaines combinaisons.

Le script vérifie aussi que les bornes supérieures transmises à la source aléatoire sont bien trois et quatre, et que la séquence de tirages prédéfinie est consommée exactement jusqu’au bout. Un appel en moins, un appel en trop ou l’utilisation erronée du nombre actuel d’emplacements comme borne supérieure fera échouer le test. Le tri sert uniquement à construire une clé de comparaison : il ne doit pas modifier discrètement le contrat de retour de la fonction de production.

Cet exemple de petite taille permet de détecter les erreurs courantes dans la condition de remplacement, mais ne constitue pas une preuve mathématique pour toutes les tailles d’entrée. Avant la fusion du code, il faut encore examiner les conditions du raisonnement par récurrence et ajouter des cas exhaustifs pour d’autres petites capacités.

Couvrir les valeurs identiques et les pièges des entrées en flux

Pour tester les valeurs identiques, utilisez des enregistrements portant un identifiant de position unique. Par exemple, attribuez les positions zéro et un à deux événements de même contenu, puis vérifiez qu’aucune position n’est sélectionnée deux fois. Il ne faut pas simplement exiger que les valeurs métier de l’échantillon soient uniques. Dédupliquer avant l’échantillonnage modifierait le poids de chaque catégorie d’événements et nécessiterait du stockage supplémentaire.

Pour une capacité de un, forcez séparément le remplacement et l’absence de remplacement. Lorsque la capacité est égale à la longueur de l’entrée, la source aléatoire ne doit pas être appelée. Lorsqu’elle dépasse cette longueur, la taille de la sortie doit être égale à celle de l’entrée.

Pour une séquence qui ne peut être consommée qu’une seule fois, ajoutez un itérateur qui compte les lectures. Avec une capacité nulle, le nombre de lectures doit être nul ; avec une capacité positive, un seul parcours doit avoir lieu. N’appelez pas Array(input) pour connaître la longueur à l’avance : même si la sélection reste correcte, l’objectif de maîtrise de la mémoire en traitement de flux serait déjà compromis.

Le compteur impose également que le nombre d’éléments d’entrée soit représentable par un Int. Pour un flux d’événements sans fin, terminez l’échantillonnage à la fermeture d’une fenêtre ; il ne faut pas attendre que cette fonction synchrone retourne d’elle-même. L’annulation et la fermeture de la fenêtre doivent être pilotées par la couche supérieure.

Conserver des preuves reproductibles lors de l’intégration

En production, vous pouvez fournir les entiers avec Int.random(in: 0..<upper). N’utilisez pas le modulo d’un entier aléatoire pour obtenir l’intervalle voulu, et n’intégrez pas la séquence de tirages fixe des tests dans la fonctionnalité livrée. Cet échantillonnage est destiné au traitement de données courant ; il ne doit pas servir directement à des tirages présentant des exigences de sécurité.

Versionnez le script dans le dépôt et exécutez-le dans les étapes de build sur le Mac cloud, avant les tests du projet. Pour chaque échec, conservez au minimum les positions d’entrée, la capacité, la séquence des tirages et la version de la chaîne d’outils. Ne journalisez pas le contenu réel des événements des utilisateurs à des fins de diagnostic.

Enfin, organisez la validation en trois niveaux : des cas limites déterministes, l’énumération exhaustive des parcours sur de petits exemples et des observations statistiques indépendantes. Ces dernières peuvent révéler un mauvais raccordement de la source aléatoire, mais des seuils de fréquence trop étroits ne doivent pas bloquer chaque commit. Une régression doit être établie à partir d’un parcours d’échec explicite et rejouable, et non d’un échantillon qui contredit ponctuellement l’intuition.

Questions fréquentes