Ho il seguente codice Clojure per calcolare un numero con una certa proprietà "factorable". (quello che fa esattamente il codice è secondario).Non dovrebbe anche una funzione ricorsiva in coda essere più veloce?
(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.
Questo è interessante, ho impostato criterium per misurare il fattore-9 e ho ottenuto che la versione TCO è in realtà un po 'più lenta rispetto alla versione non ottimizzata. Vedi https://gist.github.com/773060. –
Sorprendentemente (almeno per me :)) c'è un mondo di differenza quando si confrontano le due versioni per un semplice calcolo di Fibonacci: https://gist.github.com/773068 –
Questo è piuttosto drammatico, non è vero? Gioie di punti di riferimento. Almeno hai una tesi convincente che il TCO fa una grande differenza :-) – hutch