Эффективный способ выбора случайных элементов из потока данных

ReadMe.md

Immediately Reservoir Shuffling Algorithm

Описание

Алгоритм Immediately Reservoir Shuffling предоставляет эффективный способ выбора случайных элементов из потока данных, когда заранее неизвестно, сколько элементов будет в потоке. Алгоритм использует технику резервуарного перетасовывания для получения выборки из k элементов с использованием вероятности замены.

Ключевая особенность алгоритма — потоковая обработка данных. Это означает, что алгоритм может работать с неограниченными по объему данными, не требуя загрузки всей последовательности в память.

Преимущества:

1. Память: Использует фиксированное количество памяти, пропорциональное выборке k, независимо от объема потока.
2. Оптимизация: Предусматривает коэффициент ускорения для увеличения скорости работы алгоритма, что полезно при больших потоках и малых значениях k.
3. Ленивая генерация: Использует yield return, что позволяет возвращать элементы по мере их появления, экономя память и ускоряя выполнение.

Тирлист сравнения алгоритмов

Алгоритм	Простота	Память	Время работы	Производительность	Подходит для потоковых данных	Завершение потока для получения результата	Пояснение
Immediately Reservoir Shuffling	Средняя	O(k)	O(n)	Высокая	Да	Нет	Обрабатывает данные потоком и немедленно возвращает элементы, как только они появляются.
Reservoir Sampling	Простая	O(k)	O(n)	Средняя	Нет	Да	Требует завершения потока для получения итоговой выборки.
Fisher-Yates Shuffle	Простая	O(n)	O(n)	Средняя	Нет	Да	Перемешивает все элементы сразу, требует полной загрузки данных в память.
Knuth Shuffle	Средняя	O(n)	O(n)	Средняя	Нет	Да	Классическое перемешивание, работает с уже загруженными данными.
K-перетасовывание	Простая	O(n)	O(n)	Средняя	Нет	Да	Наивное перемешивание всех элементов в массиве, требует полной загрузки данных.

Оценка производительности

• Время: O(n) — Алгоритм проходит по всем элементам потока один раз, что гарантирует линейное время работы по числу элементов в потоке.
• Память: O(k) — Алгоритм использует только память, пропорциональную размеру выборки k. Это делает его эффективным при обработке больших потоков данных.

Примечание

Алгоритм может быть полезен в случаях, когда необходимо выбрать подмножество случайных элементов из потока, не зная его точного размера заранее, и когда важно сохранить низкие требования к памяти. Это делает алгоритм полезным для применения в реальных задачах, таких как потоковая обработка, анализ больших данных, системы рекомендаций и многое другое. Этот алгоритм вполне подходит для продакшн-среды, так как он эффективен по памяти и времени, а также предоставляет гибкость в настройке поведения перемешивания.

ImmediatelyReservoirShuffling.cs

using System;
using System.Collections.Generic;

public static class ImmediatelyReservoirShuffling
{
    /// <summary>
    /// Резервуарное перетасовывание с возможностью регулировки ускорения.
    /// Возвращает элементы лениво через yield.
    /// </summary>
    /// <param name="source">Исходная последовательность (поток данных).</param>
    /// <param name="k">Количество элементов для выборки.</param>
    /// <param name="acceleration">Коэффициент ускорения (0 - классическое поведение, 1 - максимальное ускорение).</param>
    /// <returns>Ленивая последовательность перемешанных элементов.</returns>
    public static IEnumerable<int> Shuffle(IEnumerable<int> source, int k, double acceleration = 0.5)
    {
        if (k <= 0)
            yield break;

        List<int> reservoir = new List<int>(new int[k]);
        int count = 0;
        Random rng = new Random();

        foreach (var item in source)
        {
            count++;

            // Если количество элементов меньше k, добавляем в резервуар
            if (count <= k)
            {
                reservoir[count - 1] = item;
                continue;
            }

            // Вычисляем вероятность замены
            double pReplace = k / (double)count;
            if (rng.NextDouble() < pReplace)
            {
                if (rng.NextDouble() < acceleration)
                {
                    // Ускоренное добавление элемента в результат (лениво возвращаем)
                    yield return item;
                }
                else
                {
                    // Стандартная замена в резервуаре
                    int replaceIdx = rng.Next(k);
                    reservoir[replaceIdx] = item;
                }
            }
        }

        // Дополнение оставшихся элементов (лениво)
        var used = new bool[k];
        int remaining = k - reservoir.Count;
        for (int i = 0; i < remaining; i++)
        {
            int pick;
            do
            {
                pick = rng.Next(k);
            }
            while (used[pick]);
            used[pick] = true;
            yield return reservoir[pick];
        }
    }
}