为什么此 Python 代码比其等效的 Clojure 代码更快

Question

有人告诉我，并且我相信 Clojure 比 Python 更快。为什么这个 Python 代码比这个看似等效的 Clojure 代码运行得更快？Python 在编译时是否做了一些优化？

\n

def find_fifty(n,memory=1,count=0):\n    if memory < 0.5:\n        return count\n    else:\n        return find_fifty(n,memory*(1 - count/n),count+1)\n\nfind_fifty(100000)\xe2\x80\x8a\n

\n

(defn fifty \n    ([n] (fifty n 1 0))\n    ([n memory count]\n        (if (< memory 0.5)\n            count\n            (recur n\n                   (* memory (- 1 (/ count n)))\n                   (inc count)))))\n\n(fifty 100000)\n

\n

感觉 Clojure 的时间复杂度比 Python 高。Python函数可以接收比Clojure函数高很多倍的输入，才在运行时上有显着的提升。

\n

更新 - Clojure 修复

\n

(defn fifty \n    ([n] (fifty (float n) 1 0))\n    ([n memory count]\n        (if (< memory 0.5)\n            count\n            (recur n\n                   (* memory (- 1 (/ count n)))\n                   (inc count)))))\n\n(fifty 10000000)\n

\n

正如所回答的，Clojure 将值保留为非常大的有理数。将其转换为浮点数可以简化正在执行的操作，从而减少运行时间。

\n

Answer 1

Clojure 的除法运算符应用于整数时，会进行精确的有理除法。它不像 Python 那样向下舍入到下一个最小整数。memory尽管产生一个简单的整数，但您的算法涉及变成一个非常复杂的分数。

我修改了您的函数以在最终返回结果之前打印其中间值：

(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))))))

结果如下：

(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

我希望您能够看到，即使对于很小的输入，计算这些不合理的分数也会花费多么昂贵。如果你想要与Python版本相同的逻辑，你可以简单地替换/为quot.