减少深度优先遍历树的空间使用率 [英] Reducing space usage of depth first tree traversal

问题描述

在Haskell中，可以在恒定空间中的无限列表上进行过滤器，和等操作，因为Haskell只在需要时产生列表节点，而垃圾收集它完成的列表节点。

下面是一个相当愚蠢的程序，它会生成一个无限二叉树，其节点代表自然数。

p>

然后我编写了一个函数，对该树进行深度优先遍历，将特定级别的节点吐出。

然后我已经对可以被5除的节点做了一个快速求和。理论上，这个算法可以在 O （n）对于 n 的深度空间 O（2 ^ n）节点的深度树。只需简单地生成树，就可以删除已完成处理的节点。

Haskell确实会即时生成树，但不会垃圾收集节点它似乎。

以下是代码，我希望看到具有类似效果的代码，但不需要 O（2 ^ ）
$ b

  import Data.List（foldl'）
 
数据Tree =树Int树树
 
树n =树n（树（2 * n））（树（2 * n + 1））
 treeOne =树1 
 
 depthNTree nx = go nx id []其中
 go :: Int  - >树 - > （[Int]  - > [Int]） - > [Int]  - > [Int] 
 go 0（Tree x _ _）acc rest = acc（x：rest）
 go n（Tree _ left right）acc rest = t2其中
 t1 = go n  -  1）left acc 
 t2 = go（n  -  1）right t1 
 
 main = do 
x<  -  getLine 
 print。 foldl'（+）0。过滤器（\ x  - > x`rem` 5 == 0）$ depthNTree（read x）treeOne 
  




depthNTree 使用 2 ^ n 空格，因为您保留当你遍历右子树时，左子树遍历 t1 。在右子树上的递归调用应该不包含对左边的引用，作为增量垃圾收集遍历的必要条件。 在本例中，朴素版本可以接受： / p>

  depthNTree nt = go nt其中
变为0（Tree x _ _）= [x] 
 go n（Tree_lr）= go（n-1）l ++ go（n-1）r 
  

<现在 main 输入24使用2 MB空间，而原始版本使用1820 MB。这里的最佳解决方案与上面类似，只是它使用差异列表：

  depthNTree nt = go nt []其中
去0（Tree x _ _）=（x :) 
 go n（Tree _ lr）= go（n  -  1）l。 go（n  -  1）r 
  

在很多情况下，这并不比普通列表版本快得多，因为在20-30左右的树深度下， ++ 左边的嵌套并不是很昂贵。如果我们使用大树深度，这种差异会变得更加明显：

  print $ sum $ take 10 $ depthNTree 1000000 treeOne 
  

在我的计算机上，它的运行时间为0.25秒，差异列表为1.6秒，列表为1.6秒。

In Haskell, one can do filters, sums, etc on infinite lists in constant space, because Haskell only produces list nodes when needed, and garbage collects ones it's finished with.

I'd like this to work with infinite trees.

Below is a rather silly program that generates a infinite binary tree with nodes representing the natural numbers.

I've then written a function that does a depth first traversal of this tree, spitting out the nodes at a particular level.

Then I've done a quick sum on the nodes divisable by 5.

In theory, this algorithm could be implemented in O(n) space for an n depth tree of O(2^n) nodes. Just generate the tree on the fly, removing the nodes you've already completed processing.

Haskell does generate the tree on the fly, but doesn't garbage collect the nodes it seems.

Below is the code, I'd like to see code with a similar effect but that doesn't require O(2^n) space.

import Data.List (foldl')

data Tree = Tree Int Tree Tree

tree n = Tree n (tree (2 * n)) (tree (2 * n + 1))
treeOne = tree 1

depthNTree n x = go n x id [] where
  go :: Int -> Tree -> ([Int] -> [Int]) -> [Int] -> [Int]
  go 0 (Tree x _ _) acc rest = acc (x:rest)
  go n (Tree _ left right) acc rest = t2 rest where 
    t1 = go (n - 1) left acc
    t2 = go (n - 1) right t1

main = do
  x <- getLine
  print . foldl' (+) 0 . filter (\x -> x `rem` 5 == 0) $ depthNTree (read x) treeOne

解决方案

Your depthNTree uses 2^n space because you keep the left subtree around through t1 while you're traversing the right subtree. The recursive call on the right subtree should contain no reference to the left, as a necessary condition for incrementally garbage collected traversals.

The naive version works acceptably in this example:

depthNTree n t = go n t where
  go 0 (Tree x _ _) = [x]
  go n (Tree _ l r) = go (n - 1) l ++ go (n - 1) r

Now main with input 24 uses 2 MB space, while the original version used 1820 MB. The optimal solution here is similar as above, except it uses difference lists:

depthNTree n t = go n t [] where
  go 0 (Tree x _ _) = (x:)
  go n (Tree _ l r) = go (n - 1) l . go (n - 1) r

This isn't much faster than the plain list version in many cases, because with tree-depths around 20-30 the left nesting of ++ isn't very costly. The difference becomes more pronounced if we use large tree depths:

print $ sum $ take 10 $ depthNTree 1000000 treeOne

On my computer, this runs in 0.25 secs with difference lists and 1.6 secs with lists.

这篇关于减少深度优先遍历树的空间使用率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！