Me han dicho, y creo, que Clojure es más rápido que Python. ¿Por qué este código Python se ejecuta más rápido que este código Clojure aparentemente equivalente? ¿Python está haciendo algunas optimizaciones en tiempo de compilación?
def find_fifty(n,memory=1,count=0): if memory < 0.5: return count else: return find_fifty(n,memory*(1 - count/n),count+1) find_fifty(100000) (defn fifty ([n] (fifty n 1 0)) ([n memory count] (if (< memory 0.5) count (recur n (* memory (- 1 (/ count n))) (inc count))))) (fifty 100000)Parece que la complejidad del tiempo para Clojure es mayor que para Python. La función Python puede recibir una entrada muchas veces mayor que la función Clojure antes de que tenga un aumento significativo en el tiempo de ejecución.
Actualización - Clojure Fix
(defn fifty ([n] (fifty (float n) 1 0)) ([n memory count] (if (< memory 0.5) count (recur n (* memory (- 1 (/ count n))) (inc count))))) (fifty 10000000)Como se respondió, Clojure estaba manteniendo valores como números racionales muy grandes. Convertirlo en un flotante simplifica las operaciones que se realizan, lo que reduce el tiempo de ejecución.
El operador de división de Clojure, cuando se aplica a números enteros, realiza una división racional exacta. No se redondea al siguiente entero más bajo como lo hace Python. Su algoritmo implica que memory se convierta en una fracción muy compleja, a pesar de producir un número entero simple.
Modifiqué su función para imprimir sus valores intermedios antes de finalmente devolver el resultado:
(defn fifty ([n] (fifty n 1 0)) ([n memory count] (if (< memory 0.5) count (do (println n (* memory (- 1 (/ count n))) (inc count)) (fifty n (* memory (- 1 (/ count n))) (inc count))))))Y aquí está el resultado:
(fifty 500) 500 1 1 500 499/500 2 500 124251/125000 3 500 61752747/62500000 4 500 1914335157/1953125000 5 500 189519180543/195312500000 6 500 46811237594121/48828125000000 7 500 23077940133901653/24414062500000000 8 500 2838586636469903319/3051757812500000000 9 500 1393746038506722529629/1525878906250000000000 10 500 68293555886829403951821/76293945312500000000000 11 500 33395548828659578532440469/38146972656250000000000000 12 500 2037128478548234290478868609/2384185791015625000000000000 13 500 992081569052990099463209012583/1192092895507812500000000000000 14 500 241075821279876594169559790057669/298023223876953125000000000000000 15 500 23384354664148029634447299635593893/29802322387695312500000000000000000 16 500 2829506914361911585768123255906861053/3725290298461914062500000000000000000 17 500 1366651839636803295926003532603013888599/1862645149230957031250000000000000000000 18 500 329363093352469594318166851357326347152359/465661287307739257812500000000000000000000 19 500 158423647902537874867038255502873972980284679/232830643653869628906250000000000000000000000 20 500 475270943707613624601114766508621918940854037/727595761418342590332031250000000000000000000 21 500 227654782035946926183933973157629899172669083723/363797880709171295166015625000000000000000000000 22 500 54409492906591315357960219584673545902267911009797/90949470177292823791503906250000000000000000000000 23 500 25953328116444057425747024741889281395381793551673169/45474735088646411895751953125000000000000000000000000 24 500 3088446045856842833663895944284824486050433432649107111/5684341886080801486968994140625000000000000000000000000 25 500 58680474871280013839614022941411665234958235220333035109/113686837721616029739379882812500000000000000000000000000 26 500 13907272544493363279988523437114564660685101747218929320833/28421709430404007434844970703125000000000000000000000000000 27 27 Espero que pueda ver lo costoso que sería calcular estas fracciones irrazonables incluso para entradas pequeñas. Si desea la misma lógica que la versión de Python, simplemente puede reemplazar / con quot .
Un par de sugerencias:
El argumento n de la función fifty , ya sea de OP o de @amalloy, no cambia con recur . Así que mejor hazlo con un loop :
(defn fifty [n] (loop [memory 1.0, count 0] (if (< memory 0.5) count (recur (* memory (- 1 (/ count n))) (inc count))))) Al establecer el valor inicial de la memory en 1.0 en lugar de 1 , el * produce una serie de flotantes (dobles, para ser exactos), no racionales.
Podríamos usar funciones de secuencia para aclarar lo que está pasando:
(defn fifty- [n] (let [factors (map (fn [count] (- 1 (/ count n))) (range)) products (reductions * 1.0 factors)] (count (take-while #(< 0.5 %) products))))Este es probablemente el más lento de todos.