从大型Clojure树结构中的延迟序列中删除元素,避免头部保留

Question

问题描述

为了在Clojure中处理大型数据结构,惰性序列提供了一种很好的惯用方法.但是,需要谨慎以避免头部滞留.

我很难处理像这样的大型树结构:

                 R                                         Root
       __________|____________________
       A                   B         C, D, E, ...          1st Level Children
_______|_______     _______|_______
X Y Y ... Y X Y     X Y Y ... Y X Y                        2nd Level Children

• 所有节点都是带密钥的地图:content.any的值:content是该节点的所有子节点的延迟seq.
• 整棵树不适合记忆.Y第二级有太多物品.
• 除Y项目之外的整个树都适合记忆.

在处理完树之后,我想得到一个新树,其中Y删除了所有节点:

           R
     ______|__________________
     A             B         C, D, E, ...
_____|___     _____|___
X X ... X     X X ... X

示例代码和进一步说明

;; Generating example data
;;;;;;;;;;;;;;;;;;;;;;;;;;

(defn root [content]
  {:tag :root :content content})

(defn lazy-elements [n tag content]
  (lazy-seq (repeat n {:tag tag :content content})))

(defn level-1 [content]
  (lazy-elements 3 :A content))

(defn level-2 [n]
  (concat (lazy-elements 10 :X '(:leaf))
          (lazy-elements n :Y '(:leaf))))

(defn remove-nodes [node]
  (remove #(= (:tag %) :Y) node))


;; Illustrating usage
;;;;;;;;;;;;;;;;;;;;;

;; runs and runs and runs... and eventually returns correctly
(defn valid-run []
  (->> (root (level-1 (level-2 1e8)))
       :content
       first
       :content
       remove-nodes))

;; Does not terminate properly, runs out of memory
(defn invalid-run []
  (->> (root (level-1 (level-2 1e8)))
       :content
       (map :content)       ; source of head retention
       (map remove-nodes)))

(GitHub上提供的要点)

第二个示例将崩溃(取决于可用内存,可能需要调整二级项目的数量).:content对所有1级项目进行映射会 引入一个引用,该引用会在循环浏览所有内容项时导致头部保留问题,以删除不需要的:Y项目.

我能够使用类似的数据valid-run,将其放入var保持可变状态,为所有相关节点执行此操作,然后再将所有数据拼接在一起.但我对这种方法非常不满意,因为必须依赖于可变性并且必须使用一些非常强制性的代码来最终合并数据(例如,通过列表的索引运行).

题

如何以功能性的声明式方式实现这一目标？理想情况下,我希望避免使用可变状态以及过于强制(例如使用索引等将集合拼接在一起).

资源

以下文章和片段是有关该问题方面的有趣读物:

• Clojure中的XML操作
• Rich Hickey关于头部保留的偶然复杂性
• 相关的Clojure文档
• 简而言之,保持头部保持困难

更多背景

最终我需要这个来处理大型XML文件.大意味着大于1GB并将其解析为树将无法在可用内存上运行.从那个XML我想把一些元素放到存储桶A(比如说一个数据库表)中,把所有其余的XML树放到存储桶B中.当然应该为提取的子树保留XML结构.

我可以将XML作为事件流处理,而不是将XML解析为树,例如通过data.xml/source-seq.但是,这意味着丢失XML树语义.会工作,但不是很漂亮.但也许还有其他方法来处理XML.

Answer 1

问题是您的level-2节点都具有指向相同内存中惰性序列的指针，然后您多次映射该序列。valid-run如果您只处理第一个和第二个节点，您也会遇到同样的问题- 节点的数量并不重要，因为您用任何两个节点都会破坏堆。在实际的应用程序中，您从数据库或文件或其他内容中读取这些节点，它们将指向不同的对象，您可以轮流延迟处理这些对象。

如果生成更具代表性的示例数据（即相同的数据但没有结构共享），则可以在处理每个节点时对其进行 GC：

(defn root' [content]
  (fn []
    {:tag :root :content (content)}))

(defn lazy-elements' [n tag content]
  (repeatedly n (fn [] {:tag tag :content (content)})))

(defn level-1' [content]
  (fn []
    (lazy-elements' 3 :A content)))

(defn level-2' [n]
  (fn []
    (concat (lazy-elements' 10 :X (fn [] '(:leaf)))
            (lazy-elements' n :Y (fn [] '(:leaf))))))

(defn remove-nodes [node]
  (remove #(= (:tag %) :Y) node))

(defn run []
  (let [root-builder (root' (level-1' (level-2' 1e8)))]
    (->> (root-builder)
         :content
         (map :content)       
         (map remove-nodes))))

user> (pprint (run))
(({:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)})
 ({:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)})
 ({:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}
  {:tag :X, :content (:leaf)}))

由于我们只是生成示例内容，因此我已经调整了所有节点构建器以采用他们应该调用 N 次以获得 N 个不同对象的函数，而不是他们应该存储 N 个副本的对象。它们返回的不是一个节点，而是一个函数，该函数在调用时会生成该节点的副本；这使得它们能够像原始版本一样完美地组合，只需要在外层进行一个额外的函数调用。如果您实际上已经有了不同的对象，就像我怀疑您在实际应用程序中那样，您可以只使用编写的原始函数。