随机置换大型列表(超过1亿个元素)

Question

我不关心以"功能"方式做到这一点.但我确实需要它在线性时间(不是O(n log n)),我真的更喜欢类型签名保持完整(即,不添加其他类型约束).这是我到目前为止,但我不断得到堆栈溢出:

import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.STRef
import System.Random

randomPermute :: RandomGen g => [a] -> g -> ([a],g)
randomPermute l rgen = runST $ newListArray (1,n) l >>= body rgen where
  n = length l
  body :: RandomGen g => g -> STArray s Int e -> ST s ([e],g)
  body rgen arr = do
    rgenRef <- newSTRef rgen
    let pick i j   = do vi <- readArray arr i
                        vj <- readArray arr j
                        writeArray arr j vi
                        return vj
        rand lo hi = do rgen <- readSTRef rgenRef
                        let (v,rgen') = randomR (lo,hi) rgen
                        writeSTRef rgenRef rgen'
                        return v
    rv <- forM [1..n] $ \i -> do
        j <- rand i n
        pick i j
    rgen <- readSTRef rgenRef
    return (rv,rgen)

ascCount x = sum $ map oneIfBig $ zip x $ tail x where
  oneIfBig (x,y) = if x<y then 0 else 1

main = do
  -- Using String types just for testing
  res <- getStdRandom $ randomPermute $ map show [1..1000000]
  putStrLn $ show $ ascCount res

现在我与命令式语言的交易告诉我应该有一种方法来避免一起使用堆栈.但在Haskell,我似乎无法弄清楚如何.我找到了一些方法,如果我使用未装箱的数组.但就像我说的,我宁愿不添加额外的约束.有任何想法吗？

编辑:我也很感激,如果有人可以向我解释上面的代码是如何消耗堆栈空间,为什么我不能简单地避免使用尾递归调用.我尝试在某些地方使用热切评估,但它没有帮助

Answer 1

随机列表置换可以在/ O(n)/(假设你有一个随机输入数组),通过向量包,使用该backpermute操作完成.

backpermute :: Unbox a => Vector a -> Vector Int -> Vector a

/O(n)/
Yield the vector obtained by replacing each element i of the index vector by xs!i. This is equivalent to map (xs!) is but is often much more efficient.

即

 backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>

您可以通过许多包创建有效的随机向量.