Java BigInteger内存优化

Question

我正在尝试找到给定N个数字的LCM。但是我的这段代码需要超过32Mb的内存。我可以在这里进行什么样的优化？

import java.util.Scanner ;
import java.math.BigInteger ; 
class Main {    
    public static BigInteger LCM( BigInteger a , BigInteger b ) {
        BigInteger c = a.gcd( b ) ;
        return a.multiply( b.divide( c ) ) ; 
    }
    public static void main( String[] args ) {
        Scanner s = new Scanner( System.in ) ;
        int n , t , ind , i ;    
        t = s.nextInt() ;
        for( ind = 1 ; ind <= t ; ind++ ) {
            n = s.nextInt() ;
            BigInteger res = BigInteger.ONE ;
            for( i = 0 ; i < n ; i++ ) {
                BigInteger a = s.nextBigInteger() ;
                res = LCM( res , a ) ;
            }
            System.out.println( "Case " + ind + ": " + res ) ;
        }
    }
}

样本输入：

2
3
2 20 10
4
5 6 30 60

样本输出：

Case 1: 20
Case 2: 60

Answer 1

也许你应该尝试一个像apfloat这样的好的任意精度数学库：http://www.apfloat.org/apfloat_java/另一种方法是实现一个空间复杂度较低的算法。 :)

将所有这些因子分解并将所有素数因子乘以最大指数。如果所有数字都小于10000，则可以使用基元，然后使用BigInt进行乘法运算。这意味着要创建的对象要少得多。

Answer 2

这个程序没有32MB的任何东西。 JVM的所有类都放在一起，它们的相关堆存储可能是32MB。或者，添加JVM进程的开销，您的操作系统可能会报告它使用32MB。

最接近的答案是：您不会通过更改程序来减少这种内存开销。

如果你的内存不足，那就给它更多的内存吧。 java -Xmx1g让堆变得非常大，如果需要的话，增加到1GB。

Answer 3

使用BigInteger.ONE，而不是新的BigInteger（“1”），但32Mb实际上并不多，几乎任何Java代码都需要它。

Answer 4

你可以使用java垃圾收集器来获取accepted。在为每个案例打印解决方案后，只需致电System.gc()。这是修改后的代码 -

import java.util.Scanner ;
import java.math.BigInteger ; 
class Main {    
    public static BigInteger LCM( BigInteger a , BigInteger b ) {
        BigInteger c = a.gcd( b ) ;
        return a.multiply( b.divide( c ) ) ; 
    }
    public static void main( String[] args ) {
        Scanner s = new Scanner( System.in ) ;
        int n , t , ind , i ;    
        t = s.nextInt() ;
        for( ind = 1 ; ind <= t ; ind++ ) {
            n = s.nextInt() ;
            BigInteger res = BigInteger.ONE ;
            for( i = 0 ; i < n ; i++ ) {
                BigInteger a = s.nextBigInteger() ;
                res = LCM( res , a ) ;
            }
            System.out.println( "Case " + ind + ": " + res ) ;
            System.gc();
        }
    }
}

Answer 5

如果你必须经常这样做，那么重新考虑这种方法可能是个好主意。

您可以静态地为数字1到10000的因子创建数据结构，并遍历它以快速计算所有数字的LCM。

这是一个猜测，但我认为你的内存使用和速度都应该提高。