Qualcosa che non va con il mio Fisher-Yates shuffle?

Question

Consapevole del fatto che quando qualcosa sembra troppo bello per essere vero di solito è, ho pensato che avrei posto questa domanda per eliminare eventualmente tutti i gremlins. Ho esaminato i pochi thread correlati che ho potuto trovare, ma la mia domanda rimane ancora.

Sono relativamente nuovo per Haskell, e nella mia sperimentazione ho codificato un rimescolamento base di Fisher-Yates come mostrato di seguito.

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 

Questa implementazione del corso utilizza la memoria beaucoup per grandi liste, ma è veloce - sul mio portatile 5s medio per 30M interi vs. Std C++ casuale a 2.3s). In effetti, è molto più veloce di altre implementazioni Haskell trovato altrove. (Ad esempio, http://www.haskell.org/haskellwiki/Random_shuffle)

Dato altri shuffle Haskell che ho visto sono entrambi più complicati e più lenti, mi chiedo se la velocità/semplicità sia semplicemente la mia ricompensa per essere un porco menefreghista, o se mi sono perso qualche dettaglio minuscolo ma cruciale che rende distorto il mio algoritmo. Non ho testato estesamente, ma un aspetto preliminare sembra mostrare una distribuzione uniforme delle permutazioni.

Apprezzerei la valutazione di più occhi con più esperienza Haskell e/o mischia. Mille grazie in anticipo a tutti coloro che hanno il tempo di rispondere.

Answer 1

Facciamo un buon benchmarking. Ecco un codice, con il tuo shuffle rinominato in shuffle1 e la mia variante preferita personale generata come 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] 

E così, vediamo alcuni risultati:

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, il mio sistema è veramente rumoroso, e non dovrebbe essere utilizzato per l'analisi comparativa seria di cose con numeri simili. Ma questo non ha importanza qui. shuffle2 è circa 40 volte più veloce di shuffle1 in un elenco con 1001 elementi. A causa delle differenze tra O (n) e O (n^2), ciò aumenterà solo con elenchi più grandi. Sono certo che qualunque fosse il tuo codice di test era temporizzato, non era l'algoritmo shuffle.

In realtà, ho una supposizione. La tua versione è abbastanza pigra da restituire i risultati in modo incrementale. 5 secondi è un periodo di tempo plausibile per ottenere i primi risultati, se non si tocca mai il generatore dopo la chiamata. Forse è quello che sta succedendo nei tuoi tempi.