Java BigInteger, cortou último dígito

Question

Bastante fácil, se o número BigInteger é 543 eu quero que ele cortou o último dígito de modo que é 54.

Duas maneiras fáceis de fazer isso pode ser:

1. Use cordas, obter substring e criar novas BigInteger com o novo valor.
2. Utilização BigIntegers método divisão com o número 10. (543/10 = 54,3 => 54)

A coisa é que eu estará realizando este muito de vezes com grandes números inteiros, é claro.

Meu palpite é que brincar com cordas será mais lento, mas, em seguida, BigIntegers novamente eu não usei tanto e não tem idéia do quão caro a operação de "dividir" é.

A velocidade é essencial aqui, o que é o caminho mais rápido para implementar este (memória não é problema só de velocidade)?

Outras soluções também são bem vindos.

Answer 1

Dividindo por 10 é muito mais rápido do que usar uma operação substring. Usando a seguinte referência, eu recebo cerca de 161x vezes (razão é proporcional à contagem de bits)

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

Answer 2

Dividir por 10 é mais provável vai ser mais rápido.

Answer 3

Se você criar um BigInteger estaticamente que tem o número 10, e depois usar isso para dividir por 10, que será potencialmente o caminho mais rápido para fazer isso. Ele bate a criação de um novo BigInteger temporária de cada vez.

O problema com substring é que você está criando essencialmente uma nova cadeia a cada momento, e que é muito mais lento, para não mencionar a lentidão que está interagindo através de uma corda para obter a sua substring.

Answer 4

A maneira mais rápida é a divisão do número 10 com uma implementação eficiente divisão interna. Os internos dessa operação estão nos bastidores, mas certamente não é trivial, pois o número é armazenado base-2.

Answer 5

O mais rápido possível implementação provavelmente seria usar um tipo de dados cujo interna representação usa a base 10, ou seja, uma espécie de BCD . Então, a divisão por 10 significaria simplesmente deixar cair o último byte (ou mesmo apenas incrementar / decrementar um índice se você implementá-lo da maneira correta).

Claro, você teria que implementar todas as operações aritméticas e outras que você precisa a partir do zero, tornando este um monte de trabalho.

Answer 6

É provavelmente prematuro até mesmo ser feito essa pergunta. Fazê-lo da maneira óbvia (dividir por dez), em seguida, referência-lo e otimizá-lo se você precisar. A conversão para uma representação de cadeia e volta vai ser muito mais lento.

Answer 7

O toString () sozinho é provavelmente mais lento do que o substring.

Answer 8

Várias pessoas disseram que dividindo por 10 será mais rápido do que converter para uma string e tomando o substring. Para entender o porquê, basta pensar sobre o cálculo envolvido na conversão de uma BigInteger a um String, e vice-versa. Por exemplo:

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

O importante a notar é que a conversão de um número para uma string implica repetidamente dividir por 10. Na verdade, o número de divisões é proporcional ao log 10 (número). Indo em outra direção envolve log10 (número) multiplicações. Deveria ser óbvio que este é muito mais computação do que uma única divisão por 10.

Answer 9

Se o desempenho é crucial ... não usar java

Em linguagens que compilam para código de máquina (por exemplo, C ou C ++) a divisão inteira é mais rápido por um fator enorme. operações de cadeia usar (ou pode usar) alocações de memória e são, portanto, lento.

A minha aposta é que em java divisões int será mais rápido também. Caso contrário, a sua implementação vm é realmente estranho.