2

我很难理解为什么以下在 STArray 中查找最小元素的尝试在使用ghc（7.4.1，无论 -O 级别）编译时会导致堆栈空间溢出，但在以下情况下工作正常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

注意：切换到STUArrayorST.Lazy似乎没有任何效果。

STArray但主要问题是：在 big while inside上实现这种“折叠式”操作的正确方法是什么ST？

4

3 回答 3

5

这可能getElems是一个坏主意的结果。在这种情况下，数组完全是个坏主意：

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

这个马上给你答案：(1, 1, 1)。

如果您仍然想使用数组，我建议先将数组转换为Arrayor UArray，然后在该数组上使用elemsor assocs。如果您使用runSTArrayor执行此操作，则无需额外费用runSTUArray。

于 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的 monad 中堆栈溢出的常见原因，因为(>>=)

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)

创建一个巨大的 thunk 溢出堆栈。对于严格的ST变体，您需要getElems用构建列表的东西替换，sequence或者 - 更好地 - 计算最小值而不创建元素列表。对于惰性ST变体，您需要确保数组的填充不会产生巨大的 thunk，例如通过强制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，因此它构建了一个巨大的 thunk 来计算最小值。您可以通过使用seq（或 bang-pattern）使其在m.

STArray但主要问题是：在 big while inside上实现这种“折叠式”操作的正确方法是什么ST？

通常，您将使用 strictST变体（对于 类似的类型Int，您几乎肯定应该使用STUArrays 而不是STArrays）。那么最重要的规则是你的函数足够严格。的结构findMin2还可以，实现就是太懒了。

如果性能很重要，您通常必须避免使用通用的高阶函数，foldM并编写自己的循环以避免分配列表​​并完全按照手头的问题要求控制严格性。

于 2013-01-23T15:42:17.947 回答
0

问题是 minimum 是一个非严格的折叠，所以它会导致 thunk 堆积。使用 (foldl' min)。

现在我们添加一堆废话来忽略，因为 stackoverflow 已经变得毫无价值，不再允许发布直接的答案。

于 2013-01-23T11:29:21.843 回答