Рекурсия между разными методами одного и того же мультиметода

Question

Я пишу библиотеку Clojure для анализа XML-файлов списка свойств Mac OS X . Код работает нормально, если вы не предоставите ему большой входной файл, после чего вы получите 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 в некоторой степени эквивалентен событиям саксофона, которые использовались для построения структуры.

Answer 2

Тяжелая рекурсия вызовет StackOverflowException, а не OutOfMemoryError.Также рекурсия здесь не кажется слишком глубокой (только 3 уровня в соответствии с файлом XML в вашем примере).

Я думаю, OutOfMemoryError выбрасывается, потому что структура данных ваших больших файлов XMLслишком большие, чтобы поместиться в кучу JVM.Вы можете попробовать увеличить размер кучи, используя опции -Xms и -Xmx.Однако правильный способ анализа огромных XML-файлов - использовать события SAX, а не строить дерево (структура данных DOM или Clojure).