Как избежать нехватки памяти кучи при обработке обширных последовательностей в Clojure?

Я пытаюсь сгенерировать последовательность, которая соответствует поиску в ширину очень широкого и глубокого дерева... и у меня возникают проблемы с памятью, когда я захожу слишком далеко по последовательности. Поспрашивав на IRC-канале и посмотрев здесь, причина номер 1 таких проблем — непреднамеренное удержание за голову; но я не вижу, где я это делаю.

Код довольно прост; вот версия, которая отображает проблему:

(def atoms '(a b c))

(defn get-ch [n] (map #(str n %) atoms)) 

(defn add-ch 
  ([] (apply concat (iterate add-ch atoms))) 
  ([n] (mapcat get-ch n)))

(dorun (take 20000000 (add-ch)))

А вот еще одна версия (с которой я начал до получения помощи от #clojure), которая отображает ту же проблему:

(def atoms '(a b c))

(defn get-children [n] (map #(str n %) atoms))

(defn add-layer 
  ([] (add-layer atoms)) 
  ([n] (let [child-nodes (mapcat get-children n) ] 
      (lazy-seq (concat n (add-layer child-nodes))))))

(dorun (take 20000000 (add-layer)))

Оба дают мне «пространство кучи Java OutOfMemoryError». Я запускаю их из REPL в Eclipse/CounterClockwise на Macbook Air.

Я новичок в Clojure, поэтому, после того, как я целый день ломал голову над этим, я надеюсь, что это что-то тривиальное, что я упускаю из виду. Я понимаю, что мог бы увеличить размер кучи, чтобы уменьшить вероятность возникновения проблемы, но последовательности, которые я в конечном итоге хочу обработать, настолько велики, что я не думаю, что это мне поможет.

Я пытался заменить "дубль" (в приведенных выше примерах) на "бросок", чтобы не держаться за голову - это не имеет значения.


sequence jvm memory clojure heap-memory
person Tom Hume    schedule 08.06.2012    source источник
comment
как насчет вашего варианта памяти JVM? ›= Xmx2g?   -  person number23_cn    schedule 08.06.2012
comment
Это помогает сделать проблему менее вероятной, но она все равно возникнет в будущем, не так ли?   -  person Tom Hume    schedule 08.06.2012

Ответы (1)


arrow_upward
2
arrow_downward

Я пропустил дорун. Проблема, похоже, связана с StringBuilder str.

Это работает, если я заменю get-children, как показано ниже:

 (defn get-children [n] (map #(if (seq? n) (conj n %) (conj (list n) %)) atoms))
person Shanmu    schedule 08.06.2012
comment
Когда repl пытается напечатать последовательность, он удерживает голову. Распространенной идиомой было бы дозировать огромную ленивую последовательность и печатать по одному элементу за раз. У меня есть альтернативное решение для этого, которое, кажется, работает - суть заключается в том, чтобы заменить str на conj в списке, а затем вместо прямой оценки (взять 200000...) использовать дозыq и печать. - person Shanmu; 08.06.2012
comment
Пожалуйста, проигнорируйте мой предыдущий комментарий - я пропустил дорун. С альтернативной реализацией get-children, как указано выше, которая избегает str, гарантирует, что эта реализация будет ленивой на всем протяжении. - person Shanmu; 08.06.2012
comment
я говорю удалить неправильный материал. я удалю свой вопрос, и тогда никто не узнает ... (спасибо, что докопались до сути - интересная проблема, и я до сих пор не уверен, что понимаю, почему исправление исправляет ситуацию) - person andrew cooke; 08.06.2012
comment
Боюсь, у меня не работает - я все еще получаю OutOfMemoryError. Я думаю, что проблема здесь не в Clojure, а в алгоритме. Я поддерживаю последовательность записей; каждый раз, когда я снимаю один, я добавляю его дочерние элементы, поэтому последовательность увеличивается на 2 записи. В конце концов, это должно переполнить память. Я подозреваю, что ваша реализация длится дольше, добавляя к существующей последовательности, а не создавая новую строку для каждой записи. - person Tom Hume; 10.06.2012
comment
Том, под каким номером у тебя закончилась память - я пробовал с 200000000, и у меня закончился стек, а не куча - я подозреваю, что это из-за рекурсивного вызова - использование recur также решило бы это. - person Shanmu; 11.06.2012