Recherche de mots dans une table
Description
Voici la comparaison de deux fonctions qui recherche
un mot parmis d'autres qui sont dans un tableau.
Pour ce qui est de la difference de performance,
je vous laisse juge => regardez le fichier excel !
J'espere qu'il y a assez de commentaire ...
un mot parmis d'autres qui sont dans un tableau.
Pour ce qui est de la difference de performance,
je vous laisse juge => regardez le fichier excel !
J'espere qu'il y a assez de commentaire ...
Source / Exemple :
#include <stdio.h> // printf
#include <conio.h> // getch
#include <string.h> // strcmp
#include <windows.h> // GetTickCount
//-----------------------------------------------------
// plus la valeur sera elevee,
// plus la precision sera bonne
#define PRECISION 10000
//-----------------------------------------------------
typedef struct TagMYWORD
{
const char *name;
const char *about;
}MYWORD,*P_MYWORD;
//-----------------------------------------------------
// exemple de mot avec des noms de fonction
MYWORD tabWord[] =
{
{ "abs", "Valeur absolue" },
{ "cos", "Cosinus" },
{ "exp", "Expodentielle" },
{ "fact", "Factorielle" },
{ "ln", "Logarithme neperien" },
{ "log2", "Logarithme en base 2" },
{ "log10", "Logarithme en base 10" },
{ "pgcd", "Plus Grand Commun Diviseur" },
{ "power", "Elevation a la puissance" },
{ "ppcm", "Plus Petit Commun Multiple" },
{ "random", "Hasard" },
{ "sin", "Sinus" },
{ "sqrt", "Racine carree" },
{ "tan", "Tangante" },
{ "za", "" },
{ "zb", "" },
{ "zc", "" },
{ "zd", "" },
{ "ze", "" },
{ "zf", "" },
{ "zg", "" },
{ "zh", "" },
{ "zi", "" },
{ "zj", "" },
{ "zk", "" },
{ "zl", "" },
{ "zm", "" },
{ "zn", "" },
{ "zo", "" },
{ "zp", "" },
{ "zq", "" },
{ "zr", "" },
{ "zs", "" },
{ "zt", "" },
{ "zu", "" },
{ "zv", "" },
{ "zw", "" },
{ "zx", "" },
{ "zy", "" },
{ "zz", "" },
{ "zza", "" },
{ "zzb", "" },
{ "zzc", "" },
{ "zzd", "" },
{ "zze", "" },
{ "zzf", "" },
{ "zzg", "" },
{ "zzh", "" },
{ "zzi", "" },
{ "zzj", "" },
{ "zzk", "" },
{ "zzl", "" },
{ "zzm", "" },
{ "zzn", "" },
{ "zzo", "" },
{ "zzp", "" },
{ "zzq", "" },
{ "zzr", "" },
{ "zzs", "" },
{ "zzt", "" },
{ "zzu", "" },
{ "zzv", "" },
{ "zzw", "" },
{ "zzx", "" },
{ "zzy", "" },
{ "zzz", "" },
{ "zzza", "" },
{ "zzzb", "" },
{ "zzzc", "" },
{ "zzzd", "" },
{ "zzze", "" },
{ "zzzf", "" },
{ "zzzg", "" },
{ "zzzh", "" },
{ "zzzi", "" },
{ "zzzj", "" },
{ "zzzk", "" },
{ "zzzl", "" },
{ "zzzm", "" },
{ "zzzn", "" },
{ "zzzo", "" },
{ "zzzp", "" },
{ "zzzq", "" },
{ "zzzr", "" },
{ "zzzs", "" },
{ "zzzt", "" },
{ "zzzu", "" },
{ "zzzv", "" },
{ "zzzw", "" },
{ "zzzx", "" },
{ "zzzy", "" },
{ "zzzz", "" },
{ "zzzza", "" },
{ "zzzzb", "" },
{ "zzzzc", "" },
{ "zzzzd", "" },
{ "zzzze", "" },
{ "zzzzf", "" },
{ "zzzzg", "" },
{ "zzzzh", "" },
{ "zzzzi", "" },
{ "zzzzj", "" },
{ "zzzzk", "" },
{ "zzzzl", "" },
{ "zzzzm", "" },
{ "zzzzn", "" },
{ "zzzzo", "" },
{ "zzzzp", "" },
{ "zzzzq", "" },
{ "zzzzr", "" },
{ "zzzzs", "" },
{ "zzzzt", "" },
{ "zzzzu", "" },
{ "zzzzv", "" },
{ "zzzzw", "" },
{ "zzzzx", "" },
{ "zzzzy", "" },
{ "zzzzz", "" },
{ "zzzzza", "" },
{ "zzzzzb", "" },
{ "zzzzzc", "" },
{ "zzzzzd", "" },
{ "zzzzze", "" },
{ "zzzzzf", "" },
{ "zzzzzg", "" },
{ "zzzzzh", "" },
{ "zzzzzi", "" },
{ "zzzzzj", "" },
{ "zzzzzk", "" },
{ "zzzzzl", "" },
{ "zzzzzm", "" },
{ "zzzzzn", "" },
{ "zzzzzo", "" },
{ "zzzzzp", "" },
{ "zzzzzq", "" },
{ "zzzzzr", "" },
{ "zzzzzs", "" },
{ "zzzzzt", "" },
{ "zzzzzu", "" },
{ "zzzzzv", "" },
{ "zzzzzw", "" },
{ "zzzzzx", "" },
{ "zzzzzy", "" },
{ "zzzzzz", "" }
};
//-----------------------------------------------------
// le principe est celui de la dichotomie :
// on coupe en deux le tableau <tabWord>, on tombe sur un mot
// Si celui-ci est celui recherche, BINGO on l'a trouve
// Sinon on regarde le signe de la comparaison, pour
// voir si le resutat est au-desus ou en-desous du mot
// Apres on recommence avec le tableau representer
// par le bloc du dessus ou le bloc du dessous, qui
// a pour taille la taille du grand tableau diviser par deux
// Ainsi de suite jusqu'a que l'on trouve le mot, ou que
// la taille du tableau soit 1
//
// Cet algorithme revient a faire :
// On prend le plus haut bit a 1
// Soit <r> le resultat, i.e. la position du resultat
// On regarde si le meme bit de <r> doit etre ou non a 1
// Pour cela on compare <word> avec le mot situe a la moitie
// du tableau :
// si le mot cherche se trouve au dessus => le bit est a 0
// si le mot cherche se trouve au dessous => le bit est a 1
// Apres on suit la meme logique avec le bit se situant
// a gauche, donc on fait f>>=1 ,f ayant le bit voulu a 1
// Ainsi de suite, on va regarde si le bit n, puis n-1,
// puis n-2, ... puis le bit 0 doit etre a 1 ou a 0
//
//
// N.B. : on peut faire cet algorithme par reccurrence !
//
P_MYWORD SearchWordQuick(P_MYWORD tab,int nbWord,const char *word)
{
// flag
int f;
// resulat
int r;
if(nbWord <= 0)
{
// si <nbWord> vaut des valeurs farfelues ...
return NULL;
}
// calcul de <f>
// <f> vaut le bit, le plus haut a 1 de <nbWord>, a 1, suivi de zeros (0)
// exemples : nbWord=1001 => f=1000
// nbWord=1011101 => f=1000000
f = 1;
while((f<<=1) < nbWord); // attention ici un point-virgule !
// on a fait 'f<<=1' une fois de trop
// donc on va compenser
f>>=1;
// initialisation de <r>
r = 0;
do
{
// signe de la comparaison
int s;
// on met a 1 le bit represente par <f>
// ensuite on va regarder s'il faut le garder ou pas !
// tel est l'algorithme ...
r += f;
// si <r> n'est pas dans les limites du tableau
if(r >= nbWord)
{
// <r> est trop grand
// on enleve le bit mit de trop au-dessus
// le resultat potentiel ce touve forcement
// plus haut dans le tableau
r -= f;
}
else
{
// on compare les deux chaines
s = strcmp(word,(tab + r)->name);
// si on a trouve la bonne chaine ! ... BINGO !
if(s == 0)
{
// on retourne le pointeur sur la structure
// MYWORD, donc on fait un peu d'arithmetique
// de poiteurs
return tab + r;
}
else if(s < 0)
{
// <r> est trop grand
// on enleve le bit mit de trop au-dessus
// le resultat potentiel ce touve forcement
// plus haut dans le tableau
r -= f;
}
}
}while(f >>= 1);
// ici on arrive sur les mots 'les plus loin'
// on sais que s'il ce n'est pas celui-ci,
// il n'existe pas dans le tableau
return strcmp(word,(tab + r)->name)
?
(NULL) // n'existe pas dans le tableau
:
(tab + r); // existe dans le tableau
}
//-----------------------------------------------------
// algorithme le plus simple possible, mais aussi le plus
// bourrin possible aussi !
// on teste le chaine une par une ...
P_MYWORD SearchWordSlow(P_MYWORD tab,int nbWord,const char *word)
{
// indice pour balayer tous les mots
int i;
//les valeurs farfelues seront gerer par la boucle
// 'for', i.e. aucune iteration
for(i=0;i<nbWord;i++)
{
if(strcmp(tab->name,word))
{
// si <word> different de la chaine du tableau
// alors on passe a la chaine suivante.
// encore un peu d'arithemtique de pointeurs ...
tab ++;
}
else
{
// si on a trouve le mot, BINGO !
// il suffit de retourner <tab>
return tab;
}
}
// si apres la boucle de toutes les chaines existantes
// on n'a rien trouve, alors c'est que le mot <word>
// n'existe pas dans le tableau
return NULL;
}
//-----------------------------------------------------
int main(int argc,char **argv)
{
// nombre de mot dans le tableau
int nbWord;
// nombre courant de mot
int i;
// calcul du nombre de mot dans le tableau
nbWord = sizeof(tabWord)/sizeof(tabWord[0]);
// on fais une comparaison en fonction
// du nombre de mot dans le tableau
for(i=0;i<=nbWord;i++)
{
// nombre d'iteration
int j;
// GetTickCount (gtc)
DWORD gtcBeforeSlow, // temps avant le calcul
gtcAfterSlow; // temps apres le calcul
DWORD gtcBeforeQuick, // temps avant le calcul
gtcAfterQuick; // temps apres le calcul
//**********************************************************
//* SLOW *
//**********************************************************
gtcBeforeSlow = GetTickCount();
// on fais les testes <PRECISION> fois
// pour avoir une meilleur precision au niveau
// du <GetTickCount>
for(j=0;j<PRECISION;j++)
{
// voici tout les testes que l'on va faire :
// * la recherche de tout les mots existants
// * la recherche de mot non-existants
// indice, qui va balayer tous les mots existants
int k;
// les mots existants
for(k=0;k<i;k++)
{
SearchWordSlow(tabWord,i,(tabWord + k)->name);
}
// les mots inexistants
SearchWordSlow(tabWord,i,"coucou");
SearchWordSlow(tabWord,i,"toto");
SearchWordSlow(tabWord,i,"hello world !");
SearchWordSlow(tabWord,i,"tan_");
SearchWordSlow(tabWord,i,"abs_");
}
gtcAfterSlow = GetTickCount();
//**********************************************************
//* QUICK *
//**********************************************************
gtcBeforeQuick = GetTickCount();
// on fais les testes <PRECISION> fois
// pour avoir une meilleur precision au niveau
// du <GetTickCount>
for(j=0;j<PRECISION;j++)
{
// voici tout les testes que l'on va faire :
// * la recherche de tout les mots existants
// * la recherche de mot non-existants
// indice, qui va balayer tous les mots existants
int k;
// les mots existants
for(k=0;k<i;k++)
{
SearchWordQuick(tabWord,i,(tabWord + k)->name);
}
// les mots inexistants
SearchWordQuick(tabWord,i,"coucou");
SearchWordQuick(tabWord,i,"toto");
SearchWordQuick(tabWord,i,"hello world !");
SearchWordQuick(tabWord,i,"tan_");
SearchWordQuick(tabWord,i,"abs_");
}
gtcAfterQuick = GetTickCount();
//**********************************************************
//* RESULATS *
//**********************************************************
printf(
"%4d mot(s) : Slow = %6ld Quick = %6ld\n",
i,
gtcAfterSlow - gtcBeforeSlow,
gtcAfterQuick - gtcBeforeQuick
);
}
printf("Appuyer sur une touche pour quitter le programme...");
getch();
return 0;
}
Codes Sources
A voir également
- Recherche de mots dans une table
- Php table - Conseils pratiques -PHP
- Melangeur de mots - Forum VB.NET
- Mélangeur de mots - Forum C
- Melangeur de mot ✓ - Forum Visual Basic
- Melanger les lettres d'un texte - Forum PHP
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.