Clojure计划的执行时间

Question

这是一个clojure程序,用于从文件中读取整数并计算反转次数,即在序列中较小的数字之前出现较大数字的次数.它实现了一个O(n ^ 2)算法,并且在大小为100,000的输入上运行大约需要30分钟.

(defn count-inversions
  [file]
  (let [int-list (vec (map #(Integer/parseInt %)
                           (clojure.string/split (slurp file) #"\r\n")))]
    (loop [c 0
           t-list int-list]
      (let [size (count t-list)]
        (if (empty? t-list)
         c
         (recur (reduce #(if (< %2 (first t-list)) (inc %1) %1) c (subvec t-list 1 (dec  size)))
                (subvec t-list 1 (dec size))))))))

在Java中实现时,此算法只需几秒钟即可完成.为什么这么大的差异？

Answer 1

对我来说看起来可能很慢的事情(虽然你必须要确定基准以确保....)

• 你的所有数字都是盒装的.这将使你做的任何事情比使用原语慢得多.它不是非常惯用,但如果你想获得这种加速,你可以在Clojure中使用原始数组.
• 减少子目录当前会创建大量临时对象.有一个补丁正在解决这个问题(http://dev.clojure.org/jira/browse/CLJ-894),但你可能需要等待Clojure 1.4或1.5.
• 它有助于(set! *unchecked-math* true)提高整数运算的性能(显然,如果可能发生溢出,您需要更加小心)

如果我想让它在Clojure中运行得非常快,我可能会使用原始数组并使用原始索引进行循环:

(set! *unchecked-math* true)

(defn count-inversions [coll]
     (let [^ints integers (int-array coll)
           size (long (count integers))]
       (loop [c (long 0)
              i (long 0)]
         (if (>= i size)
           c
           (recur
             (loop [c (long c)
                    v (aget integers i)
                    j (inc i)]
               (if (>= j size)
                 c
                 (recur (long (if (> v (aget integers j)) (inc c) c)) v (inc j))))
             (inc i))))))

(time (count-inversions (for [i (range 100000)] (rand-int 100))))
"Elapsed time: 16036.651863 msecs"

即此代码在我的机器上计算大约16秒内100,000个整数的所有反转(使用Clojure 1.3)