Voici quelques algorithmes pratiques que j'ai découvert en cours d'informatique, dans des livres, et/ou que j'ai mis au point moi-même par nécessité. Ces algorithmes sont optimisés et remplacent avantageusement leur équivalent en solution immédiate.
Leurs implémentations en C++ sont données.
L'exponentiation rapide
L'algorithme classique pour calculer a^n et une boucle for qui multiplie n fois le résultat initialisé à 1 par a. Sa complixité est donc en N.Le principe de l'algorithme proposé est de restreindre le nombre de multiplications, en considérant la représentation binaire de n.
Dans une variable on stocke au début a, puis à chaque boucle on la met au carré (elle contient donc successivement a, a^2, a^4, a^8 ...) et si l'écriture binaire de n contient à 1 à l'emplacement considéré, on multiple le résultat par a.
Voici l'algorithme :
__int64 Power64(__int64 base, unsigned exposant)
{
unsigned __int64 a = base, res = 1; unsigned n = exposant;
while (n > 0)
{
if (n % 2 == 1) res = res * a;
n = n / 2;
a *= a;
}
return res;
}
Exemple : exposant = 13 = 1101b
- initialisation: a = base, N = 13, R = 1
- fin étape 1 : a = base^2, n = 6, res = base
- fin étape 2 : a = base^4, n = 3, res = base
- fin étape 3 : a = base^8, n = 1, res = base^5
- fin étape 4 : a = base^16, n = 0, res = base^13
Recherche rapide de motifs et tampons cycliques
Je me suis basé sur l'idée de Boyer-Moore pour réaliser cet algorithme. L'idée de base est de comparer le dernier caractère du motif, et par exemple si l'octet correspondant dans le tampon n'apparait nulle part dans le motif, on peut se décaler complètement après cet octet et ainsi économiser autant de comparaisons que la taille du motif.J'ai donc utilisé à fond cette idée pour concevoir l'algorithme suivant :
int recherche(unsigned char *motif, int tmotif, unsigned char *buffer, int tbuffer)
{
// préparation qui peut se faire une seule fois pour le motif en dehors
int occurrences[256];
for(int i = 0; i < 256; i++)
occurrences[i] = -1;
for(int i = 0; i < length; i++)
if (occurrences[motif[i]] == -1)
occurrences[motif[i]] = i;
//algorithme de recherche
int i = length-1, j, k;
while (i < size)
{
for(j = length-1, k = i; buffer[k] == motif[j]; j--, k--)
if (j == 0) return k;
if (occurrences[buffer[k]] > j)
i += j+1;
else i += j - occurrences[buffer[k]];
}
return -1;
}
Bien sûr les performances de ce type de recherche dépend toujours fortement des données, et il est possible que pour certaines données particulières les performances de cet algorithme soient inférieures à celle de l'algorithme classique qui consiste à comparer à chaque position le motif aux octets suivant du tampon, mais c'est le cas général qu'il faut regarder, et cet algorithme effectue très souvent moins de comparaison, au mieux il divise ce nombre par la taille du motif.
Attention cependant, car si les données sont lentes à obtenir (sur un disque dur par exemple), le temps de recherche peut se retrouver négligeable devant le temps d'accès aux données, et toute optimisation de la recherche est donc inutile. Cet algorithme est donc intéressant surtout si les données se trouvent par exemple en mémoire vive, ou si les octets sont obtenus un par un car on économise alors des lectures (attention, sur un disque dur la lecture de blocs et beaucoup plus rapide que la lecture octet par octet, car windows et le dos prennent du temps pour effectuer la commande de lecture).
Permutation d'un tableau
Je propose ici un algorithme en N permettant de permuter un tableau à l'aide d'un générateur de nombres aléatoires. Il est simplement bien pensé pour éviter l'idée première de redemander un nombre aléatoire jusqu'à ce qu'on en est un que l'on a pas encore eu ...Il s'agit simplement demander quel indice on va placer en dernier, puis en avant dernier réduisant à chaque fois l'intervalle du générateur de nombres aléatoires.
void permute(int *tableau, int taille)
{
for(int i = 0; i < taille; i++)
{
int index = random(taille-i);
int tmp = tableau[taille-i-1];
tableau[taille-i-1] = tableau[index];
tableau[index] = tmp;
}
}