Зная, что когда что-то кажется слишком хорошим, чтобы быть правдой, я решил, что задам этот вопрос, чтобы избавиться от гремлинов. Я просмотрел несколько связанных тем, которые смог найти, но мой вопрос все еще остается.
Я относительно новичок в Haskell, и в своих экспериментах я закодировал базовую перетасовку Фишера-Йейтса, как показано ниже.
shuffle :: RandomGen g => [a] -> g -> ([a],g)
shuffle [] g0 = ([],g0)
shuffle [x] g0 = ([x],g0)
shuffle xs g0 = (x:newtail,g2)
where (i,g1) = randomR (0, length $ tail xs) g0
(xs1,x:xs2) = splitAt i xs
(newtail,g2) = shuffle (xs1++xs2) g1
Эта реализация, конечно, использует память beaucoup для больших списков, но она быстрая - на моем ноутбуке в среднем 5 с для 30 миллионов целых чисел по сравнению со стандартным перетасовкой С++ со скоростью 2,3 с). Фактически, это намного быстрее, чем другие реализации Haskell, найденные в других местах (например, http://www.haskell.org/haskellwiki/Random_shuffle)
Учитывая, что другие перетасовки Haskell, которые я видел, и сложнее, и медленнее, мне интересно, является ли ускорение/простота просто моей наградой за то, что я безжалостно пожираю память, или я упустил какую-то крошечную, но важную деталь, которая делает мой алгоритм предвзятым. Я не проверял всесторонне, но предварительный взгляд, кажется, показывает равномерное распределение перестановок.
Я был бы признателен за оценку большего количества глаз с большим опытом работы с Haskell и / или перетасовкой. Заранее большое спасибо всем, кто найдет время ответить.
Int
s с этим кодом занимает несколько дней. - person Daniel Fischer   schedule 26.04.2013