Каковы недостатки генерации уникальных чисел с помощью последовательного заполнения и перемешивания

Что проверяют

Умеете ли вы оценивать алгоритм по памяти и времени относительно двух чисел: размера диапазона N и количества нужных значений k. Следом обычно просят альтернативу для случая, когда k много меньше N, и спрашивают, какой генератор случайных чисел вы возьмёте.

Как отвечать

Сначала опишите подход: заполняем срез числами диапазона, перемешиваем тасованием Фишера-Йетса (rand.Shuffle или сразу rand.Perm(n)) и берём первые k. Он корректен: дубликатов нет по построению, распределение равномерное. Недостатки такие:

• память O(N), а не O(k): чтобы выбрать 10 чисел из диапазона до миллиарда, придётся выделить срез на миллиард int, это около 8 ГБ;
• время O(N): заполнение и полное перемешивание стоят линейно от диапазона, даже если нужно всего несколько значений. Частичное перемешивание первых k позиций экономит обмены, но не память;
• только конечный диапазон: для бесконечного потока подход не работает;
• качество случайности: math/rand и math/rand/v2 предсказуемы и не годятся для токенов, для этого есть crypto/rand. Засевать глобальный генератор вручную не нужно: с Go 1.20 он засевается сам, а rand.Seed объявлен устаревшим.

Альтернативы по соотношению k и N:

• k много меньше N: генерировать случайные числа и отбрасывать повторы через map[int]struct{}, ожидаемое время близко к O(k);
• ровно k итераций: алгоритм Флойда или «разреженный» Фишер-Йетс на map вместо среза, память O(k);
• k сравнимо с N: заполнение с перемешиванием как раз оптимально.

Где спотыкаются

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

Пишут перемешивание сами и выбирают индекс обмена из всего среза, а не из [0, i]. Перестановки получаются неравновероятными.

Для идентификаторов сессий берут глобальный math/rand, а диапазон получают остатком rand.Int() % n. Первое предсказуемо, второе смещает распределение. Для диапазона есть rand.IntN из math/rand/v2, для секретов crypto/rand.