简易树遍历和快速随机节点访问

在下面的Alex Taggart的评论后编辑。简易树遍历和快速随机节点访问

我使用一个拉链来轻松遍历和编辑一棵可以长到数千个节点的树。首次创建时，每个节点都不完整。数据将随机增加/删除，叶节点将被分支替换等。

该树可以是非常不平衡。对节点的快速随机访问也很重要。

一个实现是使用拉链遍历树并创建按键索引的节点的哈希表。不用说上述的将是非常低效的，因为：每个节点的

2份需要创建
任何改变需要将2层的数据结构（树和HashMap）之间被一致地镜像。

简而言之，是否有一种时间/空间高效的方式来将遍历/更新的简便性与拉链结合起来，以及在clojure中快速访问哈希表？

来源

2011-12-25 kliron

拉链不是数据结构，它是遍历和修改数据结构的一种方式。鉴于此，你的问题不太合理。另外，“高效”还没有很好的定义。 – 2011-12-25 22:18:38

“高效”，因为没有同一个东西的多个副本吃掉内存，并且不必为每个编辑更新2个数据结构。 – kliron 2011-12-25 22:41:23

Clojure的数据结构是持久的，并使用结构共享。这意味着像添加，删除或积累操作并不像您描述的那样低效。由于你没有复制已经存在的内容，因此内存成本会很低。

默认情况下Clojure的数据结构是不可变的。因此，除非使用某种引用类型（如Var），否则结构树中的节点将不会自行更新。我不太了解您的具体使用案例，以了解访问节点的最佳方式。一种访问嵌套结构中的节点的方法是get-in function，其中您提供节点的路径以返回其值。

希望这有助于解决您的问题。

来源

2012-12-08 13:28:55

是的，我意识到结构共享和整个不变性的事情。进入最接近我需要做的事情。这确实是一个愚蠢的问题，因为我使用错误的工具来完成这项工作。 – kliron 2012-12-09 13:43:05

只是好奇，你最终使用了什么工具？为什么它更合适？ – 2012-12-10 18:03:59

问题是重构任意大的xml树，需要细粒度控制（在特定位置提取特定属性，并通过在某些条件下按某些属性的值进行排序来重构文档）。使用zippers进行解析/提取是一种一点点矫枉过正。使用XPath/XSLT更合适，性能可以接受。很高兴我在这些方面投入了时间。 – kliron 2012-12-11 18:05:14

简易树遍历和快速随机节点访问

回答

相关问题