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!需要大量的内存空间,对吗？

---

两个奖金问题:

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个顶点的列表用于表达(它不是一个循环,因为word在其他语言中的意义)将运行100万次(100*100*100),所以打印它出去需要一段时间.

因为我是奖励积分的傻瓜:这里使用的是:

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}}

这使得min-dist中的原始值保持不变.