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操作を使用して vector パッケージを介して、ランダムなリスト順列を実行できます。

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>

多数のパッケージを使用して、効率的なランダム ベクトルを作成できます。

于 2012-08-24T17:34:09.860 に答える
0

自分で線形時間の解決策を見つけたと思うので、ここに追加する必要があると思いました。どうやら、forM や replicaM のような単項関数からリストを生成するのは単に悪い考えです。それらはスタックスペースを使い果たします。代わりに、純粋に命令型の処理にループを使用し、ループの外側で配列をリストに変換しました。コードは以下に貼り付けます。

誰かが興味を持っている場合に備えて、純粋に機能的な方法で同じことを行う優れた usenix の投稿がここにありますが、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 に答える