Я спрашиваю, потому что это работает очень быстро. Когда я пытаюсь написать shuffle, он работает 1 минуту для элемента 10 ^ 6, но Python shuffle делает это за 8 секунд?
лучший алгоритм случайного воспроизведения - это случайный случай Фишера-Йейтса , он выполняется за время O (n) и, как доказано, является идеальным случайным образом (при условии хорошего случайного источника)
Python random.shuffleиспользует случайный случай Фишера-Йейтса , который выполняется за время O (n) и доказал, что он является идеальным случайным образом (при условии хорошего генератора случайных чисел).
Он перебирает массив от последней к первой записи, переключая каждую запись с записью со случайным индексом под ним.
Основной процесс перетасовки Фишера-Йейтса подобен случайному выбору пронумерованных билетов из шляпы или карт из колоды, одна за другой, пока не останется больше. То, что обеспечивает конкретный алгоритм, - это способ сделать это численно эффективным и точным образом, который, при правильном выполнении, гарантирует непредвзятый результат ...
Современное ... решение состоит в том, чтобы переместить «вычеркнутые» числа в конец списка, поменяв их местами с последним неповрежденным числом на каждой итерации. Это уменьшает временную сложность алгоритма до O (n) по сравнению с O (n 2 ) для простой реализации. Это изменение дает следующий алгоритм (для массива с нулями).
To shuffle an array a of n elements (indices 0..n-1):for i from n −1 downto 1do
j ← random integer with0≤ j ≤ i
exchange a[j]and a[i]
Ответы:
Python
random.shuffle
использует случайный случай Фишера-Йейтса , который выполняется за время O (n) и доказал, что он является идеальным случайным образом (при условии хорошего генератора случайных чисел).Он перебирает массив от последней к первой записи, переключая каждую запись с записью со случайным индексом под ним.
источник