optimization - 总结 Clojure 比率很慢

Question

我正在总结 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 秒

(不太精确)的替代方案是将这些值求和为 double :

(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 使用哪种算法来求和比率吗？

Answer 1

让我们看看当您 + 两个 Ratio 时会发生什么，这就是减少过程中每一步发生的情况。我们从the two-arity version of +开始:

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

这将我们带到Numbers.add(Obj, Obj) :

返回 ops(x).combine(ops(y)).add((Number)x, (Number)y);

操作 looks 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 。

您确实需要一个分析器来准确查看成本在哪里。但希望以上内容能提供一些背景信息。