相关疑难解决方法(0)

编辑: 事实证明,一般情况下(不仅仅是数组/参考操作)减慢了更多阵列的创建速度,所以我猜这可能只是测量增加的GC时间,可能不像我想的那么奇怪.但我真的很想知道(并学习如何找出)这里发生了什么,以及是否有一些方法可以在创建大量小数组的代码中缓解这种影响.原始问题如下.

在调查库中的一些奇怪的基准测试结果时,我偶然发现了一些我不理解的行为,尽管它可能非常明显.似乎许多操作(创建新的MutableArray,读取或修改IORef)所花费的时间与内存中的数组的数量成比例地增加.

这是第一个例子:

module Main
    where 

import Control.Monad
import qualified Data.Primitive as P
import Control.Concurrent
import Data.IORef
import Criterion.Main
import Control.Monad.Primitive(PrimState)

main = do 
  let n = 100000
  allTheArrays <- newIORef []
  defaultMain $
    [ bench "array creation" $ do
         newArr <- P.newArray 64 () :: IO (P.MutableArray (PrimState IO) ())
         atomicModifyIORef'  allTheArrays (\l-> (newArr:l,()))
    ]

我们正在创建一个新数组并将其添加到堆栈中.随着标准越来越多样本和堆栈增长,数组创建需要更多时间,而且这似乎是线性和定期增长的:

更奇怪的是,IORef读取和写入都会受到影响,并且我们可以看到atomicModifyIORef'随着更多阵列的GC 而越来越快.

main = do 
  let n = 1000000
  arrs <- replicateM (n) $ …

这是我之前关于处理5.1米边缘有向图的矢量表示的问题的后续内容.我正在尝试实现Kosaraju的图算法,因此需要按照边缘反转的深度优先搜索(DFS)的完成时间的顺序重新排列我的Vector.我的代码在小数据集上运行,但在完整数据集上无法在10分钟内返回.(我不能排除大图出现循环,但我的测试数据没有迹象表明.)

DFS需要避免重新访问节点,因此我需要某种"状态"进行搜索(目前是一个元组,我应该使用State Monad吗？).第一次搜索应该返回一个重新排序的Vector,但是我现在通过返回重新排序的Node索引列表来保持简单,这样我就可以随后一次处理Vector.

我认为问题在于dfsInner.下面的代码"记住"访问的节点更新每个节点(第三个防护)的探索字段.虽然我试图使其尾递归,但代码似乎相当快地增加了内存使用. 我是否需要强制执行某些严格性,如果是,请如何执行？(我在单个搜索搜索中使用了另一个版本,它通过查看堆栈上未开发边缘的起始节点和已完成的节点列表来检查先前的访问.这不会增长得那么快,但是没有为任何连接良好的节点返回.)

但是,它也可能是foldr',但我怎么能检测出来？

这应该是Coursera的家庭作业,但我不再确定我可以勾选荣誉代码按钮!学习更重要,所以我真的不想复制/粘贴答案.我所拥有的并不是非常优雅 - 它也有一种迫切的感觉,这是由于保持某种状态的问题所致 - 见第三后卫.我欢迎对设计模式的评论.

type NodeName = Int
type Edges    = [NodeName]
type Explored = Bool
type Stack    = [(Int, Int)]

data Node  = Node NodeName Explored Edges Edges deriving (Eq, Show)
type Graph = Vector Node

main = do
    edges <- V.fromList `fmap` getEdges "SCC.txt"
    let 
        maxIndex = fst $ V.last edges
        gr = createGraph maxIndex edges
        res = …