在大型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的映射。任何: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上提供的Gist)

第二个示例将崩溃(取决于可用内存，可能需要调整级别2项的数量)。对所有级别1项的:content映射引入了一个引用，当循环遍历所有内容项以删除不需要的:Y项时，该引用会导致头部保留问题。

我能够使用来自valid-run之类的数据，将其放入一个可变变量状态，对所有相关节点执行这一操作，然后再将所有数据拼接在一起。但是，我对这种方法非常不满，因为它必须依赖于可更改性，并且必须使用一些非常必要的代码来最终合并数据(例如，遍历列表索引)。

问题

如何以功能性的、声明性的方式实现这一点？理想情况下，我希望避免使用可变状态，也避免过于命令式(例如，使用索引等将集合拼接在一起)。

资源

下面的文章和片段是关于这个问题的一些方面的有趣的阅读：

• Clojure中的XML操作
• 浅谈头部保留的偶发复杂性
• 相关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个不同的对象。而不是返回一个节点，而是返回一个函数，该函数在被调用时生成该节点的副本；这允许它们与原始版本一样很好地组成，只需要在外部级别额外调用一个函数。如果您实际上已经有了不同的对象，正如我所怀疑的那样，您可以在一个实际的应用程序中使用您编写的原始函数。