피셔 - 예이츠 셔플에 문제가 있습니까?

Question

무언가가 사실 일 때 너무 좋다고 생각하면 대개는 gremlins를 없애기 위해이 질문을 던집니다. 내가 찾을 수있는 몇 가지 관련 스레드를 검토했지만 여전히 내 질문에 남습니다.

저는 하스켈에 비교적 익숙하지 않습니다. 제 실험에서 아래에 표시된 것처럼 기본적인 피셔 - 예이츠 셔플을 코딩했습니다.

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 

물론이 구현

는 큰 목록에 대한 하셔 메모리를 사용하지만 빨리 - 내 노트북의 평균의 5 초에 표준 C 2.3s에서 ++ 셔플) 대 30M의 int를 위해. 사실, 그것은 다른 곳에서 발견 된 다른 Haskell 구현보다 훨씬 빠릅니다. (예 : http://www.haskell.org/haskellwiki/Random_shuffle)

다른 하스켈 셔플이 더 복잡하고 느린 것을 감안할 때, 나는 스피드 업/단순성이 단순히 내 것이지 궁금해합니다. 말로 표현할 수없는 기억의 돼지에 대한 보상, 또는 알고리즘이 편향된 작지만 결정적인 세부 사항을 놓친 경우. 나는 광범위하게 테스트하지는 않았지만, 예비적인 모습은 순열의 균일 한 분포를 보여주는 것으로 보인다.

더 많은 하스켈 및/또는 셔플 경험으로 더 많은 눈을 평가 해 주셔서 감사합니다. 회신 할 시간을 갖는 모든 사람들에게 미리 감사드립니다.

Answer 1

적절한 벤치마킹을 해보 죠. 셔플이 shuffle1으로 바뀌었고, 개인적으로 좋아하는 변종이 shuffle2으로 바뀌 었습니다.

carl@ubuntu:~/hask$ ghc -O2 shuffle.hs 
[1 of 1] Compiling Main    (shuffle.hs, shuffle.o) 
Linking shuffle ... 
carl@ubuntu:~/hask$ ./shuffle 
(1 1,[0, .. <redacted for brevity>]) 
warming up 
estimating clock resolution... 
mean is 5.762060 us (160001 iterations) 
found 4887 outliers among 159999 samples (3.1%) 
    4751 (3.0%) high severe 
estimating cost of a clock call... 
mean is 42.13314 ns (43 iterations) 

benchmarking shuffle1 
mean: 10.95922 ms, lb 10.92317 ms, ub 10.99903 ms, ci 0.950 
std dev: 193.8795 us, lb 168.6842 us, ub 244.6648 us, ci 0.950 
found 1 outliers among 100 samples (1.0%) 
variance introduced by outliers: 10.396% 
variance is moderately inflated by outliers 

benchmarking shuffle2 
mean: 256.9394 us, lb 255.5414 us, ub 258.7409 us, ci 0.950 
std dev: 8.042766 us, lb 6.460785 us, ub 12.28447 us, ci 0.950 
found 1 outliers among 100 samples (1.0%) 
    1 (1.0%) high severe 
variance introduced by outliers: 26.750% 
variance is moderately inflated by outliers 

좋아, 내 시스템이 정말 시끄러운이며, 비슷한 숫자 가지의 심각한 벤치마킹을 위해 사용할 수 없습니다 :

import System.Random 

import Control.Monad 

import Control.Monad.ST.Strict 
import Data.STRef.Strict 

import Data.Vector.Mutable 

import Prelude as P 

import Criterion.Main 


shuffle1 :: RandomGen g => [a] -> g -> ([a], g) 
shuffle1 [] g0 = ([],g0) 
shuffle1 [x] g0 = ([x],g0) 
shuffle1 xs g0 = (x:newtail,g2) 
    where (i,g1) = randomR (0, P.length $ P.tail xs) g0 
     (xs1,x:xs2) = P.splitAt i xs 
     (newtail,g2) = shuffle1 (xs1++xs2) g1 


shuffle2 :: RandomGen g => [a] -> g -> ([a], g) 
shuffle2 xs g0 = runST $ do 
    let l = P.length xs 
    v <- new l 
    sequence_ $ zipWith (unsafeWrite v) [0..] xs 

    let loop g i | i <= 1 = return g 
       | otherwise = do 
      let i' = i - 1 
       (j, g') = randomR (0, i') g 
      unsafeSwap v i' j 
      loop g' i' 

    gFinal <- loop g0 l 
    shuffled <- mapM (unsafeRead v) [0 .. l - 1] 
    return (shuffled, gFinal) 


main = do 
    let s1 x = fst $ shuffle1 x g0 
     s2 x = fst $ shuffle2 x g0 
     arr = [0..1000] :: [Int] 
     g0 = mkStdGen 0 
    -- make sure these values are evaluated before the benchmark starts 
    print (g0, arr) 

    defaultMain [bench "shuffle1" $ nf s1 arr, bench "shuffle2" $ nf s2 arr] 

그래서,의 몇 가지 결과를 볼 수 있습니다. 하지만 여기에서는 거의 중요하지 않습니다. shuffle2은 1001 개의 요소가있는 목록에서 shuffle1보다 약 40 배 빠릅니다. O (n)과 O (n^2)의 차이로 인해 더 큰 목록에서만 증가합니다. 나는 당신의 테스트 코드가 타이밍에 관계없이, 셔플 알고리즘이 아니라고 확신한다.

사실 나는 추측합니다. 귀하의 버전은 결과를 점진적으로 반환 할만큼 게으른 것입니다. 발전기를 호출 한 후 발전기를 만지지 않는다면 5 초가 처음 몇 가지 결과를 얻는 데 유력한 시간입니다. 어쩌면 그것은 당신의 타이밍에서 일어나는 일일 것입니다.