Если я хочу сгенерировать 1000 чисел от 0 до 999, которые являются уникальными, что мне делать?
Моя первая попытка - создать массив {0, 1, 2, ..., 999} и использовать std::random_shuffle, чтобы перетасовать их. Однако, поскольку я должен генерировать числа в длинном цикле, скажем, O (10^7), этот подход будет подавлять время работы.
Есть ли лучший способ решить эту проблему?Произвольно генерировать n уникальных чисел
Если вы сохраните массив 1000 номеров, сохраненных и вызвать std::random_shuffle каждый раз, когда вам нужно в цикле, что на самом деле самый быстрый способ, которым вы сможете генерировать 1000 случайных уникальных номеров так, как вам нужно. Вам не нужно повторно создавать массив каждый раз.
Не имеет значения, имеет ли ваша петля O (10^7) итерации, потому что если вы собираетесь использовать эти 1000 целых чисел, как вы говорите, вам нужно, пройдите через каждое из этих чисел, как вы их используете. std::random_shuffle сложность времени также O (n), поэтому она не собирается замедлять вас гораздо больше.
Вы запрашиваете реализацию shuffle (это точное описание вашего требования), которое будет лучше, чем в стандартной библиотеке. Это длинный выстрел.
Но я попробую. Я бы сказал: подготовьте файл с 10^7 такими перестановками и прочитайте его. Обязательно предварительно сделайте предварительную выборку, иначе она будет медленнее. Если вы предварительно отбираете в другой поток, это может быть быстрее. Но это всего лишь дикая догадка.
Когда я думаю об этом, если вы можете запускать многопоточность, вы можете использовать простое решение производителя-потребителя. Одна нить переносит перестановки, другая просто читает их.
Сохраните номер контейнера в другой контейнер C2.
Создать индекс элемента для выбора случайного элемента в C1. Каждый раз, когда вы создаете индекс, удалите его из контейнера C1. Итак, в следующий раз вы получите уникальный номер.
После C1 становится пустым, заселить C1 с C2 и перейти к шагу 2.
Почему это должно быть 10^7 для генерации 100 номеров – aaronman
@aaronman Это не то, что сказал ОП. Ему нужно сгенерировать их в цикле, который будет работать около 10^7 раз. – Elazar
с различным набором случайных чисел каждый раз? В чем цель этого, я не думаю, что мы сможем решить проблему без дополнительной информации, и вы не будете генерировать другой набор случайных чисел каждый раз, не пройдя все 1000 чисел. – aaronman