Эффективный алгоритм генерации уникальных (неповторяющихся) случайных чисел - PullRequest
Новая
       23

Эффективный алгоритм генерации уникальных (неповторяющихся) случайных чисел

0 голосов
/ 03 июня 2018

Я хочу решить следующую проблему.Я должен сделать выборку среди чрезвычайно большого набора, порядка 10 ^ 20 и извлечь образец без повторений размером около 10% -20%.Учитывая размер множества, я считаю, что такой алгоритм, как Фишер-Йейтс, невозможен.

Я думаю, что что-то вроде дерева случайных путей может работать для этого в O (n log n) и не может быть сделано быстрее, но я хочу спросить, было ли что-то подобное уже реализовано.

Спасибо, что уделили время!

1 Ответ

0 голосов
/ 03 июня 2018

Я не знаю, насколько хорошо техника, которую я опишу ниже, подойдет для формальных тестов случайности, но она дает "случайные" результаты.

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

А пока я писал запись в блоге о том, как генерировать запутанные последовательные ключи.Вот код: 

private void DoIt()
{
    const long m = 101;         // Number of keys + 1
    const long x = 387420489;   // must be coprime to m

    // Compute the multiplicative inverse
    var multInv = MultiplicativeInverse(x, m);

    // HashSet is used to hold the obfuscated value so we can ensure that no duplicates occur.
    var nums = new HashSet<long>();

    // Obfuscate each number from 1 to 100.
    // Show that the process can be reversed.
    // Show that no duplicates are generated.
    for (long i = 1; i <= 100; ++i)
    {
        var obfuscated = i * x % m;
        var original = obfuscated * multInv % m;
        Console.WriteLine("{0} => {1} => {2}", i, obfuscated, original);
        if (!nums.Add(obfuscated))
        {
            Console.WriteLine("Duplicate");
        }
    }    
}

private long MultiplicativeInverse(long x, long modulus)
{
    return ExtendedEuclideanDivision(x, modulus).Item1 % modulus;
}

private static Tuple<long, long> ExtendedEuclideanDivision(long a, long b)
{
    if (a < 0)
    {
        var result = ExtendedEuclideanDivision(-a, b);
        return Tuple.Create(-result.Item1, result.Item2);
    }
    if (b < 0)
    {
        var result = ExtendedEuclideanDivision(a, -b);
        return Tuple.Create(result.Item1, -result.Item2);
    }
    if (b == 0)
    {
        return Tuple.Create(1L, 0L);
    }
    var q = a / b;
    var r = a % b;
    var rslt = ExtendedEuclideanDivision(b, r);
    var s = rslt.Item1;
    var t = rslt.Item2;
    return Tuple.Create(t, s - q * t);
}

Первые несколько строк вывода для этой программы: 

1 => 43 => 1
2 => 86 => 2
3 => 28 => 3
4 => 71 => 4
5 => 13 => 5
6 => 56 => 6
7 => 99 => 7
8 => 41 => 8
9 => 84 => 9
10 => 26 => 10

Если бы вы изменили значения m и x в началефункции, чтобы отразить ваш диапазон чисел, это будет работать для вас.И вместо того, чтобы всегда начинать с 1 и брать первые 10 или 20%, вы можете начать с 50% -ой отметки и идти оттуда.Или используйте технику, которая захватывает каждое пятое число, или что-то еще, если ваш метод не посещает одно и то же число дважды.

И если вам нужно больше прогонов, просто измените значение x.

Генерация обратного мультипликатива (воспринимайте его как заполнение генератора случайных чисел) - операция O (log n).После этого генерируется каждое число O (1).

Конечно, если вы работаете с числами в диапазоне 10 ^ 20, вам придется изменить код для работы с большим целым числомкласс.

...