Какой из этих алгоритмов лучше по производительности и порядку генерации N уникальных случайных чисел в диапазоне 1..n?

Question

1

Взять массив из n элементов: {1, 2, 3, .... n}. Перемешать массив, используя любой из стандартных алгоритмов случайного перемешивания массивов. Первые N элементов модифицированного массива - это то, что вы ищете.

2

Просто используйте Random.Next() в цикле и проверьте, существует ли он уже или нет в Dictionary, пока у нас не будет N чисел.

Обратите внимание, что N << n (N очень меньше, чем n) </p>

Answer 1

Это полностью зависит от двух значений (n и N).

Для большого n и малого N (например, выберите два разных случайных значения от нуля до миллиона), вариант два будет лучше. Ожидаемое время здесь, вероятно, сложно вычислить, и оно выходит далеко за рамки моих возможностей в воскресенье вечером ... но в основном вам нужно повторять N раз во внешнем цикле; затем вам нужно проверить, возвратили ли вы уже это значение (которое, вероятно, равно O (m), как только вы уже выбрали m значений); тогда вам, возможно, придется повторить попытку, если вы нашли это значение - оно не будет иметь верхней границы по времени, но будет иметь вероятностное время, которое сложно вычислить.

Когда n и N близки друг к другу (например, выберите 99 случайных значений от одного до ста включительно), тогда настройте первый вариант (фактически выбирая столько значений, сколько вам нужно, а не перемешивая весь массив) будь лучше. Используя случай Фишера-Йейтса , вы получите O (n).

На практике:

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

Answer 2

Ни один из них не лучший.Вам нужен тасовка Фишера-Йейтса.Проблема со случайным решением состоит в том, что вы делаете много ненужной работы заранее.Проблема со вторым решением состоит в том, что вероятность дубликатов возрастает со временем, поэтому вы отбрасываете много значений.

Для очень эффективного решения, которое дает вам подмножество ваших значений с ноль возможность дубликатов (и без предварительной сортировки), Fisher-Yates - это путь.

dim n[N]                  // gives n[0] through n[N-1]
for each i in 0..N-1:
    n[i] = i              // initialise them to their indexes
nsize = N                 // starting pool size
do N times:
    i = rnd(nsize)        // give a number between 0 and nsize-1
    print n[i]
    nsize = nsize - 1     // these two lines effectively remove the used number
    n[i] = n[nsize]

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

Это важно, если число велико, поскольку оно не 't ввести ненужную задержку запуска.

Например, проверьте следующую проверку, выбрав 10-из-10:

<------ n[] ------>
0 1 2 3 4 5 6 7 8 9  nsize  rnd(nsize)  output
-------------------  -----  ----------  ------
0 1 2 3 4 5 6 7 8 9     10           4       4
0 1 2 3 9 5 6 7 8        9           7       7
0 1 2 3 9 5 6 8          8           2       2
0 1 8 3 9 5 6            7           6       6
0 1 8 3 9 5              6           0       0
5 1 8 3 9                5           2       8
5 1 9 3                  4           1       1
5 3 9                    3           0       5
9 3                      2           1       3
9                        1           0       9

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

Answer 3

Частично Фишер-Йейтс, с некоторыми хитростями *:

Алгоритм генерации 1000 различных целых чисел в диапазоне [0,8000]?

&

Алгоритм выбора одной случайной комбинации значений?

_{* Основной вывод здесь заключается в том, что использование памяти сокращено, поэтому теперь оно пропорционально количеству элементов выбрано не более, а не количеству элементов выбирается, Это может обеспечить значительную экономию, если N << n (как вы упомянули). (Использование пространства ограничено O (n / 2), независимо от того, насколько близко N к n.)}

_{Время работы O (N).}

_{Кроме этого, это довольно обычный частичный Фишер-Йейтс, он же Кнут Каста.}

Answer 4

В крайнем случае 2 может никогда не закончиться, поскольку каждое генерируемое число уже может быть в списке. Однако, как правило, вы будете выполнять итерации по гораздо большему, чем число N.

1 гарантированно завершится за конечное время.