У меня есть фрагмент кода, где я должен искать в группе векторов первый элемент, который удовлетворяет данному предикату.Я должен сделать это несколько раз, и поскольку есть несколько элементов, которые удовлетворяют моему предикату, я хотел бы несколько рандомизировать порядок, в котором я проверяю, чтобы дать всем равные возможности быть обнаруженными.
В то же время я хотел бы, чтобы это было как можно более быстрым, поэтому я действительно не хочу тасовать / распределять или что-то в этом роде.
Эти требования заставили меня попасть в случайную спиральгенерация чисел, линейные конгруэнтные генераторы, LFSR, Xorshifts, криптография, но мне трудно найти хорошее решение.
Я понимаю, что выбор случайной перестановки действительно случайным образом невозможен.Я ищу генератор, который я могу передать
N- начальное число
- некоторое количество случайных битов (в виде числапараметры, сгенерированные из отдельного PRNG)
, и он будет циклически проходить одну из перестановок из N элементов (выбранных псевдослучайно).
Этот ответ даетчто я думаю, может быть хорошей отправной точкой;генератор для 16 битов в виде
P(x) = ((x ^ 0xf) ^ (x << 2) + 3) & 0xf
, который можно перебрать, отбрасывая любое число> N. Мне нравится это, поскольку мне не требуется находить простое число, только следующая наибольшая степень2, который быстр с игрой на битах.Я играл с этим, и у меня есть генератор вида
P(x) = ((x ^ (next_pow2 - 1)) ^ (x << z) + y) & (next_pow2 - 1)
Выбор z и y случайным образом дает мне различные перестановки.Однако я не совсем понимаю, как это работает, можно ли его улучшить, и в каком диапазоне значения y и z должны быть максимально возможными (поскольку изменение параметров приведет к дублированию некоторых перестановок).
Может кто-нибудь указать мне, есть ли лучшее решение, и что именно читать, чтобы узнать больше?Это поле выглядит очень сложным для новичка, и я не знаю, с чего начать.