时间戳

首页 > 解决方案 > 在 Java 中，哪种阶乘函数的实现通常更快？

java - 在 Java 中，哪种阶乘函数的实现通常更快？

问题描述

我正在考虑阶乘函数的两种可能实现。我不确定哪一个通常更快。我可以想到为什么两者都可能更快的论点。（我实际上并没有尝试实现快速阶乘函数；我只是对此感到好奇。）

方法一：

public static BigInteger factorial (int n) {
     BigInteger product = new BigInteger("1");
     for (int i = 1; i<=n; i++) {
          product = product.multiply(BigInteger.valueOf(i));
     }
     return product;     
}

方法二：

public static BigInteger factorial (int n) {
     BigInteger product = new BigInteger("1");
     for (int i = n; i>=1; i--) {
          product = product.multiply(BigInteger.valueOf(i));
     }
     return product;     
}

本质上，方法 1 执行乘法 1*2*...*n，为 (( 1 * 2 )* 3)*...，方法 2 计算相同项的乘积，但顺序相反：( ( n * (n-1) ) * (n-2) )*...

我的问题是：其中哪些通常具有更快的运行时间？

我知道乘以更大的数字会更慢，但是当将许多项相乘时，尽可能长时间地保持乘积的值相对较小（方法 1）或者在执行最大项的乘法时是否更快总产品仍然更小（方法2）？

是否取决于大小n？如果我使用long或int代替BigInteger（除非溢出），或者如果我使用另一种语言，答案会有所不同吗？

标签： javaoptimization

解决方案

我通过JMH运行了两种不同的方法，这就是你应该如何对 java 代码进行基准测试，因为它负责减轻热点预热等的影响：

n = 100
platform: JDK11, intel x86-64 2,9Ghz core i5 laptop.
Benchmark               Mode  Cnt       Score       Error  Units
MyBenchmark.highToLow  thrpt   25  175954,070 ± 20689,017  ops/s
MyBenchmark.lowToHigh  thrpt   25  184311,758 ± 18965,592  ops/s

看起来从低到高的胜利，但事实并非如此 - 这是相同的数字，这是统计噪音。

使用更大的 n，并减少迭代和运行时间可以让您快速获得答案：

n = 10000
platform: JDK11, intel x86-64 2,9Ghz core i5 laptop.
Benchmark               Mode  Cnt   Score    Error  Units
MyBenchmark.highToLow  thrpt    6  34,683 ±  7,075  ops/s
MyBenchmark.lowToHigh  thrpt    6  31,230 ± 21,437  ops/s

这归结为相同；这并不重要。

换句话说，同样快。

推荐阅读