Java BigInteger, coupé dernier chiffre

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

Question

Assez facile, si le nombre est de 543 BigInteger Je veux de couper le dernier chiffre pour qu'il soit 54.

Deux façons simples de faire cela peut être:

  1. Utilisez des chaînes, obtenir et créer de nouveaux sous-chaîne BigInteger avec la nouvelle valeur.
  2. Utilisez BigIntegers divisent procédé avec le numéro 10. (543/10 = 54,3 => 54)

La chose est que je vais effectuerons cette beaucoup de fois avec de grands entiers bien sûr.

Je pense que jouer avec des chaînes sera plus lente mais là encore je n'ai pas utilisé Bigintegers tant et ne savent pas combien coûte l'opération « fracture » est.

La vitesse est essentielle ici, ce qui est le meilleur moyen de mettre en œuvre cette (mémoire est pas un problème que la vitesse)?

Les autres solutions sont également les bienvenus.

Était-ce utile?

La solution

La division par 10 est beaucoup plus rapide que d'utiliser une opération de sous-chaîne. Utilisation de l'indice de référence suivant, je reçois environ 161x fois (ratio est proportionnel au nombre 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));

Autres conseils

Diviser par 10 est plus susceptible d'être plus rapide.

Si vous créez un BigInteger statiquement qui a le numéro 10, et ensuite utiliser que de diviser par 10, qui sera potentiellement le meilleur moyen de le faire. Il bat la création d'un nouveau BigInteger chaque fois que temporaire.

Le problème est que de sous-chaîne vous créez essentiellement une nouvelle chaîne à chaque fois, et qui est beaucoup plus lent, sans parler de la lenteur qui est Itère une chaîne pour obtenir son sous-chaîne.

La façon la plus rapide divise le nombre de 10 avec une mise en œuvre de la division interne efficace. Les entrailles de cette opération sont dans les coulisses, mais certainement non négligeable puisque le nombre est base 2 stocké.

La mise en œuvre la plus rapide possible serait probablement d'utiliser un type de données dont la représentation interne utilise la base 10, à savoir une sorte de BCD . Ensuite, la division par 10 signifierait simplement laisser tomber le dernier octet (ou même simplement incrémenter / décrémenter un index si vous le mettre en œuvre le droit chemin).

Bien sûr, vous auriez à mettre en œuvre toutes les opérations arithmétiques et d'autres opérations dont vous avez besoin à partir de zéro, ce qui en fait beaucoup de travail.

Il est sans doute prématuré de même poser cette question. Faites-la manière évidente (diviser par dix), puis de référence, et l'optimiser si vous avez besoin. Conversion à une représentation de chaîne et le dos sera beaucoup plus lent.

Le toString () seul est probablement plus lente que la sous-chaîne.

Plusieurs personnes ont dit que la division par 10 sera plus rapide que la conversion en chaîne et en prenant la sous-chaîne. Pour comprendre pourquoi, il suffit de penser le calcul impliqué dans la conversion d'un BigInteger à une chaîne, et vice versa. Par exemple: 

/* 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 chose importante à noter est que la conversion d'un nombre à une chaîne implique de diviser de façon répétée par 10. En effet, le nombre de divisions est proportionnelle à log10 (nombre). Dans l'autre direction implique log10 (nombre) multiplications. Il devrait être évident que cela est beaucoup plus calcul qu'une seule division par 10.

si la performance est cruciale ... ne pas utiliser java

Dans les langues qui compilent de code machine (par exemple C ou C ++) la division entière est plus rapide par un facteur très important. Opérations sur les chaînes utilisent (ou peuvent utiliser) les allocations de mémoire et sont donc lents.

Mon pari est que java divisions int seront plus rapides aussi. Dans le cas contraire leur mise en œuvre vm est vraiment bizarre.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top