隨機排列大型列表（超過1億個元素）

我不介意以「功能」的方式來完成。但我確實需要它是線性時間（而不是O（n log n）），並且我更喜歡類型簽名保持完整（即不添加其他類型約束）。這是我到目前爲止，但我不斷收到一個堆棧溢出：隨機排列大型列表（超過1億個元素）

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中，我似乎無法弄清楚如何。我發現了一些方法，如果我使用unboxed數組。但正如我所說，我不想添加額外的限制。有任何想法嗎？

編輯：我也很感激，如果有人可以向我解釋上面的代碼是如何消耗堆棧空間，以及爲什麼我不能簡單地避免使用尾遞歸調用。我嘗試在某些地方使用急切的評估，但它並沒有幫助

來源

2012-08-24 Samee

隨機列表置換可以通過矢量包使用backpermute在/ O（n）/（假設您有一個隨機輸入數組）操作。

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>

您可以通過a number of packages.

來源

2012-08-24 17:34:09

謝謝。但是這難道不會將問題轉換爲生成整數置換的問題嗎？如果我理解正確，你的軟件包（mersenne-random，vector-random等）不會導出任何生成具有非重複元素的向量的方法。由於我對haskell比較新，我還想知道GHC運行時如何在我粘貼的代碼中使用堆棧空間，以便我不會再犯同樣的錯誤 – Samee

它將問題分解爲O（ n）組件來執行置換，並且O（n log n）步驟來生成唯一的隨機數（通過集合的一個集合） –

啊，所以我們回到O（n log n）。好，謝謝。但我們可以避免這種情況嗎？只是好奇 – Samee

創建高效的隨機向量我覺得剛剛找到一個線性時間的解決方案我自己，所以我想我應該在這裏添加它。顯然，從forM或replicateM等monadic函數生成列表是一個糟糕的主意。他們用盡堆棧空間。相反，我只是爲了純粹的命令式處理而使用循環，然後將數組轉換爲循環外的列表。代碼粘貼在下面。

如果有人有興趣，有一個偉大的usenix後here，它以純粹的功能方式做同樣的事情，但使用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-24 23:35:47 Samee

隨機排列大型列表（超過1億個元素）

回答

相關問題