Recursión entre diferentes métodos del mismo método múltiple

Question

Estoy escribiendo una biblioteca Clojure para analizar XML basado en Mac OS X property list files. El código funciona bien a menos que le proporcione un gran archivo de entrada, en cuyo caso obtiene java.lang.OutOfMemoryError: Java heap space.

Aquí hay un ejemplo de archivo de entrada (lo suficientemente pequeño para funcionar bien):

<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 convierte esto en:

{: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"]} 
     ]} 
    ]} 
]} 

Mi código se convierte esto en la estructura de datos Clojure

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

La parte relevante de mi código se parece a

; 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)))) 

La carne del código es la función content, un multimethod que despacha en el: etiqueta (el nombre de la etiqueta XML). Me pregunto si hay algo diferente que debería hacer para que esta recursión funcione mejor. Traté de reemplazar las tres llamadas a content con trampoline content, pero eso no funcionó. ¿Hay algo elegante que deba hacer para que esta recursión mutua funcione de manera más eficiente? ¿O estoy tomando un enfoque fundamentalmente erróneo?

Edit: Por cierto, este código es available on GitHub, en la que puede ser más fácil jugar con.

Answer 1

Tiene varias llamadas recursivas (una por niño) desde un solo método, por lo que su código no es (y no puede ser sin una pesada reorg) recursivo de cola. trampoline está destinado a mutuo recursivo de cola funciones.

¿Qué tan profundo, por cuánto tiempo es su gran archivo XML? Te pregunto porque estás obteniendo un OoM no un SO.

De todos modos, para resolver su problema de recursión (que es poco probable que cause la excepción) debe bajar la estructura de datos XML (por ejemplo, xml-zip) mientras mantiene una pila (vector o lista) representando el árbol de resultados construcción. Es irónico que el recorrido de la estructura de datos XML sea en cierto modo equivalente a los eventos sax que se utilizaron para construir la estructura.

Answer 2

La recursión pesada causará un StackOverflowException, no un OutOfMemoryError. Además, la recursión no parece ser muy profunda aquí (solo 3 niveles según el archivo XML en su ejemplo).

Supongo que el OutOfMemoryError se está lanzando porque la estructura de datos en la que se analizan sus archivos XML grandes es demasiado grande para caber en el montón de JVM. Puede intentar aumentar el tamaño del almacenamiento dinámico utilizando las opciones -Xms y -Xmx. Sin embargo, la forma correcta de analizar grandes archivos XML es usar eventos SAX en lugar de construir un árbol (estructura de datos DOM o Clojure).