Java BigInteger, abgeschnitten letzte Ziffer

StackOverflow https://stackoverflow.com/questions/1144735

Frage

Ziemlich einfach, wenn die BigInteger Nummer 543 ist ich will es die letzte Stelle abgeschnitten, so dass es 54 ist.

Zwei einfache Möglichkeiten, dies zu tun:

  1. Verwenden Sie Zeichenfolge, erhalten String und neue BigInteger mit dem neuen Wert schaffen.
  2. Verwendung BigIntegers dividieren Methode mit der Nummer 10 (543/10 = 54,3 => 54)

Die Sache ist, werde ich diese eine Menge durchführen Mal mit großen ganzen Zahlen natürlich.

Meine Vermutung ist, dass mit Streichern um zu spielen langsamer sein wird, aber dann wieder habe ich nicht verwendet BigIntegers so viel und haben keine Ahnung, wie teuer die „Kluft“ Betrieb ist.

Die Geschwindigkeit ist wichtig, hier, was der schnellste Weg, um dies zu implementieren (Speicher ist kein Problem, nur Geschwindigkeit)?

Andere Lösungen sind auch willkommen.

War es hilfreich?

Lösung

von 10 Dividing ist viel schneller als einen Teilbetrieb verwendet wird. Unter Verwendung der folgenden Benchmark, erhalte ich etwa 161x mal (Verhältnis ist proportional zur Bitzahl) 

    long divTime = 0;
    long substrTime = 0;
    final int bitsCount = 1000;

    for (int i = 0; i < 1000; ++i) {
        long t1, t2;
        BigInteger random = new BigInteger(bitsCount, new Random());

        t1 = System.currentTimeMillis();
        random.divide(BigInteger.TEN);
        t2 = System.currentTimeMillis();
        divTime += (t2 - t1);

        t1 = System.currentTimeMillis();
        String str = random.toString();
        new BigInteger(str.substring(0, str.length() - 1));
        t2 = System.currentTimeMillis();
        substrTime += (t2 - t1);
    }

    System.out.println("Divide: " + divTime);
    System.out.println("Substr: " + substrTime);
    System.out.println("Ratio:  " + (substrTime / divTime));

Andere Tipps

Division durch 10 wird höchstwahrscheinlich schneller zu gehen.

Wenn Sie eine BigInteger erstellen statisch, dass die Zahl 10 hat und dann, dass durch 10 zu teilen verwenden, dass der schnellste Weg sein wird, möglicherweise, dies zu tun. Es schlägt einen temporären neue BigInteger jedes Mal zu schaffen.

Das Problem mit Teilzeichenfolge ist, dass Sie im Wesentlichen eine neue Zeichenfolge jedes Mal erstellen, und das ist viel langsamer, nicht die Langsamkeit zu erwähnen, die durch einen String iteriert seine Teilkette zu erhalten.

Der schnellste Weg, um die Zahl von 10 mit einer effizienten internen Aufteilung Umsetzung spaltet. Die Einbauten dieser Operation sind hinter den Kulissen, aber sicherlich nicht trivial, da die Zahl zur Basis 2 gespeichert wird.

Die schnellstmögliche Implementierung würde wahrscheinlich einen Datentyp, deren interne Darstellung verwendet Basis 10, dh eine Art von BCD . Dann Division durch 10 würde lediglich bedeuten, das letzte Byte fallen (oder auch nur Inkrementieren / Dekrementieren einen Index, wenn Sie es den richtigen Weg implementieren).

Natürlich würden Sie alle arithmetischen und andere Operationen implementieren müssen Sie von Grund auf neu müssen, so dass diese eine Menge Arbeit.

Es ist wahrscheinlich verfrüht selbst diese Frage stellen. Tun Sie es die offensichtliche Art und Weise (Division durch zehn), dann Benchmark sie und optimieren es, wenn Sie benötigen. Umwandlung in eine String-Darstellung und zurück wird viel langsamer.

Die toString () allein ist wahrscheinlich langsamer als die Teilkette.

Verschiedene Leute haben gesagt, dass durch 10 dividiert wird schneller sein als Konvertierung in einen String und den Teil nehmen. Um zu verstehen, warum, man denke nur an die beteiligten Berechnung in einen String aus einem BigInteger umwandelt und umgekehrt. Zum Beispiel: 

/* simplified pseudo code for converting +ve numbers to strings */
StringBuffer sb = new StringBuffer(...);
while (number != 0) {
   digit = number % 10;
   sb.append((char)(digit + '0'));
   number = number / 10;
}
return sb.toString();

Die wichtige Sache zu beachten ist, dass in einen String aus einer Reihe Umwandlung von 10 wiederholt Teilung bringt der Tat die Anzahl der Teilungen ist proportional zu log 10 (Zahl). Geht in die andere Richtung geht log10 (Anzahl) Multiplikationen. Es sollte offensichtlich sein, dass diese viel mehr Rechenaufwand als eine Division durch 10 ist.

, wenn die Leistung ist entscheidend ... Java nicht verwenden

In Sprachen, die in Maschinencode kompilieren (zum Beispiel C oder C ++) die ganze Zahl dividieren ist schneller durch einen sehr großen Faktor. String-Operationen verwenden (oder verwenden) Speicherzuordnungen und sind daher langsam.

Meine Wette ist, dass in Java int Divisionen schneller sein. Ansonsten ihre vm Implementierung ist wirklich seltsam.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top