Re: リストをシャッフルする関数

こちらの記事にArrayで書かれていたのを見て、Vectorの方が速いと耳にしたことがあったので書いてみました。

module Main where

import Control.Monad (zipWithM_)
import Control.Monad.ST (ST)
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import System.Random (getStdRandom, randomR)

main :: IO ()
main = print =<< shuffle ([1..10000000]::[Int])

shuffle :: (VU.Unbox a) => [a] -> IO [a]
shuffle xs = do
  let m = length xs - 1
  randoms <- mapM (\i -> getStdRandom (randomR (0, i))) [m,m-1..1]
  return $ VU.toList $ VU.modify (\vum -> swaps vum [m,m-1..1] randoms) $ VU.fromList xs
  where
    -- | Mutable Vector -> Swap Indexes A -> Swap Indexes B -> ST s ()
    swaps :: (VU.Unbox a) => VUM.MVector s a -> [Int] -> [Int] -> ST s ()
    swaps = zipWithM_ . VUM.swap

所要時間は2/3くらいになりますが、こんなに時間がかかるものなのですかね？
[m,m-1..1]が共通だからと名前をつけたら遅くなったのは、キャッシュされたせいかな。