以下函数返回从根节点到树的最深节点的可能路径列表:
paths :: Tree a -> [[a]]
paths (Node element []) = [[element]]
paths (Node element children) = map (element :) $ concat $ map paths children
这在纸面上看起来非常低效,因为 concat
具有可怕的复杂性。是否可以在不使用中间数据结构(如序列)的情况下以降低复杂性的方式重写此函数?
编辑:老实说,我知道可以通过以下方式避免 concat 的 O(n)/循环复杂性:
- 在递归过程中构建路径(列表);
- 仅当到达最后一个递归级别时,才将路径附加到全局“结果”列表。
下面是一个 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 没有内置列表),但只是使用它会使其在每次迭代中保持恒定时间。)
最佳答案
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 指出的那样,我原来的答案有问题,因为底层被遍历了多次。
关于haskell - 编写此函数的正确(有效)方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27784506/