Генерация случайной выборки значений BigInt - PullRequest
Новая
       71

Генерация случайной выборки значений BigInt

1 голос
/ 04 мая 2020

Для игры, реализованной в JavaScript, мне нужно создать случайный список из n уникальных чисел в диапазоне [0, N), где N может быть больше Number.MAX_SAFE_INTEGER. Это создает три важных проблемы:

  • Стоимость памяти не может быть O (N), так как у нас не будет достаточно оперативной памяти. Это означает, что мы не можем использовать модифицированный алгоритм перемешивания Фишера-Йейтса для получения n перемешанных значений из массива N элементов. (JS массивы ограничены 32-битными индексами, но у нас закончится ОЗУ задолго до этого.)
  • Время выполнения должно быть как можно ближе к O (n), а не к O (N ). Я ожидаю, что n будет относительно небольшим (<100). </li>
  • Большинство математических операций используют значения с плавающей запятой двойной точности и не будут работать с такими большими числами.

Я нашел решение к первым двум задачам в алгоритме отбора проб коллектора Ким-Хун Ли L. Подводя итог, можно сказать, что идея этого алгоритма состоит в том, что мы перемешиваем первые n чисел, чтобы сформировать начальный резервуар, а затем постепенно перезаписываем некоторые из них случайными числами, взятыми от остального ассортимента. Мы используем прогрессию geometri c, чтобы определить, сколько чисел пропускать на каждой итерации.

Предположим, что sampleSize - это число, а PopulationSize - это BigInt в следующем коде: 

// Creates an array initialized with [0n, 1n, ... BigInt(count-1)].
function bigRange (count) {
    const array = Array(count);
    for (let i = 0; i < count; i += 1) {
        array[i] = BigInt(i);
    }
    return array;
}

function bigSample (sampleSize, populationSize) {
    const reservoir = shuffle(bigRange(sampleSize));
    let record = BigInt(sampleSize);
    let weight = exp(log(random()) / sampleSize);

    while (true) {
        const skipCount = floor(log(random()) / log(1 - weight));
        record += BigInt(skipCount);

        if (record >= populationSize) {
            return reservoir;
        }

        reservoir[floor(random() * sampleSize)] = record;
        record += BigInt(1);
        weight *= exp(log(random()) / sampleSize);
    }
}

Однако этот код не будет работать с произвольно большими числами, поскольку точность чисел с плавающей запятой ограничена. По мере роста PopulationSize в конечном итоге используются незначащие биты чисел с плавающей запятой, и у нас больше нет равномерного распределения, тогда мы попадаем на небезопасную целочисленную территорию, и, наконец, возможно, что skipCount станет Infinity. Зная это, я остаюсь в недоумении ...

  • В какой момент эта функция становится ненадежной?
  • Есть ли способ для меня для улучшения этого алгоритма для компенсации ограничений JavaScript?
  • Есть ли лучшие альтернативы?

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

Ответы [ 2 ]

2 голосов
/ 04 мая 2020

Если n относительно мало, альтернативой является сохранение чисел, уже сгенерированных в JavaScript Map или обычном объекте JavaScript, где ключи являются числами (но обратите внимание, что и Карты, и обычные объекты будут преобразовывать эти ключи к строкам, так что в этом случае ключ должен быть таким же, как значение). Если n значительно меньше, чем N, время для сохранения каждого нового случайного числа приближается к постоянной временной сложности, а вероятность того, что все n из N случайных чисел будут отличаться с первой попытки, приближается к 1.

  • Я написал раздел, показывающий различные способы выборки n из N элементов в зависимости от размера n и N.
  • Но если вы пытаетесь сгенерировать n уникальных случайных чисел из огромного пространства N возможных значений (например, 100-битных чисел), и эти числа должны каким-то образом идентифицировать что-то, тогда следует помнить о нескольких вещах, которые я подробно описываю в статье « Уникальные случайные идентификаторы ».
1 голос
/ 04 мая 2020

Вы можете генерировать свои значения побитно и добавлять их в tr ie. Когда вы генерируете не первое число, вы можете использовать счетчик свободного места в ветвях вашего tr ie для определения вероятностей go в каждой ветке. Это даст уникальные числа из равномерного распределения, если операции с плавающей запятой были бы идеальными, но я предполагаю, что эти несоответствия в вероятностях на высоком уровне в tr ie не будут иметь существенного значения (поэтому это требует дальнейшего исследования) . Обратите внимание: если вы сгенерировали число больше N, вы просто начинаете процесс генерации заново. если вы не будете делать ненужные биты, вероятность регенерации будет меньше 50%, а ожидаемое значение дополнительных поколений будет равно единице.

...