Java BigInteger, cortó último dígito

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

Pregunta

bastante fácil, si el número es 543 BigInteger quiero que cortó el último dígito para que sea 54.

Dos formas fáciles de hacer esto puede ser:

  1. Use cuerdas, consiguen subcadena y crear nuevos BigInteger con el nuevo valor.
  2. Use BigIntegers dividen método con el número 10. (543/10 = 54,3 => 54)

Lo que pasa es que va a realizar este mucho de veces con grandes números enteros, por supuesto.

Mi conjetura es que jugando con cuerdas será más lenta pero de nuevo no he utilizado BigIntegers tanto y no tienen idea de lo caro que la operación "brecha" es.

La velocidad es esencial en este caso, ¿cuál es la manera más rápida de poner en práctica esta (la memoria no es un problema sólo la velocidad)?

Otros soluciones también son bienvenidos.

¿Fue útil?

Solución

Dividiendo por 10 es mucho más rápido que el uso de una operación de subcadena. Utilizando el siguiente punto de referencia, Tengo alrededor de 161x veces (relación es proporcional al número 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));

Otros consejos

Dividir por 10 es más probable que va a ser más rápido.

Si crear un BigInteger estáticamente que tiene el número 10, y luego utilizar eso para dividir por 10, que será potencialmente la forma más rápida de hacerlo. Es mejor que la creación de un nuevo BigInteger temporal cada vez.

El problema con la subcadena es que básicamente está creando una nueva cadena cada vez, y eso es mucho más lento, por no hablar de la lentitud que se iteración a través de una cadena de conseguir su subcadena.

La forma más rápida es dividir el número 10 con una implementación eficiente de división interna. Los detalles internos de funcionamiento que están detrás de las escenas, pero sin duda no es trivial ya que el número se almacena en base 2.

El más rápido posible implementación probablemente sería utilizar un tipo de datos cuya representación interna utiliza la base 10, es decir, una especie de BCD . Entonces, la división por 10 significaría simplemente dejar caer el último byte (o incluso incrementar / decrementar un índice si se implementa de la manera correcta).

Por supuesto, habría que poner en práctica toda la aritmética y otras operaciones que necesita a partir de cero, haciendo de esta una gran cantidad de trabajo.

Es probable que sea prematuro, incluso se hace esta pregunta. Hacerlo de la manera obvia (dividir por diez), a continuación referencia, y optimizarlo si es necesario. Conversión a una representación de cadena y de vuelta será mucho más lento.

El toString () por sí sola es probablemente más lento que la subcadena.

Varias personas han dicho que dividir por 10 será más rápido que convertir en una cadena y tomar la subcadena. Para entender por qué, sólo pensar en el cálculo implicados en la conversión de un BigInteger en una cadena, y viceversa. Por ejemplo: 

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

Lo importante a destacar es que la conversión de un número en una cadena implica dividir repetidamente por 10. De hecho, el número de divisiones es proporcional a log10 (número). El ir en la otra dirección implica log10 (número) multiplicaciones. Debería ser obvio que esto es mucho más que un cálculo simple división por 10.

si el rendimiento es crucial ... no use java

En las lenguas que compilan a código de máquina (por ejemplo C o C ++) la división entera es más rápido por un factor enorme. operaciones de cadena utilizan (o pueden utilizar) las asignaciones de memoria y son por lo tanto lento.

Mi apuesta es que en java divisiones int serán más rápidas también. De lo contrario su aplicación vm es muy raro.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top