В зависимости от того, что гарантирует время выполнения, вам нужен известный алгоритм O (n) для выбора k случайных элементов из потока чисел за один проход. Чтобы понять алгоритм, давайте сначала рассмотрим его для случая, когда мы хотим выбрать только один элемент из набора, а затем обобщим его, чтобы он работал для выбора k элементов. Преимущество этого подхода в том, что он не требует предварительных знаний о размере входного набора и гарантирует доказуемо равномерную выборку элементов, что всегда очень приятно.
Предположим, что мы хотим выбрать один элемент из набора. Чтобы сделать это, мы обойдем все элементы набора и в каждой точке будем поддерживать элемент-кандидат, который мы планируем вернуть. Перебирая список элементов, мы с некоторой вероятностью будем обновлять наше предположение, пока в самом конце не выберем один элемент с одинаковой вероятностью. В каждой точке мы будем поддерживать следующий инвариант:
После просмотра k элементов вероятность того, что любой из первых k элементов в настоящее время выбран в качестве элемента-кандидата, равна 1 / k.
Если мы сохраним этот инвариант по всему массиву, то после просмотра всех n элементов у каждого из них будет 1 / n шанс стать кандидатом. Таким образом, элемент-кандидат был выбран с равномерно случайной вероятностью.
Чтобы увидеть, как работает алгоритм, давайте подумаем о том, что он должен делать, чтобы поддерживать инвариант. Предположим, что мы только что увидели самый первый элемент. Чтобы сохранить вышеупомянутый инвариант, мы должны выбрать его с вероятностью 1, поэтому мы установим наше первоначальное предположение элемента-кандидата в качестве первого элемента.
Теперь, когда мы подходим ко второму элементу, нам нужно держать инвариант, что каждый элемент выбран с вероятностью 1/2, так как мы видели два элемента. Итак, давайте предположим, что с вероятностью 1/2 мы выберем второй элемент. Тогда мы знаем следующее:
- Вероятность того, что мы выбрали второй элемент, равна 1 / 2.
- Вероятность того, что мы выбрали первый элемент, - это вероятность, что мы выбрали его в первый раз, примерно в 1 раз больше вероятности того, что мы не просто выбрали второй элемент (1/2). Это также выходит на 1/2.
Так что на данный момент инвариант все еще поддерживается! Посмотрим, что произойдет, когда мы подойдем к третьему элементу. На этом этапе нам нужно убедиться, что каждый элемент выбран с вероятностью 1/3. Хорошо, предположим, что с вероятностью 1/3 мы выберем последний элемент. Тогда мы знаем, что
- Вероятность того, что мы выбрали третий элемент, равна 1/3.
- Вероятность того, что мы выбрали один из первых двух элементов, - это вероятность того, что он был выбран после первых двух шагов (1/2), умноженных на вероятность того, что мы не выбрали третий элемент (2/3) , Это работает до 1 / 3.
Итак, инвариант верен!
Общий шаблон здесь выглядит следующим образом: после того, как мы увидели k элементов, каждый из элементов имеет шанс 1 / k быть выбранным. Когда мы видим (k + 1) -ый элемент, мы выбираем его с вероятностью 1 / (k + 1). Это означает, что он выбран с вероятностью 1 / (k + 1), и все элементы перед ним выбраны с вероятностью, равной вероятностям, которые мы выбрали ранее (1 / k), и не выбрали (k + 1) ) первый элемент (k / (k + 1)), что дает каждому элементу вероятность выбора 1 / (k + 1). Так как это поддерживает инвариант на каждом шаге, мы получили отличный алгоритм:
- Выберите первый элемент в качестве кандидата, когда увидите его.
- Для каждого последующего элемента замените элемент-кандидат этим элементом с вероятностью 1 / k, где k - это количество элементов, видимых до сих пор.
Это выполняется за время O (n), требует пространства O (1) и возвращает равномерно-случайный элемент из потока данных.
Теперь давайте посмотрим, как это масштабировать, чтобы мы работали, если мы хотим выбрать k элементов из набора, а не только один. Идея чрезвычайно похожа на предыдущий алгоритм (который фактически оказывается частным случаем более общего). Вместо того, чтобы поддерживать одного кандидата, мы сохраняем k разных кандидатов, хранящихся в массиве с номером 1, 2, ..., k. В каждой точке мы поддерживаем этот инвариант:
После просмотра m> k элементов вероятность выбора любого из первых m элементов равна
к / м.
Если мы сканируем весь массив, это означает, что когда мы закончим, каждый элемент имеет вероятность k / n выбора. Поскольку мы выбираем k различных элементов, это означает, что мы выборочно выбираем элементы из массива случайным образом.
Алгоритм аналогичен ранее. Сначала выберите первые k элементов из набора с вероятностью 1. Это означает, что когда мы увидели k элементов, вероятность того, что какой-либо из них был выбран, равна 1 = k / k, и инвариант имеет место. Теперь предположим индуктивно, что инвариант выполняется после m итераций, и рассмотрим (m + 1) -ю итерацию. Выберите случайное число от 1 до (m + 1) включительно. Если мы выберем число от 1 до k (включительно), заменим этот элемент-кандидат следующим элементом. В противном случае не выбирайте следующий элемент. Это означает, что мы выбираем следующий элемент с вероятностью k / (m + 1), как требуется. Вероятность того, что выбран любой из первых m элементов, равна вероятности того, что они были выбраны до (k / m), умноженной на вероятность того, что мы не выбрали слот, содержащий этот элемент (m / (m + 1)), что дает полную вероятность быть выбранным k / (m + 1), как требуется. По индукции это доказывает, что алгоритм идеально равномерно и случайно выбирает k элементов из множества!
Кроме того, время выполнения равно O (n), которое пропорционально размеру набора, которое полностью не зависит от количества элементов, которые вы хотите выбрать. Он также использует только O (k) память и не делает никаких предположений о типе хранимых элементов.
Поскольку вы пытаетесь сделать это для C ++, в качестве бесстыдной саморекламы, у меня есть реализация этого алгоритма (написанного как алгоритм STL) , доступная здесь on мой личный сайт. Не стесняйтесь использовать его!
Надеюсь, это поможет!