La performance de certaines applications peut être considérablement améliorée avec l'utilisation de tables. Il s'agit tout simplement de ne pas calculer le résultat à chaque fois, mais de précalculer le résultat une fois pour toutes.
Dans certaines applications d'informatique graphique, par exemple, il
est souvent nécessaire de compter le nombre de bits à dans un octet.
On peut bien sûr se servir de la fonction
logcount (voir section 6.2.8). Mais celle-ci
est trop générale pour l'application en question, car elle
s'applique non seulement aux octets, mais à n'importe quel entier.
Elle est donc obligée d'utiliser une méthode générale pour compter le
nombre de bits à
. Une façon plus rapide est de calculer, une fois
pour toutes, un tableau de
éléments dont l'élément numéro
contient le nombre de bits à
de l'octet ayant la valeur
. La
taille d'un tel tableau est environ
octets si les valeurs
qu'il contient sont des entiers de
bits.
Voici un exemple de ce que cela peut donner en terme de performance :
Dans cet exemple, on calcule la somme du nombre de bits à dans tous
les entiers de 0 à 255. Ce calcul est effectué
fois et la somme est renvoyée. Dans le premier cas, la
fonction logcount est utilisée et le calcul nécessite
environ
secondes. Dans le deuxième cas, un tableau est utilisé,
et le calcul nécessite environ
secondes, soit une amélioration
de
.
Si l'application n'a pas besoin de économiser la mémoire, il est même
possible de créer un tableau contenant le nombre de bits à de tous
les entiers de taille
bits.
Irene DURAND