总结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 ms
• n = 10 ^ 6 ...... 3.4 s
• 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 ms
• n = 10 ^ 6 ...... 350 ms
• n = 10 ^ 7 ...... 3.4 s

为什么加总比率要慢得多？我猜测它与找到Ratios的分母的最小公倍数有关,但是有没有人知道Clojure用什么算法来比较Ratios？

Answer 1

让我们来看看你们+两个人发生的事情Ratio,这就是减少中每一步所发生的事情.我们从+的两个版本开始:

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

这需要我们Numbers.add(Obj, Obj):

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

ops 查看第一个操作数的类并找到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)

你可以看到如何实现多重 ; 它本身并不是微不足道的,你可以自己检查其他人.

果然,除法函数包括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函数创建两个新MutableBigInteger对象.

从计算上来说,它是昂贵的,正如你从上面所有可以看到的那样.但是,不要打折额外附带对象创建的成本(gcd如上所述),因为我们涉及非缓存内存访问通常会更加昂贵.

该double转换是不是免费的,FWIW,因为它涉及到两个新建的一个部门BigDecimal小号.

您真的需要一个分析器来确切了解成本的位置.但希望上面给出了一点背景.