2011-02-01 91 views
5

我正在編寫一個Clojure庫來解析Mac OS X的基於XML的property list files。代碼工作正常,除非你給它一個大的輸入文件,在這一點你得到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函數,該函數是一個派生在:tag(XML標記的名稱)上的多方法。我想知道是否有什麼不同,我應該做的,以使這種遞歸更好。我試圖用trampoline content替換所有三個電話content,但那不起作用。我應該怎麼做才能讓這種相互遞歸更高效地工作?或者我採取了一個根本錯誤的方法?

編輯:順便說一句,這個代碼是available on GitHub,在這種形式可能更容易玩弄。

回答

4

你有多個(每個孩子一個)來自單一方法的遞歸調用,所以你的代碼不是(並且不能沒有重度reorg)尾遞歸。 trampoline旨在相互作用尾遞歸函數。

你的大型XML文件有多深?我在問,因爲你得到的是一個OOM不是一個SO。

無論如何,爲了解決你的遞歸問題(這不太可能是引發異常的問題),你必須走下你的XML數據結構(例如用xml-zip),同時維護代表結果樹的棧(向量或列表)施工。 具有諷刺意味的是,XML數據結構的遍歷與用於構建結構的sax事件有些相同。

+0

我還沒有聽說過xml-zip,但我會研究它。謝謝! – bdesham 2011-02-03 19:18:36

4

重遞歸會導致StackOverflowException,而不是OutOfMemoryError。此外,遞歸在這裏似乎並不深(根據您的示例中的XML文件,只有3個級別)。

我的猜測是,OutOfMemoryError正在被拋出,因爲您的大型XML文件被解析到的數據結構太大,無法放入JVM堆。您可以嘗試使用-Xms-Xmx選項增加堆大小。但是,解析大型XML文件的正確方法是使用SAX事件而不是構建樹(DOM或Clojure數據結構)。

+0

實際的文件當然要大得多,但在例子中,遞歸仍然不是那麼深。我會研究SAX事件和xml-zip,看看這個庫最有意義。謝謝! – bdesham 2011-02-03 19:19:48