Chỉ số Tổng kết Clojure là chậm

Question

Tôi đang tổng hợp một danh sách dài các tỷ lệ trong Clojure, một cái gì đó như:

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

Thời gian chạy cho nhiều n là:

• n = 10^4 .. .... 41 ms
• n = 10^6 ...... 3.4 s
• n = 10^7 ...... 36 s

The (ít chính xác) thay thế là tổng hợp các giá trị như tăng gấp đôi:

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

Thời gian chạy cho phiên bản này là:

• n = 10^4 ...... 8.8 ms
• n = 10^6 ...... 350 ms
• n = 10^7 ...... 3.4 s

Tại sao tỷ lệ tổng hợp lại chậm hơn đáng kể? Tôi đoán rằng nó đã làm với việc tìm kiếm nhiều phổ biến nhất của các mẫu số của tỷ lệ được tổng kết, nhưng không ai biết cụ thể mà thuật toán Clojure sử dụng để tổng tỷ lệ?

Answer 1

Hãy làm theo những gì xảy ra khi bạn + hai Ratio s, điều gì sẽ xảy ra ở mỗi bước trong quá trình giảm. Chúng tôi bắt đầu từ the two-arity version of +:

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

này đưa chúng ta đến Numbers.add(Obj, Obj):

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

opslooks at the class of the first operand và sẽ tìm RatioOps. Điều này dẫn đến hàm 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); 
} 

Vì vậy, đây là thuật toán của bạn. Có lămBigInteger hoạt động ở đây (ba nhân lên, một add, một chia):

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

Bạn có thể xem như thế nào multiply được thực hiện; nó một mình không phải là tầm thường, và bạn có thể kiểm tra những người khác cho chính mình.

Chắc chắn, divide function liên quan đến việc tìm kiếm các gcd giữa hai con số để nó có thể được giảm:

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); 
    ... 
} 

Các gcd function tạo ra hai MutableBigInteger đối tượng mới.

Tính toán, tốn kém, như bạn có thể thấy từ tất cả những điều trên.Tuy nhiên, không giảm chi phí tạo thêm đối tượng ngẫu nhiên (như trong gcd ở trên), vì điều này thường đắt hơn khi chúng tôi liên quan đến truy cập bộ nhớ không được lưu vào bộ nhớ cache.

Chuyển đổi double không miễn phí, FWIW, là it involves a division of two newly-created BigDecimals.

Bạn thực sự cần một hồ sơ để xem chính xác nơi chi phí là. Nhưng hy vọng rằng ở trên cho một bối cảnh nhỏ.