Java BigInteger, taglia l'ultima cifra

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

Domanda

Abbastanza semplice, se il numero BigInteger è 543 voglio che tagli l'ultima cifra in modo che sia 54.

Due semplici modi per farlo possono essere:

  1. Usa le stringhe, ottieni la sottostringa e crea un nuovo biginteger con il nuovo valore.
  2. Utilizza il metodo di divisione BigIntegers con il numero 10.( 543 / 10 = 54,3 => 54 )

Il fatto è che lo eseguirò molto di volte con numeri interi grandi ovviamente.

La mia ipotesi è che giocare con le stringhe sarà più lento, ma ancora una volta non ho usato così tanto Bigintegers e non ho idea di quanto sia costosa l'operazione di "divisione".

La velocità è essenziale qui, qual è il modo più veloce per implementarlo (la memoria non è un problema, solo la velocità)?

Sono benvenute anche altre soluzioni.

È stato utile?

Soluzione

Dividendo per 10 è molto più veloce rispetto all'utilizzo di un'operazione di stringa. Utilizzando il seguente parametro di riferimento, ottengo circa 161x volte (rapporto è proporzionale al numero di bit) 

    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));

Altri suggerimenti

Divide by 10 è più probabile che sarà più veloce.

Se si crea un BigInteger staticamente che ha il numero 10, e quindi utilizzare tale di dividere per 10, che sarà potenzialmente il modo più veloce per farlo. Si batte la creazione di una nuova temporanea BigInteger ogni volta.

Il problema con la stringa è che si sta essenzialmente creando una nuova stringa ogni volta, e che è molto più lento, per non parlare della lentezza che sta scorrendo una corda per ottenere la sua sottostringa.

Il modo più veloce sta dividendo il numero da 10 con un'implementazione divisione interna efficiente. Gli interni di questa operazione sono dietro le quinte, ma certamente non banale dal momento che il numero è memorizzato base-2.

Il più veloce possibile implementazione sarebbe probabilmente utilizzare un tipo di dati la cui rappresentazione interna utilizza base 10, cioè una sorta di BCD . Poi, la divisione per 10 significherebbe semplicemente cadere l'ultimo byte (o anche solo incrementare / decrementare un indice se si implementa nel modo giusto).

Naturalmente, dovreste implementare tutta l'aritmetica e le altre operazioni è necessario da zero, rendendo questo un sacco di lavoro.

E 'probabilmente prematuro anche essere questa domanda. Farlo nel modo più ovvio (dividere per dieci), quindi punto di riferimento, e ottimizzarlo se è necessario. Conversione in una rappresentazione di stringa e ritorno sarà molto più lento.

Il toString () da solo è probabilmente più lento rispetto alla stringa.

Diverse persone hanno affermato che dividere per 10 sarà più veloce che convertire in una stringa e prendere la sottostringa.Per capire perché, basti pensare al calcolo coinvolto nella conversione da un BigInteger a una String e viceversa.Per esempio: 

/* 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();

La cosa importante da notare è che la conversione da un numero a una stringa comporta una divisione ripetuta per 10.Infatti il ​​numero di divisioni è proporzionale a log10(numero).Andare nella direzione opposta implica moltiplicazioni di log10 (numero).Dovrebbe essere ovvio che si tratta di calcoli molto più complessi di una singola divisione per 10.

se le prestazioni è fondamentale ... non utilizzare java

In lingue che possono essere compilati in codice macchina (ad esempio C o C ++) la divisione intera è più veloce di un fattore enorme. operazioni di stringa utilizzano (o possono usare) allocazioni di memoria e sono quindi lento.

La mia scommessa è che in Java sarà più veloce anche divisioni Int. In caso contrario, la loro attuazione VM è davvero strano.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top