Проверка резервуарной выборки iOS на облачном Mac

После реализации фильтрации журналов в Windows понадобилось случайным образом сохранять небольшое число записей из потока событий, размер которого заранее неизвестен. Если загрузить все записи в массив и перемешать его, потребление памяти будет расти вместе с объёмом входных данных. На облачном Mac можно сначала проверить резервуарную выборку на Swift, а затем подключить ту же реализацию к проекту iOS. Главное — не оценивать, «похож ли результат на случайный», а превратить правила отбора в контракт, допускающий воспроизводимую проверку.

Определяем единицу отбора и контракт ёмкости

В статье используется Algorithm R: сначала сохраняем первые k элементов; при чтении элемента с номером t равномерно выбираем целое число j от нуля до t−1 и заменяем элемент в соответствующей ячейке, только если j меньше k. После завершения обхода вероятность попадания каждой входной позиции в выборку равна k/n, дополнительная память составляет O(k), а время обхода — O(n).

Этот вывод требует, чтобы каждый розыгрыш оставался равномерным при условии всей предшествующей истории. Самого по себе попадания случайного числа в допустимый диапазон недостаточно для справедливого отбора.

Сразу зафиксируем четыре граничных условия: ёмкость не может быть отрицательной; при нулевой ёмкости возвращается пустая выборка без чтения входных данных; если элементов меньше, чем вмещает резервуар, сохраняются все; одинаковые значения в разных позициях участвуют в отборе отдельно. Порядок ячеек на выходе не является случайной перестановкой, сохранение исходного порядка тоже не гарантируется.

Справедливый отбор не означает, что результат каждый раз должен быть новым. Проверка «два результата подряд не должны совпадать» превращает нормальный случайный исход в периодически возникающий сбой теста.

Отделяем источник случайности от логики отбора

Войдите на облачный Mac OSXMesh и выполните в терминале xcrun swift --version, чтобы убедиться, что текущий набор инструментов позволяет запускать Swift. Сохраните приведённый ниже код в файл ReservoirCheck.swift. Замыкание получает верхнюю границу, не включаемую в диапазон: благодаря этому рабочий источник случайности и тестовый сценарий используют одну и ту же логику отбора.

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

Запустите xcrun swift ReservoirCheck.swift. При успехе скрипт ничего не выводит, при неудаче завершается с ненулевым кодом. Проверки в нём основаны на предусловиях, поэтому запускать его с параметрами оптимизации, отключающими проверки безопасности, нельзя. Если реальное приложение получает ёмкость извне, значение нужно проверить до вызова алгоритма, а не допускать завершение процесса из-за некорректного ввода.

Проверяем правила отбора перебором двенадцати путей

При выборе двух позиций из четырёх для третьего элемента возможны три варианта, а для четвёртого — четыре. Всего получается двенадцать путей. При описанных выше предположениях об источнике случайности вероятность каждого пути равна одной двенадцатой, а каждое из шести неупорядоченных сочетаний позиций должно встретиться дважды.

Здесь проверяется распределение сочетаний, а не только число появлений отдельных позиций. Некоторые ошибочные реализации дают почти одинаковые маргинальные частоты для всех элементов, но при этом никогда не выдают часть сочетаний.

Скрипт также проверяет, что источник случайности получил верхние границы три и четыре, а подготовленная последовательность розыгрышей израсходована точно до конца. Тест завершится неудачей, если вызовов окажется на один меньше или больше либо если вместо нужной верхней границы передать текущее число ячеек. Сортировка нужна только для построения ключа сравнения: она не должна незаметно менять контракт возвращаемого значения рабочей функции.

Такой небольшой пример позволяет обнаружить распространённые ошибки в условии замены, но не служит математическим доказательством для входных данных любого размера. Перед слиянием изменений нужно проверить условия индуктивного доказательства и добавить полный перебор для других небольших значений ёмкости.

Учитываем повторяющиеся значения и особенности потокового ввода

Для проверки повторяющихся значений используйте записи с уникальными порядковыми номерами. Например, двум событиям с одинаковым содержимым назначьте позиции ноль и один и проверяйте, что выбранные позиции не повторяются. Нельзя просто требовать уникальности самих значений данных в выборке. Удаление дубликатов перед отбором меняет вес каждого типа событий и требует дополнительной памяти.

При ёмкости один нужны отдельные случаи с принудительной заменой и с принудительным пропуском. Если ёмкость равна длине входа, источник случайности вызываться не должен. Если ёмкость больше длины входа, длина результата должна совпадать с длиной входа.

Для последовательности, которую можно прочитать только один раз, добавьте итератор со счётчиком чтений. При нулевой ёмкости число чтений должно быть нулевым, при положительной допускается только один проход. Не вызывайте Array(input), чтобы заранее узнать длину: даже при правильном результате отбора цель по ограничению памяти при потоковой обработке уже будет нарушена.

Счётчик также требует, чтобы число входных элементов представлялось типом Int. Бесконечный поток событий нужно разбивать на окна и завершать отбор при закрытии окна: нельзя рассчитывать, что эта синхронная функция вернёт управление сама. Отменой и закрытием окна должен управлять вышестоящий уровень.

Сохраняем воспроизводимые свидетельства при интеграции в проект

В рабочем коде целые числа можно получать через Int.random(in: 0..<upper). Не подгоняйте случайное число под диапазон взятием остатка и не переносите фиксированную тестовую последовательность в рабочую функцию. Описанная выборка предназначена для обычной обработки данных; без дополнительной проработки её нельзя использовать для розыгрышей, требующих гарантий безопасности.

Добавьте скрипт в репозиторий и запускайте его на этапе сборки на облачном Mac перед тестами проекта. При сбое сохраняйте как минимум входные позиции, ёмкость, последовательность розыгрышей и версию набора инструментов. Не записывайте содержимое реальных пользовательских событий ради диагностики.

В итоге разделите проверку на три уровня: детерминированные граничные случаи, полный перебор путей для малых примеров и независимые статистические наблюдения. Статистические наблюдения помогают выявлять ошибки подключения источника случайности, но слишком узкие допуски по частотам не должны блокировать каждый коммит. Основанием для регрессионной проверки должен быть явно заданный, воспроизводимый путь к сбою, а не отдельный результат выборки, случайно не совпавший с интуицией.

Часто задаваемые вопросы