Una de las formas intuitivas de calcular π en suma polinómica se ve a continuación,

π = (1/1 - 1/3 + 1/5 - 1/7 + 1/9 ...) × 4

La siguiente función ρ o ρ 'denota la suma polinómica , y el tiempo consumido τ para calcular el π se mide respectivamente,

 (defn term [k]                                                                                                        
   (let [x (/ 1. (inc (* 2 k)))]                                                                                       
     (if (even? k)                                                                                                     
       x                                                                                                               
       (- x))))                                                                                                        

 (defn ρ [n]                                                                                                           
   (reduce                                                                                                             
     (fn [res k] (+ res (term k)))                                                                                     
     0                                                                                                                 
     (lazy-seq (range 0 n))))                                                                                          

 (defn ρ' [n]                                                                                                          
   (loop [res 0 k 0]                                                                                                   
     (if (< k n)                                                                                                       
       (recur (+ res (term k)) (inc k))                                                                                
       res)))                                                                                                          

 (defn calc [P]                                                                                                        
   (let [start (System/nanoTime)                                                                                       
         π (* (P 1000000) 4)                                                                                           
         end (System/nanoTime)                                                                                         
         τ (- end start)]                                                                                              
     (printf "π=%.16f τ=%d\n" π τ)))                                                                                   

 (calc ρ)                                                                                                              
 (calc ρ')       

El resultado indica que ρ es aproximadamente la mitad de tiempo invertido que ρ ', de ahí que el reduce realiza mucho menos de lo óptimo que recurrir en este caso, pero ¿por qué?

1
sof 29 abr. 2020 a las 03:56

3 respuestas

La mejor respuesta

Reescribir su código y usar un temporizador más preciso muestra que no hay una diferencia significativa. Esto es de esperarse ya que tanto loop/recur como reduce son formas muy básicas y esperamos que ambos estén bastante optimizados.

(ns tst.demo.core
  (:use demo.core tupelo.core tupelo.test)
  (:require
    [criterium.core :as crit] ))

(def result (atom nil))

(defn term [k]
  (let [x (/ 1. (inc (* 2 k)))]
    (if (even? k)
      x
      (- x))))

(defn ρ [n]
  (reduce
    (fn [res k] (+ res (term k)))
    0
    (range 0 n)) )

(defn ρ' [n]
  (loop [res 0 k 0]
    (if (< k n)
      (recur (+ res (term k)) (inc k))
      res)) )

(defn calc [calc-fn N]
  (let [pi (* (calc-fn N) 4)]
    (reset! result pi)
    pi))

Medimos el tiempo de ejecución de ambos algoritmos usando Criterium:

(defn timings
  [power]
  (let [N (Math/pow 10 power)]
    (newline)
    (println :-----------------------------------------------------------------------------)
    (spyx N)
    (newline)
    (crit/quick-bench (calc ρ N))
    (println :rho @result)
    (newline)
    (crit/quick-bench (calc ρ' N))
    (println :rho-prime N @result)
    (newline)))

Y lo intentamos para 10 ^ 2, 10 ^ 4 y 10 ^ 6 valores de N:

(dotest
  (timings 2)
  (timings 4)
  (timings 6))

Con resultados para 10 ^ 2:

-------------------------------
   Clojure 1.10.1    Java 14
-------------------------------

Testing tst.demo.core

:-----------------------------------------------------------------------------
N => 100.0

Evaluation count : 135648 in 6 samples of 22608 calls.
             Execution time mean : 4.877255 µs
    Execution time std-deviation : 647.723342 ns
   Execution time lower quantile : 4.438762 µs ( 2.5%)
   Execution time upper quantile : 5.962740 µs (97.5%)
                   Overhead used : 2.165947 ns

Found 1 outliers in 6 samples (16.6667 %)
    low-severe   1 (16.6667 %)
 Variance from outliers : 31.6928 % Variance is moderately inflated by outliers
:rho 3.1315929035585537

Evaluation count : 148434 in 6 samples of 24739 calls.
             Execution time mean : 4.070798 µs
    Execution time std-deviation : 68.430348 ns
   Execution time lower quantile : 4.009978 µs ( 2.5%)
   Execution time upper quantile : 4.170038 µs (97.5%)
                   Overhead used : 2.165947 ns
:rho-prime 100.0 3.1315929035585537

Con resultados para 10 ^ 4:

:-----------------------------------------------------------------------------
N => 10000.0

Evaluation count : 1248 in 6 samples of 208 calls.
             Execution time mean : 519.096208 µs
    Execution time std-deviation : 143.478354 µs
   Execution time lower quantile : 454.389510 µs ( 2.5%)
   Execution time upper quantile : 767.610509 µs (97.5%)
                   Overhead used : 2.165947 ns

Found 1 outliers in 6 samples (16.6667 %)
    low-severe   1 (16.6667 %)
 Variance from outliers : 65.1517 % Variance is severely inflated by outliers
:rho 3.1414926535900345

Evaluation count : 1392 in 6 samples of 232 calls.
             Execution time mean : 431.020370 µs
    Execution time std-deviation : 14.853924 µs
   Execution time lower quantile : 420.838884 µs ( 2.5%)
   Execution time upper quantile : 455.282989 µs (97.5%)
                   Overhead used : 2.165947 ns

Found 1 outliers in 6 samples (16.6667 %)
    low-severe   1 (16.6667 %)
 Variance from outliers : 13.8889 % Variance is moderately inflated by outliers
:rho-prime 10000.0 3.1414926535900345

Con resultados para 10 ^ 6:

:-----------------------------------------------------------------------------
N => 1000000.0

Evaluation count : 18 in 6 samples of 3 calls.
             Execution time mean : 46.080480 ms
    Execution time std-deviation : 1.039714 ms
   Execution time lower quantile : 45.132049 ms ( 2.5%)
   Execution time upper quantile : 47.430310 ms (97.5%)
                   Overhead used : 2.165947 ns
:rho 3.1415916535897743

Evaluation count : 18 in 6 samples of 3 calls.
             Execution time mean : 52.527777 ms
    Execution time std-deviation : 17.483930 ms
   Execution time lower quantile : 41.789520 ms ( 2.5%)
   Execution time upper quantile : 82.539445 ms (97.5%)
                   Overhead used : 2.165947 ns

Found 1 outliers in 6 samples (16.6667 %)
    low-severe   1 (16.6667 %)
 Variance from outliers : 81.7010 % Variance is severely inflated by outliers
:rho-prime 1000000.0 3.1415916535897743

Tenga en cuenta que los tiempos para flip-flop rho y rho-prime para los casos 10 ^ 4 y 10 ^ 6. En cualquier caso, no crea ni se preocupe demasiado por los tiempos que varían en menos de 2 veces.


Actualizar

Eliminé el lazy-seq en el código original ya que clojure.core/range ya es vago. Además, nunca he visto lazy-seq usado sin un cons y una llamada recursiva a la función generadora.

Re clojure.core/range, tenemos los documentos:

Gama

Devuelve una secuencia perezosa de números desde el inicio (inclusive) hasta el final (exclusivo), por paso, donde start por defecto es 0, paso a 1 y finaliza al infinito. Cuando el paso es igual a 0, devuelve una secuencia infinita de inicio. Cuando inicio es igual a fin, devuelve la lista vacía.

En el código fuente, invoca el Java impl de clojure.core:

  ([start end]
   (if (and (instance? Long start) (instance? Long end))
     (clojure.lang.LongRange/create start end)
     (clojure.lang.Range/create start end)))

& el código Java indica que está fragmentado:

    public class Range extends ASeq implements IChunkedSeq, IReduce {
      private static final int CHUNK_SIZE = 32;
      <snip>
1
Alan Thompson 29 abr. 2020 a las 05:35

Además de otras respuestas. El rendimiento puede aumentar significativamente al eliminar el boxeo matemático (las versiones originales eran de unos 25 ms). Y la variante con loop/recur es 2 veces más rápida.

(set! *unchecked-math* :warn-on-boxed)

(defn term ^double [^long k]
  (let [x (/ 1. (inc (* 2 k)))]
    (if (even? k)
      x
      (- x))))

(defn ρ [n]
  (reduce
    (fn [^double res ^long k] (+ res (term k)))
    0
    (range 0 n)))

(defn ρ' [^long n]
  (loop [res (double 0) k 0]
    (if (< k n)
      (recur (+ res (term k)) (inc k))
      res)))

(criterium.core/quick-bench
    (ρ 1000000))
Evaluation count : 42 in 6 samples of 7 calls.
             Execution time mean : 15,639294 ms
    Execution time std-deviation : 371,972168 µs
   Execution time lower quantile : 15,327698 ms ( 2,5%)
   Execution time upper quantile : 16,227505 ms (97,5%)
                   Overhead used : 1,855553 ns

Found 1 outliers in 6 samples (16,6667 %)
    low-severe   1 (16,6667 %)
 Variance from outliers : 13,8889 % Variance is moderately inflated by outliers
=> nil
(criterium.core/quick-bench
    (ρ' 1000000))
Evaluation count : 72 in 6 samples of 12 calls.
             Execution time mean : 8,570961 ms
    Execution time std-deviation : 302,554974 µs
   Execution time lower quantile : 8,285648 ms ( 2,5%)
   Execution time upper quantile : 8,919635 ms (97,5%)
                   Overhead used : 1,855553 ns
=> nil
1
Sergey Trofimov 29 abr. 2020 a las 17:30

A continuación se muestra la versión mejorada para ser más representativo. Aparentemente, el rendimiento varía de un caso a otro, pero no tanto.

 (defn term [k]                                                                                                        
   (let [x (/ 1. (inc (* 2 k)))]                                                                                       
     (if (even? k)                                                                                                     
       x                                                                                                               
       (- x))))                                                                                                        

 (defn ρ1 [n]                                                                                                          
   (loop [res 0 k 0]                                                                                                   
     (if (< k n)                                                                                                       
       (recur (+ res (term k)) (inc k))                                                                                
       res)))                                                                                                          

 (defn ρ2 [n]                                                                                                          
   (reduce                                                                                                             
    (fn [res k] (+ res (term k)))                                                                                      
    0                                                                                                                  
    (range 0 n)))                                                                                                      

 (defn ρ3 [n]                                                                                                          
   (reduce + 0 (map term (range 0 n))))                                                                                

 (defn ρ4 [n]                                                                                                          
   (transduce (map term) + 0 (range 0 n)))                                                                             

 (defn calc [ρname ρ n]                                                                                                
   (let [start (System/nanoTime)                                                                                       
         π (* (ρ n) 4)                                                                                                 
         end (System/nanoTime)                                                                                         
         τ (- end start)]                                                                                              
     (printf "ρ=%8s n=%10d π=%.16f τ=%10d\n" ρname n π τ)))                                                            

 (def args                                                                                                             
   {:N (map #(long (Math/pow 10 %)) [4 6])                                                                             
    :T 10                                                                                                              
    :P {:recur ρ1 :reduce ρ2 :mreduce ρ3 :xreduce ρ4}})                                                                

 (doseq [n (:N args)]                                                                                                  
   (dotimes [_ (:T args)]                                                                                              
     (println "---")                                                                                                   
     (doseq [kv (:P args)] (calc (key kv) (val kv) n))))      
0
Alan Thompson 29 abr. 2020 a las 16:47