优化大向量的操作

这是我的后续行动上一个问题 https://stackoverflow.com/questions/24278006/need-advice-on-optimising-haskell-data-processing关于处理 5.1m 边有向图的向量表示。我正在尝试实现 Kosaraju 的图算法，因此需要按照反向边缘上深度优先搜索（DFS）的完成时间的顺序重新排列我的向量。我的代码可以在小数据集上运行，但在完整数据集上无法在 10 分钟内返回。 （我不能排除大图会产生循环，但我的测试数据上没有任何迹象。）

DFS 需要避免重新访问节点，因此我需要某种“状态”来进行搜索（当前是一个元组，我应该使用 State Monad 吗？）。第一次搜索应该返回一个重新排序的向量，但我目前通过返回重新排序的节点索引列表来保持简单，以便我可以随后一次性处理该向量。

我认为问题在于dfsInner。下面的代码“记住”访问过的节点，更新每个节点的探索字段（第三个守卫）。尽管我尝试使其尾递归，但代码似乎使内存使用量增长得相当快。我需要执行一些严格的规定吗如果是这样，怎么办？ （我有另一个用于单个搜索的版本，它通过查看堆栈上未探索的边缘的起始节点和已完成的节点列表来检查以前的访问。这不会增长得那么快，但是不会返回任何连接良好的节点。）

然而，它也可能是foldr', but 我怎样才能检测到?

这应该是 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 = dfsOuter gr
    --return gr
    putStrLn $ show res

dfsOuter gr = 
    let tmp = V.foldr' callInner (gr,[]) gr
    in snd tmp

callInner :: Node -> (Graph, Stack) -> (Graph, Stack)
callInner (Node idx _ fwd bwd) (gr,acc) = 
    let (Node _ explored _ _) = gr V.! idx
    in case explored of
        True  -> (gr, acc)
        False ->
            let
                initialStack = map (\l -> (idx, l)) bwd
                gr' = gr V.// [(idx, Node idx True fwd bwd)]
                (gr'', newScc) = dfsInner idx initialStack (length acc) (gr', [])
            in (gr'', newScc++acc)

dfsInner :: NodeName -> Stack -> Int -> (Graph, [(Int, Int)]) -> (Graph, [(Int, Int)])
dfsInner start [] finishCounter (gr, acc) = (gr, (start, finishCounter):acc)
dfsInner start stack finishCounter (gr, acc)
    | nextStart /= start =                      -- no more places to go from this node
        dfsInner nextStart stack (finishCounter + 1) $ (gr, (start, finishCounter):acc)
    | nextExplored = 
-- nextExplored || any (\(y,_) -> y == stack0Head) stack || any (\(x,_) -> x == stack0Head) acc =
        dfsInner start (tail stack) finishCounter (gr, acc)
    | otherwise =
        dfsInner nextEnd (add2Stack++stack) finishCounter (gr V.// [(nextEnd, Node idx True nextLHS nextRHS)], acc)
--      dfsInner gr stack0Head (add2Stack++stack) finishCounter acc

    where
        (nextStart, nextEnd) = head stack
        (Node idx nextExplored nextLHS nextRHS) = gr V.! nextEnd
        add2Stack = map (\l -> (nextEnd, l)) nextRHS

简而言之：

了解时间复杂度。

优化有很多要点，其中很大一部分在日常编程中并不是很重要，但如果不了解渐近复杂性，程序通常会变得很糟糕。根本不起作用.

Haskell 库通常会记录复杂性，尤其是当它不明显或无效时（线性或更糟）。特别是，与这个问题相关的所有复杂性都可以在Data.List and Data.Vector.

性能被杀死V.//这里。向量是内存中装箱或拆箱的不可变连续数组。因此，修改它们需要复制整个向量。由于我们有 O(N) 这样的修改，整个算法是 O(n^2)，所以我们必须复制大约 2 TB，其中 N = 500000。因此，在向量内标记访问过的节点没有多大用处。相反，建立一个IntSet根据需要的索引。

initialStack (length acc)看起来也很糟糕。使用它几乎从来都不是一个好主意length在大型列表上，因为它也是 O(n)。它可能没有那么糟糕//在您的代码中，因为它位于相对很少出现的分支中，但在我们更正矢量问题后，它仍然会导致性能下降。

此外，搜索实现对我来说似乎相当不清楚且过于复杂。旨在对伪代码进行字面翻译Wiki http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm页面应该是一个好的开始。此外，没有必要将索引存储在节点中，因为它们可以根据向量位置和邻接列表来确定。