同一多方法的不同方法之间的递归

Question

我正在编写一个Clojure库来解析Mac OS X的基于XML的属性列表文件.代码工作正常,除非你给它一个大的输入文件,此时你得到java.lang.OutOfMemoryError: Java heap space.

这是一个示例输入文件(小到可以正常工作):

<plist version="1.0">
<dict>
    <key>Integer example</key>
    <integer>5</integer>
    <key>Array example</key>
    <array>
        <integer>2</integer>
        <real>3.14159</real>
    </array>
    <key>Dictionary example</key>
    <dict>
        <key>Number</key>
        <integer>8675309</integer>
    </dict>
</dict>
</plist>

clojure.xml/parse 把它变成:

{:tag :plist, :attrs {:version "1.0"}, :content [
    {:tag :dict, :attrs nil, :content [
        {:tag :key, :attrs nil, :content ["Integer example"]}
        {:tag :integer, :attrs nil, :content ["5"]}
        {:tag :key, :attrs nil, :content ["Array example"]}
        {:tag :array, :attrs nil, :content [
            {:tag :integer, :attrs nil, :content ["2"]}
            {:tag :real, :attrs nil, :content ["3.14159"]}
        ]}
        {:tag :key, :attrs nil, :content ["Dictionary example"]}
        {:tag :dict, :attrs nil, :content [
            {:tag :key, :attrs nil, :content ["Number"]}
            {:tag :integer, :attrs nil, :content ["8675309"]}
        ]}
    ]}
]}

我的代码将其转换为Clojure数据结构

{"Dictionary example" {"Number" 8675309},
 "Array example" [2 3.14159],
 "Integer example" 5}

我的代码的相关部分看起来像

; extract the content contained within e.g. <integer>...</integer>
(defn- first-content
  [c]
  (first (c :content)))

; return a parsed version of the given tag
(defmulti content (fn [c] (c :tag)))

(defmethod content :array
  [c]
  (apply vector (for [item (c :content)] (content item))))

(defmethod content :dict
  [c]
  (apply hash-map (for [item (c :content)] (content item))))

(defmethod content :integer
  [c]
  (Long. (first-content c)))

(defmethod content :key
  [c]
  (first-content c))

(defmethod content :real
  [c]
  (Double. (first-content c)))

; take a java.io.File (or similar) and return the parsed version
(defn parse-plist
  [source]
  (content (first-content (clojure.xml/parse source))))

代码的核心是content函数,一个调用:标记(XML标记的名称)的多方法.我想知道是否有一些不同我应该做的,以使这个递归更好地工作.我试着更换所有三个电话来content用trampoline content,但没有奏效.我是否应该做些什么来使这种相互递归更有效地工作？或者我采取了根本错误的做法？

编辑:顺便说一句,这个代码可以在GitHub上获得,其形式可能更容易玩.

Answer 1

您有来自单个方法的多个（每个子级）递归调用，因此您的代码不是（并且不能没有大量的重组）尾递归。trampoline用于相互尾递归函数。

您的大型 XML 文件有多深、多长？我这么问是因为你得到的是 OoM 而不是 SO。

不管怎样，为了解决你的递归问题（这不太可能是导致异常的问题），你必须遍历你的 XML 数据结构（例如使用 ），xml-zip同时维护一个代表正在构建的结果树的堆栈（向量或列表）。具有讽刺意味的是，XML 数据结构的遍历在某种程度上等同于用于构建该结构的 sax 事件。