Как работает Python random shuffle?

11

Как случайная случайность работает в Python?

Я спрашиваю, потому что это работает очень быстро. Когда я пытаюсь написать shuffle, он работает 1 минуту для элемента 10 ^ 6, но Python shuffle делает это за 8 секунд?

Павел Шиманский
источник
14
Почему бы просто не посмотреть на исходный код ?
ленивец
4
лучший алгоритм случайного воспроизведения - это случайный случай Фишера-Йейтса , он выполняется за время O (n) и, как доказано, является идеальным случайным образом (при условии хорошего случайного источника)
трещотка урод
1
@ratchetfreak: Python использует Fisher-Yates.
Мартейн Питерс
1
Какой твой алгоритм для случайного выбора?
whatsisname
@sloth, кстати, Рэймонд Хеттингер предложил универсальную практику ссылок на ссылки на исходный код еще в 2011 году.
Кристиан Чиупиту,

Ответы:

17

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 1 do
       j  random integer with 0  j  i
       exchange a[j] and a[i]
комара
источник