logo标签列表

提高Java的BigInteger性能

javabiginteger
12

如何提高Java的大整数性能？

例如，以下是一个计算阶乘的程序：

import java.math.*;
class Fac {
  public static void main(String[] args) {
    BigInteger i = BigInteger.ONE;
    for(BigInteger z=BigInteger.valueOf(2);z.compareTo(BigInteger.valueOf(99999)) != 0;) {
      i = i.multiply(z);
      z = z.add(BigInteger.ONE);
    }
    System.out.println( i );
  }
}

那个程序在31.5秒内完成。

它是用 C++ 写的：

#include <iostream>
#include <gmpxx.h>
using namespace std;
int main() {
  mpz_class r;
  r = 1;
  for(int z=2;z<99999;++z) {
    r *= mpz_class(z);
  }
  cout << r << endl;
}

用时1.0s完成。

为了比较，以下是Ruby代码：

puts (2...99999).inject(:*)

使用Ruby完成所花费的时间为4.4秒，而在JRuby中则为32.2秒。

还有Go语言（作为比较）：

package main
import (
 "fmt"
 "math/big"
)
func main() {
  i := big.NewInt(1);
  one := big.NewInt(1)
  for z := big.NewInt(2); z.Cmp(big.NewInt(99999)) < 0;  {
      i.Mul(i,z);
      z.Add(z,one)
  }
  fmt.Println( i );
}

完成于1.6秒和0.7秒，用于MulRange

编辑 如要求：

import java.math.*;
class F2 {
  public static void main(String[] args) {
    BigInteger i = BigInteger.ONE, r = BigInteger.valueOf(2);
    for(int z=2; z<99999 ; ++z) {
      i = i.multiply(r);
      r = r.add(BigInteger.ONE);
    }
    System.out.println( i );
  }
}

运行时间：31.4 秒

编辑2 对于那些仍认为第一段和第二段Java代码不公平的人.. 

import java.math.*;
class F3 {
  public static void main(String[] args) {
    BigInteger i = BigInteger.ONE;
    for(int z=2; z<99999 ; ++z) {
      i = i.multiply(BigInteger.valueOf(z));
    }
    System.out.println( i );
  }
}

完成于31.1秒

编辑3 @OldCurmudgeon评论：

import java.math.*;
import java.lang.reflect.*;
class F4 {
  public static void main(String[] args) {
    try {
      Constructor<?> Bignum = Class.forName("java.math.MutableBigInteger").getDeclaredConstructor(int.class);
      Bignum.setAccessible(true);
      Object i = Bignum.newInstance(1);
      Method m = i.getClass().getDeclaredMethod("mul", new Class[] { int.class, i.getClass()});
      m.setAccessible(true);
      for(int z=2; z<99999 ; ++z) {
        m.invoke(i, z, i);
      }
      System.out.println( i );
    } catch(Exception e) { System.err.println(e); } 
  }
}

用时23.7秒完成

编辑4 正如@Marco13所说，最大的问题在于字符串的创建而不是BigInteger本身。

  • BigInteger: 3.0秒
  • MutableBigInteger hack: 10.1秒
  • 字符串创建: ~20秒
13
这并不是一个完全公平的比较；在Java中，您正在使用BigInteger作为循环变量，而在C++中，您只是使用了一个int。 - Oliver Charlesworth
2
一个修复方法是开始使用int，并缓存.valueOf，否则每次都会创建一个新的BigInteger。 - Marco Acierno
2
你可以尝试使用 MutableBigInteger。 - OldCurmudgeon
@OldCurmudgeon，它快了大约8秒，谢谢 - Kokizzu
1
你已经消除了之前所有值的GC开销，但仍然经常重新分配int[]。我尝试调整您的代码以预先分配int [50,000]，但似乎对我不起作用。我可能做错了。 - OldCurmudgeon
1
在Java 8中，编辑2需要运行3.5秒。比C++慢3倍并不算太糟糕。 - Captain_Obvious
4个回答
4

从以下开始：

import java.math.*;
class Fac {
  public static void main(String[] args) {
    BigInteger i = BigInteger.ONE;
    BigInteger maxValue = BigInteger.valueOf(99999);

    for(BigInteger z=BigInteger.valueOf(2); z.compareTo(maxValue) != 0;) {
      i = i.multiply(z);
      z = z.add(BigInteger.ONE);
    }

    System.out.println( i );
  }
}

.valueOf 源码

1081    public static BigInteger More ...valueOf(long val) {
1082        // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
1083        if (val == 0)
1084            return ZERO;
1085        if (val > 0 && val <= MAX_CONSTANT)
1086            return posConst[(int) val];
1087        else if (val < 0 && val >= -MAX_CONSTANT)
1088            return negConst[(int) -val];
1089
1090        return new BigInteger(val);
1091    }

由于MAX_CONSTANT为16，每次都会创建一个新的BigInteger。

我认为它可能会变慢，因为GC开始收集一些旧的BigInteger实例，但无论如何，你应该始终使用int和long..在这里并不真正需要使用BigInteger。

根据您最后的测试结果，我认为我们可以确定它可能是由GC引起的。

好的，这是垃圾回收。为了正确计时，您应该禁用垃圾回收（因为在for循环中使用int更好）。请阅读此链接：https://dev59.com/hHRB5IYBdhLWcg3wz6UK - Marco Acierno
3
计算本身不应该花费太长时间。但是字符串创建可能需要一段时间。

这个程序（感谢OldCurmudgeon和https://dev59.com/CGsz5IYBdhLWcg3wfn4x#8583188）在使用-Xmx1000m -sever启动时，在Core I7，3GHz，Java 7/21上大约需要3.9秒：

import java.lang.reflect.Constructor;
import java.lang.reflect.Method;

public class FastBigInteger
{
    public static void main(String[] args)
    {
        try
        {
            Class<?> c = Class.forName("java.math.MutableBigInteger");
            Constructor<?> con = c.getDeclaredConstructor(int.class);
            con.setAccessible(true);
            Object i = con.newInstance(1);
            Method m = c.getDeclaredMethod("mul", new Class[] { int.class, c });
            m.setAccessible(true);
            long before = System.nanoTime();
            for (int z = 2; z < 99999; ++z)
            {
                m.invoke(i, z, i);
            }
            long after = System.nanoTime();
            System.out.println("Duration "+(after-before)/1e9);

            String s = i.toString();
            int n = s.length();
            int lineWidth = 200;
            for (int j=0; j<n; j+=lineWidth)
            {
                int j0 = j;
                int j1 = Math.min(s.length(), j+lineWidth);
                System.out.println(s.substring(j0, j1));
            }
        }
        catch (Exception e)
        {
            System.err.println(e);
        }
    }
}

在打印实际计算的持续时间之后，直到完成字符串的创建，需要相当长的时间，但这在此处几乎不应考虑。
这仍然不是一个明智的基准测试，但至少表明计算本身没有问题。
但是必须承认，当仅使用BigInteger而不是这个MutableBigInteger hack时，需要大约15秒的时间，与C++实现相比相当差。
1
你是对的，它在 3.0 秒内完成，总时间为 23.8 秒，所以问题可能出在字符串创建上。 - Kokizzu
1

其他答案与使用代码来调节性能有关。

如果您使用的Java版本低于1.8.0_151，可以通过使用以下命令选项来调整大整数性能：

-XX:+UseMontgomerySquareIntrinsic
-XX:+UseMontgomeryMultiplyIntrinsic
-XX:+UseSquareToLenIntrinsic
-XX:+UseMultiplyToLenIntrinsic

在1.8.0_151版本之后，这些选项默认开启。

1
我有一些Clojure代码，使用大整数计算第100000个斐波那契数。现在这个帖子不是关于Clojure的，但是由于Clojure运行在JVM上，并且我对一些现有的大整数实现进行了基准测试，所以我觉得在这里发表评论可能会有价值。
当算法使用JVM BigInteger类（在Clojure中表示为xN文字语法）时，它看起来如下：
(defn fibo [n]
  (loop [i n a 1N b 1N]
    (if (> i 0)
      (recur (dec i) b (+ a b))
      a)))

我已经使用四个大整数实现重新实现了这个功能，并使用 Clojure criterium 库运行基准测试，该库对数据进行预热和一些统计分析，以尝试得到相对准确的数字。
我在我的 2.8 GHz 英特尔 Core i7 MacBook 上获得以下结果：

现在我意识到这只是个人经验，并且我们仅在这里测量了加法，但我必须说 huldra 的口号“自 2015 年以来超越 BigInteger”在这种情况下似乎非常准确。

非常感谢您提供有关更快的大整数加法算法的候选人的指针。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接