Non dovrebbe anche una funzione ricorsiva in coda essere più veloce?

Question

Ho il seguente codice Clojure per calcolare un numero con una certa proprietà "factorable". (quello che fa esattamente il codice è secondario).

(defn factor-9 
    ([] 
    (let [digits (take 9 (iterate #(inc %) 1)) 
      nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))] 
     (some (fn [x] (and (factor-9 x) x)) nums))) 
    ([n] 
     (or 
     (= 1 (count (str n))) 
     (and (divisible-by-length n) (factor-9 (quot n 10)))))) 

ora, sono in TCO e si rendono conto che Clojure può fornire solo coda ricorsione se esplicitamente detto in modo da utilizzare la parola chiave recur. Così ho riscritto il codice per farlo (sostituendo il fattore-9 con ripresentarsi essendo l'unica differenza):

(defn factor-9 
    ([] 
    (let [digits (take 9 (iterate #(inc %) 1)) 
      nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))] 
     (some (fn [x] (and (factor-9 x) x)) nums))) 
    ([n] 
     (or 
     (= 1 (count (str n))) 
     (and (divisible-by-length n) (recur (quot n 10)))))) 

A mia conoscenza, TCO ha un doppio vantaggio. Il primo è che non usa lo stack pesantemente come una chiamata non ricorsiva alla coda e quindi non lo fa saltare su ricursioni più grandi. Il secondo, penso sia che di conseguenza è più veloce poiché può essere convertito in loop.

Ora, ho fatto un benchmark molto approssimativo e non ho visto alcuna differenza tra le due implementazioni. Ho sbagliato nella mia seconda ipotesi o ha qualcosa a che fare con l'esecuzione sulla JVM (che non ha TCO automatico) e recur usando un trucco per raggiungerlo?

Grazie.

Answer 1

L'uso di ripresentarsi non accelerare le cose, ma solo di circa 3 nanosecondi (veramente) oltre una chiamata ricorsiva. Quando le cose diventano così piccole possono essere nascoste nel rumore del resto del test. Ho scritto quattro test (link sotto) che sono in grado di illustrare la differenza di prestazioni.

Vorrei anche suggerire di utilizzare qualcosa come criterium durante il benchmarking. (Stack Overflow non mi consente di pubblicare più di 1 link poiché non ho alcuna reputazione di cui parlare, quindi dovrai cercarlo su google, forse "criterium clojure")

Per motivi di formattazione, I ' abbiamo messo i test e i risultati in questo gist.

In breve, per confrontare relativamente, se il test ricorsivo è 1, allora il test di looping è di circa 0,45, e il TCO test di circa 0,87 e la differenza assoluta tra i test ricorsivi e TCO sono di circa 3ns.

Ovviamente, all si applicano le avvertenze relative al benchmarking.

Answer 2

Dopo aver valutato factor-9 (quot n 10) un and e un or deve essere valutato prima che la funzione possa tornare. Quindi non è coda-ricorsiva.

Answer 3

Quando si ottimizza qualsiasi codice, è opportuno iniziare da colli di bottiglia potenziali o effettivi e ottimizzarlo prima.

Mi sembra che questo particolare pezzo di codice sta mangiando la maggior parte del tempo di CPU:

(map (fn [x] ,(Integer. (apply str x))) (permutations digits)) 

E questo non dipende da TCO in alcun modo - viene eseguita in stesso modo. Quindi, la chiamata di coda in questo particolare esempio ti consentirà di non utilizzare tutto lo stack, ma per ottenere prestazioni migliori, prova a ottimizzarlo.

Answer 4

solo un promemoria gentile che non ha clojure TCO