Droit de diffusion et d'utilisation:
Tous les documents ou partie de document ainsi que le code sont libres d'accès, mais ne peuvent pas être diffusé sur d'autres sites HTTP, FTP ou autres, sans mon accord.
Je me decharge de toutes les erreurs possibles mais j'accepte des propositions de modification.
Ce tutoriel n'a qu'un but informatif.

Avant propos :
Dans ce tutorial, je risque peut-être de faire appel à des notions de c++ mais cela ne doit pas faire fuir ceux qui ne connaisse pas ce langage car l’idée est la même partout.


Avertissement :
L'optimisation est le contraire de la clarté donc prenez conscience qu'en optimisant, le lecteur de votre code (voir vous meme plus tard) ne puisse ne pas comprendre aisement ce que vous avez ecris. Pensez à commenter !!!
De plus, toutes les astuces soumisent peuvent ne pas être adéquate dans votre programme, étant donné que c'est souvent du cas par cas. A vous de calculer le nombre d'opérations effectuées par le processeur, de savoir si vous voulez privilégier le temps de calcul, la taille mémoire, la taille du code(à éviter) et surtout testez vos algos.

1. Introduction

Salutations, aujourd’hui nous allons voir quelques notions et idées d’optimisation.
Tout d’abord qu’est-ce que l’optimisation ?
L’optimisation est l’art d’améliorer un algorithme pour le rendre plus rapide. Autant dire qu’un jour ou un autre il faudra bien passer par là.
Certains penserons que se ne sont que des légère améliorations qui ne valent pas le coup, ce qui est vrai pour la plupart des cas; mais dans d'autres, c'est indispensable (traitement d'image par exemple).

Nous verrons quelques petits trucs par ci par là pour optimiser - d’ailleurs je vous donne le droit de me contacter par mp (message privé) pour m’en soumettre d’autres ou me corriger- puis nous verrons l'orientation et l'état d’esprit à avoir pour améliorer ses algorithmes et enfin nous verrons le concept de pointeur mobile.

2. Glossaire des termes utilisés

i est une variable entiere
c est une variable caractère
f est une variable flottante (à virgule)
d est une variable double (toujours à virgule mais avec plus de précision)
nb est un nombre quelconque
& est l'operateur ET LOGIQUE
| est l'operateur OU LOGIQUE

3. Trucs et Astuces en vrac

  

3.1. On préfèrera

un entier à un décimal //cela prend moins de place dans la plupart des cas
on preferera toujours l'int car c'est un mot mémoire du processeur et il est donc plus rapide en manipulation par le processeur. un non signé à un signé //possibilité d'avoir un nombre plus grand

Lors des tests avec des ET LOGIQUES (&&), on mettra en argument de gauche le test qui a le plus de chance d'etre faux. De meme, lors des tests avec des OU LOGIQUES (||), on mettra en argument de gauche le test qui a le plus de chance d'etre vrai. ainsi:

bool souventvrai;
bool souventfaux;

if(souventfaux && souventvrai)
//et
if(souventvrai || souventfaux)
  

3.2. Les Boucles



Lorsque l'on connait le nombre de fois que l'on va parcourir notre boucle, on privilégera un compteur qui se décrementera et qui se comparera à 0.
Exemple:
unsigned int i(nbparcour);
while(i--){}
au lieu de:
for(unsigned int i(0);i<nbparcour;i++){}
Attention, il faudra adapter si l'on utilise les valeurs du compteur et peut etre commencer le traitement par la fin.

Ne negligez pas les break pour quitter une boucle, cela evite de faire un test pour savoir si on quitte la boucle.
Exemple:
bool pastrouve=true;
for(i=0;pastrouve && i<nbelem ;i++)
    if (tab[i]==5)
        pastrouve=false;
sera remplace par:
for(i=0;i<nbelem ;i++)
    if (tab[i]==5)
        break;

  

3.3. Les Tableaux

Lorsque l'on voudra copier un tableau, on utilisera de preference memcpy à un parcours de tableau et une recopie membre à membre
memcpy(tab2,tab,nbelem*sizeof(T));//ou T est le type d'objet stocke dans tab
au lieu de:
for(unsigned int i(0);i<nbelem;i++)
    tab2[i]=tab[i];
  

3.4. Selon les cas

Et oui, l'optimisation c'est aussi et surtout du cas par cas, sinon ca serait trop facile.


Par exemple, lorsque l'on a plusieurs booleens:
On regroupera les booléens (2 valeurs possibles: VRAI ou FAUX) dans un octet (les char par exemple). exemple:
bool b1,b2,b3,b4,b5,b6,b7,b8;
//ces huits booléens seront en fait stocké dans un seul octet (car un booléen est stocké dans un octet et non pas dans un bit)
char b;
//ainsi pour donner la valeur du 1er booléen, on fera:
faux: b &= 254;
vrai: b |= 1;
//le second:
faux: b &= 253;
vrai: b |= 2;
//le troisieme:
faux: b &= 251;
vrai: b |= 4;
//le nieme:
faux: b &= 255-2^(n-1);
vrai: b |= 2^(n-1);

et pour récuperer la valeur du premier
val=b&1;
le second :
val=b>>1 & 1=true;
le 3eme :
val=b>>2 & 1=true;
le nieme :
val=b>>(n-1) & 1=true;
Possibilité d'étendre cette astuce à un tableau de char au lieu d'un tableau de booléens, cela reduit la taille de 8.
  

3.5. Mathematiques



trouver rapidement si un nombre entier est pair revient à savoir si son bit de poids faible est faux donc
pair=i&1;


On essayera de calculer les sinus et cosinus le moins de fois possible car les appels de fonctions sont très lourds.
On calculera donc sin(a) et on le stocke dans une variable qui sera utilisé plus tard.


Voir meme, lors d'un calcul cyclique avec des sinus et cosinus, on preferera stocker les differentes valeurs dans un tableau.
Exemple:
On a besoin de connaitre tous les cosinus des angles, au lieu de faire cos(angle) on fera tab[angle] ou tab sera un tableau initialisé avec toutes les valeurs des cosinus des angles.


  

4. Orientations et état d'esprit

Il faut minimiser le nombre d'appels de fonction (c'est pas pour ca qu'il faut tout mettre dans une fonction), surtout lorsque l'on effectue beaucoup de fois une fonction.
Simplifier et optimiser les fonctions appellées souvent, voir même essayer de les coder en assembleur si possible.
Pour les gros objets, lors des passages en paramêtre, on essayera tant que possible de les passer par référence (comme ca le compilo n'est pas obligé de tout dupliquer)
Exemple:
void consulter(DataBase & a){...}
...
DataBase a;
consulter(a);
...


Lors de la création d'algorithmes, essayez, avant de trouver l'algo, de vous dire combien d'actions vous avez à faire et vous y tenir(voir faire moins si possible).


Ne soyez pas avare en ligne de code, souvent l'optimisation demandera plus de lignes de code.
  

5. Les Pointeurs Mobiles

Vous en avez beaucoup entendu parler, ils vous font froid dans le dos, ... les voici:

Le principe du pointeur mobile: il est utilisé dans les tableaux, lors d'un parcours linéaire - c'est à dire lorsque on veut parcourir tout le tableau - et au lieu à chaque fois d'indexer pour recuperer la valeur à un endroit donné dans le tableau, on aura une adresse qui pointe sur la valeur directement.
Un exemple s'impose:
j'ai un tableau sur lequel je fait des opérations,
for(unsigned int i(0);i<taille;i++){
    action(tab[i]);
}
on remplacera par (et en utilisant des techniques déja utilisées avant):
unsigned int i(taille);
//en supposant que c'est un tableau de T
T * pointeur_mobile=tab;
while(i--){
action(*(pointeur_mobile++));
}
Ainsi pour un tableau à plusieurs dimensions: au lieu de :
for(unsigned int ligne(0);ligne<nbligne;ligne++)
    for(unsigned int colonne(0);colonne<nbcolonne;colonne++)
        action(tab[ligne][colonne]);
on aura:
unsigned int i(nbligne*nbcolonne);
T * pointeur_mobile=tab;
while(i--)
action(*(pointeur_mobile++));