簡易樹遍歷和快速隨機節點訪問

在下面的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

簡易樹遍歷和快速隨機節點訪問

回答

相關問題