Clojure 惯用的内存高效循环

Question

我正在 Clojure 中实现一个简单的算法，该算法坚持要耗尽内存，即使 :jvm-opts ["-Xmx4G"] 设置在我的 project.clj 上也是如此。假设以下数据结构：

(def inf Double/POSITIVE_INFINITY)
(def min-dist (atom {:1 {:1 0 :2 4} :2 {:1 4 :2 0 :3 5} :3 {:2 5 :3 0}}))
(def vertexes [:1 :2 :3])

以下将运行在更大的输入 (|vertexes| = 100) 上内存不足：

(for [k vertexes i vertexes j vertexes]
  (do
    (println " " i " " j " "k)
    (let [s (+ (get-in @min-dist [i k] inf) (get-in @min-dist [k j] inf))]
      (if (> (get-in @min-dist [i j] inf) s) (swap! min-dist assoc-in [i j] s)))))

输出：

OutOfMemoryError Java heap space  java.util.Arrays.copyOf (Arrays.java:2367)

我很确定这是一个 reduce 选项，可以使一切变得干净和快速，但我就是找不到它。看起来 swap! 占用大量内存 space，对吗？

两个奖励问题：

如果我删除 println 行（当然还有 do），代码会运行快，但 min-dist 不会更新，就好像循环没有被执行一样。为什么呢？
在运行 lein run 时会出现相同的行为，即使其中包含 println。为什么？

任何对新 Clojurist 的帮助都将不胜感激。 =)

Answer 1

你的子问题 #1 是关键。

for 生成一个 lazy 列表，因此除非实际读取结果，否则不会完成任何工作。如果你想对结果进行评估，你可以将整个事情包装在对 dorun 的调用中，它遍历列表而不将整个事情保存在内存中。我通常将这种情况称为 "being bitten by the lazy bug"，大多数 Clojurians 发生这种情况的频率比他们表现的要高 ;-)

user> @min-dist
{:1 {:1 0, :2 4}, :2 {:1 4, :2 0, :3 5}, :3 {:2 5, :3 0}}
user> (time
        (dorun (for [k vertexes i vertexes j vertexes]
                 (let [s (+ (get-in @min-dist [i k] inf) (get-in @min-dist [k j] inf))]
                  (if (> (get-in @min-dist [i j] inf) s) (swap! min-dist assoc-in [i j] s))))))
"Elapsed time: 4.272336 msecs"
nil
user> @min-dist
{:1 {:1 0, :2 4, :3 9}, :2 {:1 4, :2 0, :3 5}, :3 {:2 5, :3 0, :1 9}}

删除 println 是一个好主意，因为对于表达式的 100 个顶点的列表（从其他语言中的单词的意义上来说，它不是一个循环）将会运行 100 万次（100 * 100 * 100), 所以打印出来需要一段时间。

而且因为我很喜欢加分：这里使用的是 reduce:

user> (def min-dist {:1 {:1 0 :2 4} :2 {:1 4 :2 0 :3 5} :3 {:2 5 :3 0}})
#'user/min-dist
user> (time
       (->> (for [k vertexes i vertexes j vertexes]     ;; start by making a sequence of all the combinatioins of indexes
              [i j k])
            (reduce
             (fn [result [i j k]]                       ;; the reducer function takes the result so far and either modifies it 
               (let [s (+ (get-in result [i k] inf)     ;; or passes it through unchanged.
                          (get-in result [k j] inf))]
                 (if (> (get-in result [i j] inf) s)    ;; depending on this if expression here.
                   (assoc-in result [i j] s)            ;; pass on the changed value
                   result)))                            ;; pass on the original value, unchanged
             min-dist)))                                ;; this argument is the initial value.
                                                        ;; the ->> expression places the result of the for expression here. (as the last argument)
"Elapsed time: 5.099 msecs"
{:1 {:1 0, :2 4, :3 9}, :2 {:1 4, :2 0, :3 5}, :3 {:2 5, :3 0, :1 9}}

这会保留最小距离中的原始值。

Clojure 惯用的内存高效循环

Clojure idiomatic and memory-efficient loop

lisp

memory

idioms

clojure