用Clojure寫的階乘函數的低性能

Question

我是Clojure的新手。在實驗中，我寫了函數來計算n!。我的Clojure代碼如下：

(defn factorial 
    [n] 
    (reduce * (biginteger 1) (range 1 (inc n)))) 

然後我在repl中運行以下代碼。

(time (factorial 100)) 

這是結果：

"Elapsed time: 0.50832 msecs" 
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000N 

我然後創建Ruby中類似的解決方案：

def factorial(n) 
    start = Time.now.to_f 
    (2..n).inject(1) { |p, f| p * f } 
    finish = Time.now.to_f 
    time_taken = finish - start 
    puts "It took: #{(time_taken * 1000)} msecs" 
end 

的與IRB我跑factorial(100) ，導致：

It took: 0.06556510925292969 msecs 
=> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 

雖然我已經看到多數證據表明Clojure應該具有卓越的性能，但Ruby版本的性能似乎要明顯更高。有什麼我誤解或我的Clojure解決方案的某些元素會減慢速度？

Answer 1

米羅基準是經常誤導，在總體上是相當難以得到正確的事：

您可以通過類型暗示參數n獲得進一步加快。讓Clojure中相當接近（我發現最簡單的方法是嚴格的標準庫（感謝雨果！）。如果我開始一個醜陋的版本，通過簡單的循環，我得到約3納秒計算階乘。

user> (defn loopy-fact [x] 
     (loop [y x 
       answer-so-far 1] 
      (if (pos? y) 
      (recur (dec y) (*' answer-so-far y)) 
      answer-so-far))) 
#'user/loopy-fact 

user> (loopy-fact 100) 
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000N 

然後讓我們的基準是：

user> (criterium.core/bench #(loopy-fact 100)) 
WARNING: Final GC required 11.10521514596218 % of runtime 
WARNING: Final GC required 1.069604210579865 % of runtime 
Evaluation count : 12632130300 in 60 samples of 210535505 calls. 
      Execution time mean : 2.978360 ns 
    Execution time std-deviation : 0.116043 ns 
    Execution time lower quantile : 2.874266 ns (2.5%) 
    Execution time upper quantile : 3.243399 ns (97.5%) 
        Overhead used : 1.844334 ns 

Found 4 outliers in 60 samples (6.6667 %) 
    low-severe 2 (3.3333 %) 
    low-mild  2 (3.3333 %) 
Variance from outliers : 25.4468 % Variance is moderately inflated by outliers 

如果我們再使代碼看起來使用Clojure的正常風格更好，地圖和減少，並使其快速不遺餘力。

user> (defn mapy-fact [x] 
     (reduce *' (range 1 (inc x))) 
#'user/mapy-fact 

user> (mapy-fact 100) 
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000N 

現在，讓我們看看如何來比較：

user> (criterium.core/bench #(mapy-fact 100)) 
Evaluation count : 8674569060 in 60 samples of 144576151 calls. 
      Execution time mean : 5.208031 ns 
    Execution time std-deviation : 0.265287 ns 
    Execution time lower quantile : 5.032058 ns (2.5%) 
    Execution time upper quantile : 5.833466 ns (97.5%) 
        Overhead used : 1.844334 ns 

Found 4 outliers in 60 samples (6.6667 %) 
    low-severe 1 (1.6667 %) 
    low-mild  3 (5.0000 %) 
Variance from outliers : 36.8585 % Variance is moderately inflated by outliers 

這是一個慢一點，但只有兩納秒慢。

這比它在你的測試中看起來好多了，因爲Criterium運行足夠多的時間讓JVM的Hotspot編譯器編譯並內聯所有部分。這證明了爲什麼微基準可能會在JVM上造成誤導。你應該幾乎可以肯定這種情況下的標準。

PS：*'是「自動推進」乘法opperator，反而會促進這類型大整數或大小數按要求

Answer 2

BigInteger來自java，而BigInt在Clojure的核心中實現。馬上就會有一些與interopability相關的費用。

---

此外，BigInt被表示爲任一a long or a BigInteger。只要有可能，the long is used。但是，如果有任何操作使其產生overflow，則產生新的BigIntwill use it's BigInteger。 Java的long映射到本地體系結構的實現，因此顯着更快。這與Ruby在Fixnum和Bignum之間的魔術轉換類似。

由於您幾乎全部使用小數字（1到100和大量中間產品），因此您可以獲得顯着的性能提升。

Answer 3

繼@ndn's answer：

(defn factorial [^long n] 
    (reduce * (bigint 1) (range 1 (inc n))))