编写此函数的正确(有效)方法是什么？

Question

以下函数返回从根节点到树的最深节点的可能路径列表:

paths :: Tree a -> [[a]]
paths (Node element []) = [[element]]
paths (Node element children) = map (element :) $ concat $ map paths children

这在纸面上看起来非常低效,因为它concat具有可怕的复杂性.是否可以在不使用中间数据结构(如序列)的情况下以较低的复杂度重写此函数？

编辑:说实话,我知道可以通过以下方式避免连接的O(n)/循环复杂性:

1. 在递归时构建路径(列表);
2. 仅当您到达最后一个递归级别时,将路径追加到全局"结果"列表.

这是一个JavaScript实现,说明了这个算法:

function paths(tree){
    var result = [];
    (function go(node,path){
        if (node.children.length === 0)
            result.push(path.concat([node.tag]));
        else
            node.children.map(function(child){
                go(child,path.concat([node.tag]));
            });
    })(tree,[]);
    return result;
}
console.log(paths(
    {tag: 1,
    children:[
        {tag: 2, children: [{tag: 20, children: []}, {tag: 200, children: []}]},
        {tag: 3, children: [{tag: 30, children: []}, {tag: 300, children: []}]},
        {tag: 4, children: [{tag: 40, children: []}, {tag: 400, children: []}]}]}));

(它实际上不是O(1)/迭代,因为我使用Array.concat而不是列表consing(JS没有内置列表),但只是使用它而不是每次迭代使它成为常量时间.)

Answer 1

concat没有可怕的复杂性; 它是O(n),n每个列表中的元素总数,但是最后一个.在这种情况下,除非您更改结果的类型,否则我认为无论是否有中间结构都不可能做得更好.在此上下文中,列表列表绝对没有共享的可能性,因此您别无选择,只能分配每个列表的每个"缺点".该concatMap只增加了一个常数因子开销,我会感到惊讶,如果你能找到一种方法来减少显著.

如果您想使用某些共享(以结构性惰性为代价),您确实可以切换到不同的数据结构.只有当树有点"浓密"时,这才有意义.任何序列类型支持snoc都可以.最简单的是,您甚至可以反向使用列表,因此您可以获得从叶子到根的路径,而不是相反的路径.或者你可以使用更灵活的东西Data.Sequence.Seq:

import qualified Data.Sequence as S
import Data.Sequence ((|>), Seq)
import qualified Data.DList as DL
import Data.Tree

paths :: Tree a -> [Seq a]
paths = DL.toList . go S.empty
  where
    go s (Node a []) = DL.singleton (s |> a)
    go s (Node a xs) = let sa = s |> a
                       in sa `seq` DL.concat . map (go sa) $ xs

编辑

正如Viclib和delnan指出的那样,我的原始答案存在问题,因为底层被多次遍历.

Answer 2

我们的基准:

{-# LANGUAGE BangPatterns #-}

import Control.DeepSeq
import Criterion.Main
import Data.Sequence ((|>), Seq)
import Data.Tree
import GHC.DataSize
import qualified Data.DList as DL
import qualified Data.Sequence as S

-- original version
pathsList :: Tree a -> [[a]]
pathsList = go where
  go (Node element []) = [[element]]
  go (Node element children) = map (element:) (concatMap go children)

-- with reversed lists, enabling sharing of path prefixes
pathsRevList :: Tree a -> [[a]]
pathsRevList = go [] where
  go acc (Node a []) = [a:acc]
  go acc (Node a xs) = concatMap (go (a:acc)) xs

-- dfeuer's version
pathsSeqDL :: Tree a -> [Seq a]
pathsSeqDL = DL.toList . go S.empty
  where
    go s (Node a []) = DL.singleton (s |> a)
    go s (Node a xs) = let sa = s |> a
                       in sa `seq` DL.concat . map (go sa) $ xs

-- same as previous but without DLists. 
pathsSeq :: Tree a -> [Seq a]
pathsSeq = go S.empty where
  go acc (Node a []) = [acc |> a]
  go acc (Node a xs) = let acc' = acc |> a
                       in acc' `seq` concatMap (go acc') xs

genTree :: Int -> Int -> Tree Int
genTree branch depth = go 0 depth where
  go n 0 = Node n []
  go n d = Node n [go n' (d - 1) | n' <- [n .. n + branch - 1]]

memSizes = do
  let !tree = force $ genTree 4 4      
  putStrLn "sizes in memory"
  putStrLn . ("list: "++) . show =<< (recursiveSize $!! pathsList tree)
  putStrLn . ("listRev: "++) . show =<< (recursiveSize $!! pathsRevList tree)
  putStrLn . ("seq: "++) . show =<< (recursiveSize $!! pathsSeq tree)
  putStrLn . ("tree itself: "++) . show =<< (recursiveSize $!! tree)

benchPaths !tree = do
  defaultMain [
    bench "pathsList" $ nf pathsList tree,
    bench "pathsRevList" $ nf pathsRevList tree,
    bench "pathsSeqDL" $ nf pathsSeqDL tree,
    bench "pathsSeq" $ nf pathsSeq tree
    ]  

main = do
  memSizes
  putStrLn ""
  putStrLn "normal tree"
  putStrLn "-----------------------"
  benchPaths (force $ genTree 6 8)
  putStrLn "\ndeep tree"
  putStrLn "-----------------------"  
  benchPaths (force $ genTree 2 20)
  putStrLn "\nwide tree"
  putStrLn "-----------------------"  
  benchPaths (force $ genTree 35 4)  

一些说明:

• 我使用-O2和-fllvm对GHC 7.8.4进行基准测试.
• 我genTree用一些Int-s 填充树,以防止GHC优化导致子树被共享.
• 在memSizes树中必须非常小,因为它recursiveSize具有二次复杂性.

我的Core i7 3770上的结果:

sizes in memory
list: 37096
listRev: 14560
seq: 26928
tree itself: 16576

normal tree
-----------------------
pathsList               372.9 ms   
pathsRevList            213.6 ms   
pathsSeqDL              962.2 ms   
pathsSeq                308.8 ms   

deep tree
-----------------------
pathsList               554.1 ms   
pathsRevList            266.7 ms   
pathsSeqDL              919.8 ms   
pathsSeq                438.4 ms   

wide tree
-----------------------
pathsList               191.6 ms   
pathsRevList            129.1 ms   
pathsSeqDL              448.2 ms   
pathsSeq                157.3 ms  

评论:

• 我完全没有意外.带有列表的原始版本对于作业而言是渐近最佳的.此外,DList只有当我们否则会有低效的列表追加时才使用它是有意义的,但在这里并非如此.
• 请注意,反向路径列表占用的空间比树本身少.
• 在不同形状的树木上,性能模式是一致的.在"深树"案例中Seq表现相对较差,大概是因为Seqsnoc比列表缺点更昂贵.
• 我认为Clojure风格的持久向量(Int-indexed shallow try)在这里会很好,因为它们可以非常快,可能比普通列表具有更少的空间开销,并支持高效的snoc和随机读/写.相比之下,Seq虽然它支持更广泛的高效操作,但重量更重.