python 的 reduce 实现产生了哪些开销？

Question

我有一些 python 脚本花费的时间比我预期的要长，所以我开始调查并在 python 的性能中发现了一些惊喜。大多数情况下，它似乎围绕着reduce，但我不明白为什么。

为了实验，我写了以下两个模块：

py.py

from functools import reduce

def mysum(n):
    return reduce(lambda acc, x: acc + x, range(n + 1))

n = int(1e8)
print(mysum(n))

和

clj.clj

(defn mysum [n]
  (reduce + (range (inc n))))

(println (mysum 1e8))

我使用 time:

比较了他们的表现

➜  ~ time python py.py
5000000050000000
python py.py  21.90s user 0.41s system 95% cpu 23.344 total
➜  ~ time lumo clj.clj
5000000050000000
lumo clj.clj  2.44s user 0.13s system 102% cpu 2.519 total

看来 python 的执行速度比 clojure 实施慢 10 倍以上。但这与我的预期相反。

即使运行使用 JVM 的 clj 文件会产生大量启动成本，python 也被击败了一英里：

➜  ~ time clj clj.clj
5000000050000000
clj clj.clj  6.01s user 0.72s system 153% cpu 4.394 total

为什么python这里的reduce这么慢？我做错了什么吗？

Answer 1

您的 python 代码正在被解释，而 Clojure 代码正在 JVM 上由 HotSpot 编译器编译。这是在 JVM 上的一大优势，也是 Python 和 Ruby 分别在 JVM 上具有端口 Jython 和 JRuby 的原因。

本机中的简单求和甚至更快Java：以下是一些快速比较：

class Calc {
  public static long cumsum( long limit ) {
    long result = 0;
    for (long i=0; i<limit; i++) {
      result += i;
    }
    return result;
  }

(let [limit 1e8]
  (newline) (println :result-clj)
  (crit/quick-bench (reduce + (range limit)))

(newline) (println :result-java-cumsum)
(crit/quick-bench (Calc/cumsum limit)))

:result-clj             Execution time mean : 1777.600 ms
:result-java-cumsum     Execution time mean :   26.920399 ms

是的，这是 66 倍的加速。尝试将计数减少到 1e6。

:result-clj             Execution time mean : 17572.885 µs
:result-java-cumsum     Execution time mean :   257.092 µs

另一个技巧是 Hotspot Compiler 通常可以识别 1..N 的和并代入代数公式

sum(1..N) => N*(N+1)/2

完全没有循环！

Answer 2

我记得，range 是一个列表，而 xrange 是可迭代的。尽管如此，我已经尝试更换它，但没有用。所以是的，这里的关键问题似乎与解释器的性质有关。顺便说一句，这个工作很快 - 总和（xrange（100000001））

python 的 reduce 实现产生了哪些开销？

What overhead is incurred in python's reduce implementation?

python

clojure

python-3.x

clojurescript