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/< /a>
另一种方法是实现空间复杂度较低的算法。 :)

将它们全部因式分解，并将所有质因数与最大指数相乘。如果所有数字都小于 10000，则可以使用基元，然后使用 BigInt 进行乘法。这意味着要创建的对象要少得多。

Answer 2

该程序不占用 32MB 的任何内容。 JVM 的所有类加在一起及其关联的堆存储可能为 32MB。或者，加上 JVM 进程的开销，您的操作系统可能会报告它正在使用 32MB。

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

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

Answer 3

使用 BigInteger.ONE，而不是 new BigInteger("1")，但 32Mb 实际上并不算多，几乎任何 Java 代码都会占用它。

Answer 4

您可以使用 java 垃圾收集器来获得接受。只需在打印每种情况的解决方案后调用 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。

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