Fisher-Yatesのシャッフルに何か問題がありますか？

Question

何かが本当に良いと思われるときは、通常はそうですが、私はうまくいけばグレムリンを洗い流すためにこの質問をすると思いました。私は見つけることができるいくつかの関連スレッドを見直しましたが、まだ私の質問は残っています。

私は比較的新しいHaskellです。私の実験では、以下に示すように基本的なFisher-Yatesシャッフルをコーディングしました。

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使用していますが、それは高速です - ）2.3sでSTD C++シャッフル対30M int型のために私のラップトップの平均5S上。実際、他のHaskellの実装よりもはるかに高速です（例えば、http://www.haskell.org/haskellwiki/Random_shuffle）

私が見た他のHaskellシャッフルは、より複雑で低速ですが、私はスピードアップ/シンプルさが単に私のものかどうか疑問です私のアルゴリズムが偏ってしまっているような、細かくはっきりとした細部を見逃してしまった場合は、私は広範囲にテストしていませんが、予備的な外観は順列の一様分布を示すようです。

私は、より多くのハスケルやシャッフルの経験でより多くの目を評価していただきたいと思います。返信する時間がかかるすべての人に事前に感謝します。

Answer 1

適切なベンチマークを試してみましょう。ここであなたのシャッフルをshuffle1に変更し、私の個人的に好きなものをshuffle2という名前で変更したコードがあります。

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] 

そしてそう、のは、いくつかの結果を見てみましょう：

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 

[OK]を、私のシステムは本当にうるさいです、と同様の番号を持つ事の深刻なベンチマーキングのために使用すべきではありません。しかし、ここではそれほど重要ではありません。 shuffle2は、要素数1001のリストのshuffle1より約40倍高速です。 O（n）とO（n^2）の違いのために、それは大きなリストでのみ増加します。あなたのテストコードがどんなタイミングであっても、それはシャッフルアルゴリズムではありませんでした。

実際、私は推測しています。あなたのバージョンは結果を徐々に返すほど怠惰です。ジェネレータを呼び出した後にジェネレータに触れることがない場合は、最初のいくつかの結果を得るためには5秒が当てはまります。たぶんあなたのタイミングで起こっていることです。