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

Question

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

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)

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

更新 - Clojure 修复

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

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

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.

Answer 2

一些建议：

OP 或@amalloy 的函数 fifty 的 n 参数未被 recur 更改。所以最好用 loop:

(defn fifty [n]
  (loop [memory 1.0, count 0]
    (if (< memory 0.5)
      count
      (recur (* memory (- 1 (/ count n))) (inc count)))))

通过将 memory 的初始值设置为 1.0 而不是 1，* 会产生一系列浮点数（准确地说是双精度数），而不是理性。

我们可以使用序列函数让事情变得更清楚：

(defn fifty- [n]
  (let [factors (map (fn [count] (- 1 (/ count n))) (range))
        products (reductions * 1.0 factors)]
    (count (take-while #(< 0.5 %) products))))

这可能是最慢的。

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

Why is this Python code faster than its equivalent Clojure code

python

optimization

runtime

clojure