2

STArrayで最小要素を見つけようとする次の試みが、ghc（-Oレベルに関係なく、7.4.1）でコンパイルされたときにスタックスペースのオーバーフローにつながる理由を理解するのに苦労していますが、次の場合は正常に機能しますghci：

import Control.Monad
import Control.Monad.ST
import Control.Applicative
import Data.Array.ST

n = 1000 :: Int

minElem = runST $ do
  arr <- newArray ((1,1),(n,n)) 0 :: ST s (STArray s (Int,Int) Int)
  let ixs = [(i,j) | i <- [1..n], j <- [1..n]]
  forM_ ixs $ \(i,j) -> writeArray arr (i,j) (i*j `mod` 7927)
--  readArray arr (34,56)  -- this works OK
--  findMin1 arr           -- stackoverflows when compiled
  findMin2 arr           -- stackoverflows when compiled

findMin1 arr = do
  es <- getElems arr
  return $ minimum es

findMin2 arr = do
  e11 <- readArray arr (1,1) 
  foldM (\m ij -> min m <$> readArray arr ij) e11 ixs
      where ixs = [(i,j) | i <- [1..n], j <- [1..n]]

main = print minElem

注：切り替えてSTUArrayもST.Lazy効果がないようです。

STArrayしかし、主な質問：内部でこのような「折り畳みのような」操作を大規模に実装する適切な方法は何でしょうSTか。

4

3 に答える 3

5

それはおそらくgetElems悪い考えの結果です。この場合、配列はまったく悪い考えです。

minimum (zipWith (\x y -> (x, y, mod (x*y) 7927)) [1..1000] [1..1000])

これはすぐに答えを与えます：（1、1、1）。

とにかく配列を使用したい場合は、最初に配列をArrayまたはに変換してから、その配列でまたはを使用することをお勧めします。またはを使用して行う場合、これには追加費用はかかりません。UArrayelemsassocsrunSTArrayrunSTUArray

于 2013-01-23T02:42:27.563 に答える
3

の大きな問題findMin1はgetElems：

getElems :: (MArray a e m, Ix i) => a i e -> m [e]
getElems marr = do
  (_l, _u) <- getBounds marr      -- Hmm, why is that there?
  n <- getNumElements marr
  sequence [unsafeRead marr i | i <- [0 .. n - 1]]

sequence長いリストで使用することは(>>=)、十分に怠惰ではないモナドでのスタックオーバーフローの一般的な原因です。

sequence ms = foldr k (return []) ms
        where
          k m m' = do { x <- m; xs <- m'; return (x:xs) }

次に、リストの長さに比例したサイズのサンクを作成する必要があります。getElemsで動作しますControl.Monad.ST.Lazyが、配列を次のように入力します

forM_ ixs $ \(i,j) -> writeArray arr (i,j) (i*j `mod` 7927)

スタックをオーバーフローする巨大なサンクを作成します。厳密なSTバリアントの場合、要素のリストをまったく作成せずにリストを作成するもの、または-はるかに優れた-最小値を計算するgetElemsものに置き換える必要があります。sequence怠惰なバリアントの場合、たとえば呼び出しSTの結果を強制することによって、配列の塗りつぶしが巨大なサンクを構築しないことを確認する必要がありますwriteArray

let fill i j
      | i > n     = return ()
      | j > n     = fill (i+1) 1
      | otherwise = do
          () <- writeArray arr (i,j) $ (i*j `mod` 7927)
          fill i (j+1)
() <- fill 1 1

の問題findMin2は

foldM (\m ij -> min m <$> readArray arr ij) e11 ixs

で怠惰なmので、最小値を計算するために巨大なサンクを構築します。seqで（またはbang-pattern）を使用して厳密にすることで、これを簡単に修正できますm。

STArrayしかし、主な質問：内部でこのような「折り畳みのような」操作を大規模に実装する適切な方法は何でしょうSTか。

通常、厳密なSTバリアントを使用します（また、のようなタイプのInt場合は、ほぼ確実STUArrayにsの代わりにSTArraysを使用する必要があります）。次に、最も重要なルールは、関数が十分に厳密であるということです。の構造findMin2は大丈夫です、実装はあまりにも怠惰です。

foldMパフォーマンスが重要な場合は、リストの割り当てを回避し、目前の問題が要求するとおりに厳密さを制御するために、のような一般的な高階関数を避け、独自のループを作成する必要があります。

于 2013-01-23T15:42:17.947 に答える
0

問題は、最小値が厳密ではないフォールドであるため、サンクの蓄積を引き起こしていることです。（foldl'min）を使用します。

今度は、stackoverflowが無価値になり、簡単な回答を投稿できなくなったため、無視する冗長性を追加します。

于 2013-01-23T11:29:21.843 に答える