Đệ quy giữa các phương thức khác nhau của cùng một phương pháp

Question

Tôi đang viết thư viện Clojure để phân tích cú pháp dựa trên XML property list files của Mac OS X. Mã hoạt động tốt trừ khi bạn cung cấp cho nó một tệp đầu vào lớn, tại thời điểm bạn nhận được java.lang.OutOfMemoryError: Java heap space.

Dưới đây là một ví dụ tập tin đầu vào (nhỏ đủ để làm việc tốt):

<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 biến này vào:

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

Mã của tôi biến này vào cấu trúc dữ liệu Clojure

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

Phần có liên quan của mã của tôi trông giống như

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

Thịt mã là chức năng content, một phương thức đa phương tiện gửi đến thẻ: (tên của thẻ XML). Tôi tự hỏi liệu tôi có nên làm gì đó khác để làm cho đệ quy này hoạt động tốt hơn không. Tôi đã thử thay thế cả ba cuộc gọi thành content bằng trampoline content, nhưng điều đó không hiệu quả. Có điều gì lạ mắt tôi nên làm để có được sự đệ quy lẫn nhau này để làm việc hiệu quả hơn? Hay tôi đang sử dụng một cách tiếp cận cơ bản sai?

Chỉnh sửa: Nhân tiện, mã này là available on GitHub, trong đó hình thức có thể dễ dàng hơn để chơi xung quanh.

Answer 1

Bạn có nhiều cuộc gọi đệ quy (một/trẻ em) đệ quy từ một phương pháp duy nhất để mã của bạn không phải (và không thể không có reorg nặng) đệ quy đuôi. trampoline được thiết kế cho các chức năng tương ứng đệ quy.

Mức độ sâu bao nhiêu, tệp XML lớn của bạn trong bao lâu? Tôi hỏi vì bạn đang nhận được OoM chứ không phải SO.

Dù sao, để giải quyết vấn đề đệ quy của bạn (không phải là nguyên nhân gây ra ngoại lệ), bạn phải đi xuống cơ sở dữ liệu XML của mình (ví dụ: xml-zip) trong khi duy trì ngăn xếp (vectơ hoặc danh sách) đại diện cho cây kết quả của bạn xây dựng. Thật mỉa mai là sự truyền tải của cơ sở dữ liệu XML tương đương với các sự kiện sax được sử dụng để xây dựng cấu trúc.

Answer 2

Đệ quy nặng sẽ gây ra StackOverflowException, không phải là OutOfMemoryError. Ngoài ra đệ quy không có vẻ rất sâu ở đây (chỉ có 3 cấp độ theo tệp XML trong ví dụ của bạn).

Tôi đoán là, OutOfMemoryError đang được ném vì cấu trúc dữ liệu các tệp XML lớn của bạn đang được phân tích cú pháp quá lớn để vừa với heap JVM. Bạn có thể thử tăng kích thước heap bằng cách sử dụng các tùy chọn -Xms và -Xmx. Tuy nhiên, cách chính xác để phân tích các tệp XML lớn là sử dụng các sự kiện SAX thay vì xây dựng một cây (cấu trúc dữ liệu DOM hoặc Clojure).