在集更新或大数目计算上的闭包性能

Question

我试图用筛子算法来总结Euler项目问题的素数。我使用一个可变集来存储非素数的数字，并使用'dosync‘和’整流‘来更新该集合(否则，如果它是不可变的，我就会耗尽内存)。性能大约是线性的，直到120万素数，但在150万(7秒对64秒)的性能是可怕的。知道我做错什么了吗？我的猜测是，数字可能变得太大，或者更新可变集的效率很低。

(defn mark-multiples [not-prime-set multiple prime-max]
  (loop [ counter (long 2) 
      product (* counter multiple)]
    (if (> product prime-max) not-prime-set
      (do
        (dosync (commute not-prime-set conj product))
        (recur  (inc counter) (* (inc counter) multiple))))))


(defn sieve-summation [prime-max]
  (def not-prime-set (ref #{ (long 1) }) )
  (loop [counter (long 2)
     summation (long 0)]
    (if (> counter prime-max) summation
      (if (not (contains? @not-prime-set counter)) 
        (do 
          (mark-multiples not-prime-set counter prime-max)
          (recur  (inc counter) (+ summation counter)))
        (recur (inc counter) summation)))))

=> (时间(筛-和100000))“经过的时间: 496.673毫秒”454396537

=> (时间(筛-和150000))“经过的时间: 763.333毫秒”986017447

=> (时间(筛-和1000000))“经过的时间: 6037.926毫秒”37550402023

=> (时间(筛-和1100000))“经过的时间: 6904.385毫秒”45125753695

=> (时间(筛-和1200000))“经过的时间: 7321.299毫秒”53433406131

=> (时间(筛-和1500000))“经过的时间: 64995.216毫秒”82074443256

-编辑

谢谢韦伯，好建议！您的代码有点慢，所以为了加快速度，我必须在一开始就使非素数集瞬态化，现在它运行得更快(大约8次)。我仍然会出现内存不足的错误，所以我将尝试找出如何增加jvm上的堆大小，看看是否修复了它。我正在Mac上的Eclipse上运行Clojure，而且我对Clojure和Mac还很陌生。

我想看看如何进一步重构程序(保持相同的逻辑)，使之在Clojure中更加优雅。再次感谢。

(defn mark-multiples2 [not-prime-set prime prime-max]
  (loop [multiple (* 2 prime) nps not-prime-set ]
    (if (> multiple prime-max) 
      nps
      (recur (+ multiple prime) (conj! nps multiple)))))


(defn sieve-summation2 [prime-max]
  (loop [counter 2, summation 0, not-prime-set (transient #{1})]
    (if (> counter prime-max) 
      summation
      (if (not-prime-set counter) 
        (recur (inc counter) summation not-prime-set)
        (recur (inc counter) 
           (+ summation counter) 
           (mark-multiples2 not-prime-set counter prime-max))))))

=> (时间(筛-和2 100000))“经过的时间: 124.781毫秒”454396537

=> (时间(筛-和100000))“经过的时间: 876.744毫秒”454396537

Answer 1

在Clojure中有更好和更优雅的方法来解决这个问题，但这不是问题的重点。

使用一个引用类型--不管它是一个参考文献，还是一个原子--在这里对你没有任何帮助。你仍然在创造同样多的垃圾。您只需将可变存储位置的内容从一个不可变的数据结构交换到另一个。我不知道是什么导致了你的时间激增，但有一种可能是你触发了一个很长的垃圾收集周期。

您想在这里使用的是瞬变。在不过多更改代码的情况下，下面的内容应该是一个显著的加速。

(defn mark-multiples [not-prime-set multiple prime-max]
  (loop [m (* 2 multiple), nps (transient not-prime-set)]
    (if (> m prime-max) 
      (persistent! nps)
      (recur (+ m multiple) (conj! nps m)))))


(defn sieve-summation [prime-max]
  (loop [counter 2, summation 0, not-prime-set #{1}]
    (if (> counter prime-max) 
      summation
      (if (contains? not-prime-set counter) 
        (recur (inc counter) summation not-prime-set)
        (recur (inc counter) 
               (+ summation counter) 
               (mark-multiples not-prime-set counter prime-max))))))

这是相同的算法，以更惯用的方式：

(defn mark [s n m]
  (into s (range (* 2 n) m n)))

(defn prime-sum [m]
  (let [step (fn [[a s] n] 
               (if (s n)
                 [a s] 
                 [(+ a n) (mark s n m)]))]
  (first (reduce step [0 #{}] (range 2 m)))))

从这里开始，您可能开始攻击算法固有的内存问题--您正在存储所有的非素数，而您只需要在任何给定的点存储下一个非素数。有关该想法的漂亮实现，请参阅Christophe的每个人都喜欢埃拉托斯提尼的筛子条目。

Answer 2

我使用了Eclipse的逆时针插件，它使用的是Clojure 1.5，我相信是因为我有JDK1.6。我升级到JDK1.7，并更新了project.clj，使其使用Clojure 1.6.0，并且内存/速度问题都不是问题。谢谢你的建议。