Java BigInteger Оптимизация памяти

Question

Я пытаюсь найти LCM с данными N числами. Но этот мой код занимает более 32 Мб памяти. Какую оптимизацию я могу выполнить здесь?

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

Эта программа не берет 32 МБ ничего. Все вместе собранные классы JVM и связанное с ними хранилище кучи могут занимать 32 МБ. Или, добавив накладные расходы на процесс JVM, ваша ОС может сообщить, что она использует 32 МБ.

Самый краткий ответ: вы не собираетесь уменьшать эти накладные расходы памяти, изменяя вашу программу.

Если у вас заканчивается память, дайте ей больше памяти. java -Xmx1g позволяет куче расти очень большой, до 1 ГБ, если она хочет.

Answer 3

Используйте BigInteger.ONE, а не новый BigInteger ("1"), но на самом деле 32 МБ не так много, практически любой код 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 для всех чисел.

Это предположение, но я думаю, что ваше использование памяти и скорость должны улучшиться.