performance - 如何使阶乘更快？

Question

我在 Clojure 中制作了简单的阶乘程序。

(defn fac [x y] 
     (if (= x 1) y (recur (- x 1) (* y x)))
)

(def fact [n] (fac n 1))

怎样才能更快完成？如果它可以做一些更快的方式。

Answer 1

您可以在这里找到许多快速阶乘算法：http ://www.luschny.de/math/factorial/FastFactorialFunctions.htm

如上所述，Clojure 并不是最好的语言。考虑使用 C、C++、ForTran。

小心你使用的数据结构，因为阶乘增长得非常快。

Answer 2

借助您自己的fact函数（或任何其他函数），我们可以定义这个极快的版本：

(def fact* (mapv fact (cons 1 (range 1 21))))

这将在恒定时间内为 1 到 20 范围内的参数提供正确的结果。超出该范围，您的版本也不会给出正确的结果（即存在整数溢出(fact 21)）。

编辑：这是一个改进的实现，不需要另一个fact实现，不会溢出，并且在定义期间应该更快，因为它不会从头开始计算其查找表中的每个条目：

(def fact (persistent! (reduce (fn [v n] (conj! v (*' (v n) (inc n))))
                               (transient [1])
                               (range 1000))))

编辑2：对于不同的快速解决方案，即不建立查找表，最好使用已经高度优化的库。Google 的通用实用程序库 Guava 包含一个阶乘实现。

通过添加此 Leiningen 依赖项将其添加到您的项目中：[com.google.guava/guava "15.0"]. 然后你需要(import com.google.common.math.BigIntegerMath)然后可以用(BigIntegerMath/factorial n).

Answer 3

这是我最喜欢的：

(defn fact [n] (reduce *' (range 1 (inc n))))

' 告诉 Clojure 透明地使用 BigInteger 以避免溢出。