Czy Java może optymalizować "mutowanie" operacji BigInteger w pętlach?

Question

Muszę radzić sobie z dużą liczbą dużych liczb o wiele większych niż długie (> 10^200), więc używam BigIntegers. Najczęstszym operacja ja wykonać jest dodanie ich do akumulatora, ex:

BigInteger A = new BigInteger("0"); 
for(BigInteger n : nums) { 
    A = A.add(n); 
} 

oczywiście wykonywania kopii dotyczących działań destrukcyjnych jest dość odpadów (dobrze, tak długo jak nie jest na tyle duże, dostępny bufor), więc jestem zastanawiasz się, czy Java może to jakoś zoptymalizować (słyszałem, że istnieje klasa MutableBigInteger nie ujawniona przez math.java) lub czy powinienem napisać własną klasę BigInteger.

Answer 1

Tak, istnieje klasa java.math.MutableBigInteger używana przez BigInteger do operacji wymagających dużej mocy obliczeniowej. Niestety, jest zadeklarowany jako pakiet prywatny, więc nie możesz z niego korzystać. Istnieje również klasa "MutableBigInteger" w bibliotece Apache Commons, ale jest to tylko zmienne opakowanie dla BigInteger i to nie jest pomoc dla ciebie.

Zastanawiałem się, czy Java może zoptymalizować to jakoś ...

No ... nie do wytrzymania wyżej.

czy powinienem napisać własną klasę BigInteger.

To jest jedno podejście.

Innym jest pobranie źródeł OpenJDK, znalezienie kodu źródłowego dla java.math.MutableBigInteger, zmiana nazwy pakietu i dostępu oraz włączenie go do swojej bazy kodu. Jedyny szkopuł jest taki, że OpenJDK jest licencjonowany na licencji GPL (myślę, że GPL-2), i to ma znaczenie, jeśli kiedykolwiek rozpowszechnisz kod używając zmodyfikowanej klasy.

Zobacz także:

• What is the purpose of java.math.MutableBigInteger?

Answer 2

Szybszym rozwiązaniem jest ominięcie widoczność pakietu Java. Można to zrobić poprzez stworzenie pakietu o nazwie java.math w swoim własnym projekcie oraz tworzenie publicznych klasy, która naraża pakiet prywatnej MutableBigInteger tak:

package java.math; 

public class PublicMutableBigInteger extends MutableBigInteger { 

} 

Następnie można po prostu importować java.math.PublicMutableBigInteger; i używaj go jak każdej innej klasy. To rozwiązanie jest szybkie i nie narzuca żadnej konkretnej licencji.

Answer 3

Kompilator nie może wiele zrobić, ponieważ nie wie, co robi metoda add. Oto wygenerowany kod dla ciała pętli. Jak widać, po prostu wywołuje add i przechowuje wynik.

25: iload 5 
    27: iload 4 
    29: if_icmpge  51 
    32: aload_3 
    33: iload 5 
    35: aaload 
    36: astore 6 
    38: aload_1 
    39: aload 6 
    41: invokevirtual #5; //Method java/math/BigInteger.add:(Ljava/math/BigInteger;)Ljava/math/BigInteger; 
    44: astore_1 
    45: iinc 5, 1 
    48: goto 25 

Teoretycznie system uruchamiania maszyny wirtualnej Java może być bardziej inteligentny. Na przykład, może wykryć, że jeden obiekt ciągle nadpisuje inne właśnie przydzielone i po prostu zamienia dla nich dwa bufory alokacji. Jednak, jak widzimy, uruchamiając następujące program z rejestrowania zbieranie śmieci włączona, to niestety nie w tym przypadku

import java.math.BigInteger; 
import java.util.ArrayList; 
import java.util.Random; 

class Test { 
    public static void main(String[] args) { 
    ArrayList <BigInteger> nums = new ArrayList<BigInteger>(); 
    final int NBITS = 100; 
    final int NVALS = 1000000; 

    System.out.println("Filling ArrayList"); 
    Random r = new Random(); 
    for (int i = 0; i < NVALS; i++) 
     nums.add(new BigInteger(NBITS, r)); 

    System.out.println("Adding ArrayList values"); 
    BigInteger A = new BigInteger("0"); 
    for(BigInteger n : nums) { 
     A = A.add(n); 
    } 

    System.gc(); 
    } 
} 

Zobacz zbieranie śmieci nazywa trakcie dodawania.

C:\tmp>java -verbose:gc Test 
Filling ArrayList 
[GC 16256K->10471K(62336K), 0.0257655 secs] 
[GC 26727K->21107K(78592K), 0.0304749 secs] 
[GC 53619K->42090K(78592K), 0.0567912 secs] 
[Full GC 42090K->42090K(122304K), 0.1019642 secs] 
[GC 74602K->65857K(141760K), 0.0601406 secs] 
[Full GC 65857K->65853K(182144K), 0.1485418 secs] 
Adding ArrayList values 
[GC 117821K->77213K(195200K), 0.0381312 secs] 
[GC 112746K->77245K(228288K), 0.0111372 secs] 
[Full GC 77245K->137K(228288K), 0.0327287 secs] 

C:\tmp>java -version 
java version "1.6.0_25" 
Java(TM) SE Runtime Environment (build 1.6.0_25-b06) 
Java HotSpot(TM) 64-Bit Server VM (build 20.0-b11, mixed mode) 

Answer 4

Java nie zrobi żadnych specjalnych optymalizacji dla tego przypadku. BigInteger jest zwykle traktowany jak zwykła klasa, tak jak każda inna (w przeciwieństwie do String, która czasami otrzymuje pewne specjalne optymalizacje podczas łączenia wielu łańcuchów).

Ale w większości przypadków BigInteger jest wystarczająco szybki, aby i tak nie miało to znaczenia. Jeśli naprawdę sądzisz, że to może być problem, proponuję profilowanie kodu i opracowanie tego, co zajmuje trochę czasu.

Jeśli dodawanie BigIntegers jest naprawdę wąskim gardłem, to może być może mieć wartość ma sens, aby użyć niestandardowej mutowalnej klasy dużej liczby całkowitej do działania jako akumulator. Ale nie zrobiłbym tego, zanim nie udowodnisz, że jest to rzeczywiście główne wąskie gardło.