memory - Clojure 惯用的内存高效循环

Question

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

(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! 占用大量内存空间，对吗？

---

两个奖励问题:

1. 如果我删除 println 行(当然还有 do)，代码将运行得很快，但 min-dist 不会更新，就好像循环没有被执行一样。这是为什么？

2. 使用 lein run 运行时会看到相同的行为，即使其中有 println。为什么？

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

Answer 1

您的子问题 #1 是关键。

for 生成一个惰性 列表，因此除非实际读取结果，否则不会完成任何工作。如果你想对结果进行评估，你可以将整个事情包装在对 dorun 的调用中，它遍历列表而不将整个事情保存在内存中。我通常将这种情况称为“被懒虫咬伤”，大多数 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}}

这使最小距离中的原始值保持不变。