求和Clojure的比率是慢

我總結比率一長串Clojure中，是這樣的：求和Clojure的比率是慢

(defn sum-ratios 
    [n] 
    (reduce 
    (fn [total ind] 
     (+ 
     total 
     (/ 
      (inc (rand-int 100)) 
      (inc (rand-int 100))))) 
    (range 0 n)))

各種n中的運行時間是：

N = 10^4 .. .... 41毫秒
N = 10^6 3.4 ......小號
N = 10^7 ...... 36號

的（不太精確）的選擇是作爲加倍來概括這些值：

(defn sum-doubles 
    [n] 
    (reduce 
    (fn [total ind] 
     (+ 
     total 
     (double 
      (/ 
      (inc (rand-int 100)) 
      (inc (rand-int 100)))))) 
    (range 0 n)))

此版本的運行時間：

N = 10^4 ...... 8.8毫秒
N = 10^6 ...... 350毫秒
N = 10^7 ...... 3.4小號

爲什麼總和比率顯着較慢？我猜測它與查找比率的最小公倍數有關，但是有人明確知道Clojure使用哪種算法來總和比率？

來源

2017-06-26 bslawski

另外，如果您想使用雙打，請在劃分之前進行。用一個int和一個double來重劃一個比一個必須計算一個比率的分區更加便宜的分區，然後把它轉換成double。 – NielsK

讓我們來看看當你+兩個Ratio s發生什麼，這是減少每一步發生的情況。我們開始在the two-arity version of +：

([x y] (. clojure.lang.Numbers (add x y)))

這需要我們Numbers.add(Obj, Obj)：

return ops(x).combine(ops(y)).add((Number)x, (Number)y);

opslooks at the class of the first operand，並會找到RatioOps。這導致RatioOps.add功能：

final public Number add(Number x, Number y){ 
    Ratio rx = toRatio(x); 
    Ratio ry = toRatio(y); 
    Number ret = divide(ry.numerator.multiply(rx.denominator) 
      .add(rx.numerator.multiply(ry.denominator)) 
      , ry.denominator.multiply(rx.denominator)); 
    return normalizeRet(ret, x, y); 
}

所以這裏是你的算法。這裏有 BigInteger操作（三級乘法，一個加，一個分）：

(yn*xd + xn*yd)/(xd*yd)

你可以看到如何multiply實施;它本身並不是微不足道的，你可以爲自己檢查其他人。

果然，divide function包括尋找兩個數字之間的gcd所以可以降低：

static public Number divide(BigInteger n, BigInteger d){ 
    if(d.equals(BigInteger.ZERO)) 
     throw new ArithmeticException("Divide by zero"); 
    BigInteger gcd = n.gcd(d); 
    if(gcd.equals(BigInteger.ZERO)) 
     return BigInt.ZERO; 
    n = n.divide(gcd); 
    d = d.divide(gcd); 
    ... 
}

的gcd function創建兩個新的MutableBigInteger對象。

從計算上看，它很昂貴，正如你從上面所看到的那樣。但是，不要打折附加對象創建的成本（如上面的gcd），因爲這通常更昂貴，因爲我們涉及非緩存內存訪問。

double轉換不是免費的，FWIW，爲it involves a division of two newly-created BigDecimals。

您確實需要一個分析器才能看到正好是其中的代價是。但希望以上給出一點背景。

來源

2017-06-27 02:24:27 Josh

它的確如此。謝謝！ – bslawski

求和Clojure的比率是慢

回答

相關問題