sumowanie clojure wskaźniki powoli

Question

ja zsumowanie długą listę proporcjach Clojure, podobnie jak:

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

Czas pracy dla różnych n wynosi:

• n = 10^4 .. .... 41 ms
• n = 10^6 ...... 3,4 s
• n = 10^7 ...... 36S

The (mniej dokładna) alternatywnie jest podsumowanie tych wartości jako podwójna:

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

czas przebiegu tej wersji jest:

• n = 10^4 ...... 8,8 ms
• n = 10^6 ...... 350 ms
• n = 10^7 ...... 3,4 s

Dlaczego jest znacznie wolniej niż suma współczynników? Zgaduję, że ma to związek ze znalezieniem najmniejszej wspólnej liczby mnogiej mianowników, ale czy ktoś wie dokładnie, jaki algorytm Clojure używa do sumowania współczynników?

Answer 1

Zobaczmy, co się stanie, gdy + dwa Ratio s, co dzieje się na każdym etapie redukcji. Zaczynamy w the two-arity version of +:

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

To prowadzi nas do Numbers.add(Obj, Obj):

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

opslooks at the class of the first operand i znajdzie RatioOps. To prowadzi do funkcji 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); 
} 

Oto Twój algorytm. Istnieje pięćBigInteger tutaj (trzy operacje mnożenia, jedna dodawać, jeden divide):

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

Można zobaczyć, jak multiply jest realizowany; samo to nie jest trywialne i możesz samemu zbadać innych.

Pewnie mało, divide function polega na znalezieniu gcd pomiędzy dwoma numerami, więc może być zmniejszona:

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 tworzy dwie nowe MutableBigInteger obiektów.

Pod względem obliczeniowym jest to kosztowne, jak widać na podstawie powyższych danych.Nie pomijaj jednak kosztu dodatkowego, przypadkowego utworzenia obiektu (jak w powyższym przykładzie), ponieważ jest często droższy, ponieważ mamy do czynienia z dostępem do pamięci podręcznej.

Konwersja double nie jest darmowa, FWIW, jako it involves a division of two newly-created BigDecimals.

Naprawdę potrzebujesz profilera, aby zobaczyć dokładnie, gdzie koszt jest. Mam jednak nadzieję, że powyższe daje trochę kontekstu.