0

我已经开始在 clojure 中解决项目欧拉问题作为学习语言的一种方式。在为问题 10 实施埃拉托色尼筛时，我最初遇到的性能极差，这似乎源于绕过 a boolean-array。我发现我可以通过添加类型提示或重新排序代码来解决这个问题，以便帮助函数可以boolean-array直接从父范围访问，但我不明白为什么需要它。(type sieve)在任何辅助函数中都返回[Z，所以看起来 clojure 已经知道它是一个boolean-array. 谁能解释一下为什么这里需要类型提示？

为代码墙道歉，我不知道在说明问题的同时可以删除哪些部分。

;;; returns a vector containing all primes smaller than limit
(defn gen-primes-orig [limit]
  (defn next-unmarked [sieve v]
    (loop [i (inc v)]
      (cond
       (>= i limit) nil
       (false? (aget sieve i)) i
       :true (recur (inc i)))))

  (defn mark-powers-of! [sieve v]
    (loop [i (+ v v)]
      (if (>= i limit) sieve
          (do
            (aset-boolean sieve i true)
            (recur (+ i v))))))

  (defn collect-primes [sieve]
    (loop [primes []
           i 0]
      (cond
       (>= i limit) primes
       (false? (aget sieve i)) (recur (conj primes i) (inc i))
       :true (recur primes (inc i)))))

  (let [sieve (boolean-array limit false)]
    ;; 0 and 1 are not primes
    (aset-boolean sieve 0 true)
    (aset-boolean sieve 1 true)

    (loop [v 0]
      (let [v (next-unmarked sieve v)]
        (if (nil? v) (collect-primes sieve)
            (do
              (mark-powers-of! sieve v)
              (recur v)))))))

(defn gen-primes-hint [limit]
  (defn next-unmarked [^booleans sieve v]
    ;; same body as in gen-primes-orig
    )
  (defn mark-powers-of! [^booleans sieve v]
    ;; same body as in gen-primes-orig
    )
  (defn collect-primes [^booleans sieve]
    ;; same body as in gen-primes-orig
    )
  (let [sieve (boolean-array limit false)]
    ;; same body as in gen-primes-orig
    ))

(defn gen-primes-letfn [limit]
  (let [sieve (boolean-array limit false)]
    ;; 0 and 1 are not primes
    (aset-boolean sieve 0 true)
    (aset-boolean sieve 1 true)

    (letfn [(next-unmarked [v]
              ;; same body as in gen-primes-orig
              )
            (mark-powers-of! [v]
              ;; same body as in gen-primes-orig
              )
            (collect-primes []
              ;; same body as in gen-primes-orig
              )]
      (loop [v 0]
        (let [v (next-unmarked v)]
          (if (nil? v) (collect-primes)
              (do
                (mark-powers-of! v)
                (recur v))))))))

这是三种混合物中每种混合物的运行时间。（结果已被删除。所有混合都会产生相同的正确结果。）

user> (time (apply + (gen-primes-orig  2000000)))
"Elapsed time: 108001.047327 msecs"
user> (time (apply + (gen-primes-hint  2000000)))
"Elapsed time: 2599.091978 msecs"
user> (time (apply + (gen-primes-letfn 2000000)))
"Elapsed time: 2768.060355 msecs"
4

1 回答 1

0

type函数.getClass对传递的对象使用方法来返回对象的类。即它使用运行时反射来确定对象的类。其中类型提示有助于 clojure 编译器通过避免生成基于反射的代码来生成高效的代码。基本上type与帮助 clojure 编译器发出高效代码的类型提示无关。

于 2013-10-07T04:33:47.953 回答