1

我不在乎以“功能性”的方式来做。但我确实需要它处于线性时间（而不是 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 中，我似乎无法弄清楚如何。如果我使用未装箱的数组，我发现了一些可行的方法。但就像我说的，我不希望添加额外的约束。有任何想法吗？

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

4

2 回答 2

5

随机列表排列可以在 /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.

IE

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

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

于 2012-08-24T17:34:09.860 回答
0

我想我自己找到了一个线性时间解决方案，所以我想我应该在这里添加它。显然，从 forM 或 replicateM 等一元函数生成列表是个坏主意。它们耗尽了堆栈空间。相反，我将循环仅用于纯粹的命令式处理，然后将数组转换为循环外的列表。代码粘贴在下面。

如果有人感兴趣，这里有一篇很棒的 useenix 帖子，它以纯粹的功能方式做同样的事情，但使用 O(n log n) 时间。

randomPermute :: RandomGen g => [a] -> g -> ([a],g)
randomPermute x rgen = (body,rgen2) where
  (rgen1,rgen2) = split rgen
  body = elems $ runST $ do
    g   <- newSTRef rgen1
    arr <- newArray x
    let newInd st = do
          (i,rgen') <- liftM (randomR (st,n-1)) (readSTRef g)
          writeSTRef g rgen'
          return i
    forM_ [0..n-1] $ \i -> do
      j <- newInd i
      p <- readArray arr i
      q <- readArray arr j
      writeArray arr j p
      writeArray arr i q
    unsafeFreeze arr
  n = length x
  newArray :: [a] -> ST s (STArray s Int a)
  newArray x = newListArray (0,length x-1) x
于 2012-08-24T23:35:47.743 回答