algorithm - 优化大向量的操作

Question

这是我的 previous question 的跟进关于处理 5.1m 边有向图的向量表示。我正在尝试实现 Kosaraju 的图形算法，因此需要按照深度优先搜索 (DFS) 的结束时间顺序重新排列我的 Vector 边缘反转。我有在小数据集上运行的代码，但在 10 分钟内无法在完整数据集上返回。 (我不能排除大图会产生循环，但在我的测试数据中没有任何迹象。)

DFS 需要避免重新访问节点，因此我需要某种“状态”来进行搜索(目前是一个元组，我应该使用 State Monad 吗？)。第一次搜索应该返回一个重新排序的 Vector，但我目前通过返回一个重新排序的节点索引列表来保持事情简单，以便我可以随后一次性处理该 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 = 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

Answer 1

简而言之:

了解时间复杂度。

优化有很多要点，其中很大一部分在日常编程中不是很重要，但如果不知道渐近复杂性，程序通常根本无法运行。

Haskell 库通常会记录复杂性，尤其是当它不明显或无效时(线性或更糟)。特别是，与此问题相关的所有复杂性都可以在 Data.List 和 Data.Vector 中找到。

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

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

此外，搜索实现对我来说似乎相当模糊和过于复杂。旨在对 Wiki 上的伪代码进行字面翻译页面应该是一个好的开始。此外，没有必要将索引存储在节点中，因为它们可以从向量位置和邻接列表中确定。