Optimisation de comparaison de chaines

Version imprimable

Voir 40 message(s) de cette discussion en une page

Bonjour à tous,

actuellement j'ai un code structuré ainsi:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
for(i....)
{
    for(k...)
    {
                                if(strcmp(paramName,"val1")==0)
				{
					TAB[k]=(float)Obj->val1[k];
				}
				else if(strcmp(paramName,"val2")==0)
				{
					TAB[k]=(float)Obj->val2[k];
				}
				else if(strcmp(paramName,"val3")==0)
				{
					TAB[k]=(float)Obj->val3[k];
				}
				else if(strcmp(paramName,"val4")==0)
				{
					TAB[k]=(float)Obj->val4[k];
				}
				else if(strcmp(paramName,"val5")==0)
				{
					V_TAB[k]=(float)Obj->val5[k];
				}
                                etc..etc..
 
    }
}

Sachant que la liste de strcmp est bcp plus longue, y aurait-il pas un moyen d'optimiser cela car le traitement est vraiment long sachant qu'on fait tjrs appelle à l'attribut de l'Obj, qui est strictement égale au paramName

Merci d'avance pour vos réponses

17/11/2010, 10h22
Steph_ng8

Bonjour.

Pour commencer, une petite question : tu fais du C ou du C++ ?
Là, c'est du code C que je vois…
Si c'est le cas, tu peux éventuellement créer une structure pour stocker à la fois le nom du paramètre et sa valeur, et utiliser un tableau de ces structures pour les représenter dans ton objet.
Ça fera une sorte de « map »…
Ensuite, au lieu de faire cette liste de « strcmp », tu recherches dans ton « map » le nom du paramètre adéquat (à l'aide de « bsearch », par exemple), et tu auras directement accès au champ que tu veux modifier.

Honnêtement, ça ne changera pas grand chose pour ton programme, il fera tout autant de comparaisons de chaînes.
Par contre, ton code sera beaucoup plus concis. ;)

Si tu veux vraiment faire du C++, en revanche, tu n'as peut-être pas la bonne approche.
Déjà, utilise les « std::string », et fais un switch !
Euh en fait non, le code sera tout aussi lourd… :D

Plus sérieusement, la meilleure idée qui me vient est d'utiliser un « std::map » (et les « std::string »).
Mais c'est peut-être une structure un peu lourde pour ce que tu veux faire.
Alors tu peux également utiliser l'astuce que je donne au-dessus, avec d'autres fonctions de recherche, comme « std::find ».

Ah, et pour parcourir les conteneurs, les itérateurs, il n'y a que ça de vrai… :P
(Pour les tableaux aussi, d'ailleurs… :roll:)
17/11/2010, 10h34
rockt13

Salut merci pour ta réponse, c'est en effet du c++

En utilisant un switch sur des string, le code sera aussi lourd, mais est-ce que cela signifie que le traitement sera aussi long ?

Car moi c'est au niveau du traitement que je veux optimiser
17/11/2010, 10h42
ram-0000

Peut être que tu peux imaginer une solution à base de hash si la liste des chaines de caractères à tester est vraiment très longue.

Déjà, un tableau de structure qui contient les chaines et les hash de ces chaines. Le hash est à calculer une fois (hors du programme) pour créer des données statiques.

Ensuite quand tu rentres dans ta fonction de recherche, tu calcules le hash de ta string, tu regardes dans ton tableau statique toutes les strings qui ont le même hash (c'est une comparaison de nombres, cela devrait aller plus vite) et ensuite, tu n'a plus que quelques comparaisons de chaines à faire en cas de collision de hash.

La difficulté dans cette approche est de trouver une fonction de hash sans trop de collisions par rapport à tes strings attendues et ensuite de créer le tableau de données statiques.

Bonjour Raymond,

J'ai plus de 50 chaines à tester, sachant que j'itère environs 100 fois
L'idée du Hash me semble pas mal, mais je n'arrive pas à savoir comment je peux directement appelé le bon attribut par la suite exemple:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 maMap[hash(val1)]=(float)Obj->val1[k]; maMap[hash(val2)]=(float)Obj->val2[k]; maMap[hash(val3)]=(float)Obj->val3[k]; paramName="val2"; for (k....) { if(maMap[hash(paramName)]) { TAB[k]=maMap[hash(paramName)]; } }
ça serait un truc dans le genre?

Bonjour,

Si tes chaines de caractères sont de type "val1", "val2"... tu peux tenter lire d'analyser le contenu de la chaine plutôt que de comparer :

Code:

1
2
3
4
5
6
 
if(strcmp(paramName,"val1")==0) {
 
} else if(strcmp(paramName,"val2")==0) {
 
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
int index;
if(1 == sscanf(paramName, "val%d", &index)) {
    switch(index) {
          case 1 :
        TAB[k]=(float)Obj->val1[k];
        break;
 
          case 2 :
        TAB[k]=(float)Obj->val2[k];
        break
        /* ... */
    }
} else {
    /* paramName n'est pas de forme "val%d"*/
}

17/11/2010, 11h30
rockt13

En fait non, mes chaines, ne sont pas du genre "val1" , "val2" mais plutôt du genre
"toto", "titi" , "var" etc...
17/11/2010, 12h53
rockt13
L'idéal serait de faire comme en python, exécuter directement une commande

Si je reçois "paramName" faire un truc du genre :
Code:

1 2 exec("HTAB[k]=(float)Obj->%s[k]" % paramName)
Mais je crois que quelque chose d'équivalent n'existe pas en C++ ?
17/11/2010, 12h59
Steph_ng8
Citation:

Envoyé par rockt13

En utilisant un switch sur des string, le code sera aussi lourd, mais est-ce que cela signifie que le traitement sera aussi long ?

En fait, oui.
La structure de contrôle « switch » n'est rien d'autre qu'une simplification d'écriture, et au final les traitements sont pratiquement les mêmes.
Les différences principales entre un « switch » et une suite de « if … then … else » sont :
- l'expression à tester n'est évaluée qu'une seule fois ;
- les valeurs de comparaison sont obligatoirement des constantes ;
- la fonction de comparaison est forcément l'opérateur « == ».
Comparer deux std::string avec l'opérateur == ou comparer deux char* avec strcmp() revient exactement au même en interne.
Donc toutes les méthodes que je t'ai données ne retirent pas toutes ces comparaisons, elles ne font que les masquer.
Mais tu peux optimiser la recherche en triant les chaînes de caractères par ordre lexicographique croissant (indispensable pour utiliser bsearch(), et comportement normal des std::map).

Mais si tu veux encore accélérer la recherche, je crois que le mieux est d'associer un nombre à chaque chaîne : une comparaison sur des nombres est beaucoup plus rapide que sur des chaînes.
Le plus évident est probablement de passer par une fonction de hachage, et là on revient sur ce que proposait ram-0000.
17/11/2010, 13h05
Steph_ng8
Citation:
Envoyé par rockt13

L'idéal serait de faire comme en python, exécuter directement une commande

Si je reçois "paramName" faire un truc du genre :

Code:

1 2 exec("HTAB[k]=(float)Obj->%s[k]" % paramName)

Mais je crois que quelque chose d'équivalent n'existe pas en C++ ?
Non.
Pas à ma connaissance en tout cas.

PS: Comment effectuer une conversion de type explicite (cast) ?
17/11/2010, 13h21
guillaume07

Citation:

Envoyé par Steph_ng8

Bonjour.

Pour commencer, une petite question : tu fais du C ou du C++ ?
Là, c'est du code C que je vois…

modulo qu'il est tout à fait correct d'utiliser la libC intégrer à la biblio du C++ (qui est une version arrangée de la libC) .

Pour le "switch-on-string-litteral", l'optimisation la plus classique consiste à faire un premier élagage sur la taille, c'est à dire remplacer :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 if(strcmp(paramName,"toto")==0) { TAB[k]=(float)Obj->toto[k]; } else if(strcmp(paramName,"bar")==0) { TAB[k]=(float)Obj->bar[k]; } else if(strcmp(paramName,"a")==0) { TAB[k]=(float)Obj->a[k]; } else if(strcmp(paramName,"foo")==0) { TAB[k]=(float)Obj->foo[k]; } ...
par
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 int size = strlen(paramName); switch(size) { case 1: { if(strcmp(paramName,"a")==0) { TAB[k]=(float)Obj->a[k]; } break; } case 3: { if(strcmp(paramName,"foo")==0) { TAB[k]=(float)Obj->foo[k]; } else if(strcmp(paramName,"bar")==0) { TAB[k]=(float)Obj->bar[k]; } break; } case 4: { if(strcmp(paramName,"toto")==0) { TAB[k]=(float)Obj->toto[k]; } break; } }
Mais bon, cette optimisation me semble esquiver le vrai problème qui est : On ne s'amuse généralement pas à faire des montagnes de comparaison de string au beau milieu d'une double-boucle critique. :mrgreen:

Dans le code original, pourquoi paramName est-il une string ? J'ai du mal à imaginer une justification pertinente :koi:

17/11/2010, 14h26
rockt13

Salut merci pour ta réponse.

paramName, est un paramètre provenant de la couche Python vers le noyau C++.

Pourquoi ne devrait-il pas être une chaine de caractères?

est ce que l'idée du Hachage donné plus haut pourrait fonctionner de la sorte.

j'initialise un tableau contenant tous mes HASH

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
double *TAB_HASH = NULL;
TAB_HASH = new double[50];
 
//Je créer les hash correspondants à chaque paramètres possibles
TAB_HASH[0]=hash("param1");
TAB_HASH[1]=hash("param2");
TAB_HASH[2]=hash("toto");
etc..
 
//je fais un switch sur les hash
for(k...)
{
      switch(hash(paramName))
      {
            case TAB_HASH[0]: TAB[k]=(float)Obj->param1[k];
                                        break;
            case TAB_HASH[1]: TAB[k]=(float)Obj->param2[k];
                                        break;
            case TAB_HASH[2]: TAB[k]=(float)Obj->toto[k];
                                        break;
 
           etc...
       }
}

Qu'en pensez vous ?

Salut,

Si tu as un nombre fini de chaines de caractères intervenant dans ParanName (ce qui semble être le cas), mais que tu en accepte un nombre plus ou moins infini, tu peux envisager de tester tous les parametres l'un à la suite de l'autre et de leur donner une valeur en fonction de la chaine de caractères rencontrées.

Cela pourrait se faire sous la forme de
Code:

1 2 3 4 5 6 7 8 9 10 std::string const paramNamesString[]={"toto","tata","titi","var","brol","truc" /*... */}; int maxNameStrings = /* le nombre de chaines de caractères envisagées int indexOfString(std::string const & s) { int ret=0; while(ret<maxNameStrings && s.find(paramNamesString[ret])==std::string::npos) ++ret; return ret; };
Tu pourrais placer l'indice ainsi obtenu dans un tableau d'entiers, qui irait très bien pour la cause:
Code:

1 2 3 4 5 6 7 8 9 10 11 int main(int argc, char *argv[]) { std::vector<int> tab; if(argc>1) // si l'on a introduit des arguments { // on les passe tous en revue for(int i=1;i<argc;++i) tab.push_back(indexOfString(argv[i]); } }
Il n'y a plus par la suite qu'à parcourrir ce vecteur et de décider quoi faire ;)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 template <typename iterator> void useParams(iterator b, iterator e) { while(b!=e) { swich(*b) { case 0: /* si c'était "toto" */ break case 1: /* si c'était "tata" */ break case 2: /* si c'était "titi" */ break /*... */ default : /* si ce n'était aucune des chaines envisagées */ } ++b; } }
(NOTA: j'ai créé une fonction template pour ne pas être limité à l'utilisation d'un vecteur ;))

Et cette fonction, tu l'insère à ta guise dans une boucle "classique":
Code:

1 2 for(int i=...) useParams(tab.begin(), tab.end());
Et le tour est joué :D

Tu auras un "temps de latence" avant le lancement de la boucle principale (le for(int i = ...) parce qu'il faudra, quoi qu'il arrive, comparer l'ensemble des arguments passés à potentiellement la totalité des chaines de caractères envisagées, mais cela accélérera fortement ta boucle principale (toujours le for (int i=...) ) parce que tu te contentera de comparer des entiers entre eux, ce qui est particulièrement rapide ;)

N'oublie pas que l'on passe 90% du temps dans 10% du code... ici, la comparaison des paramètres se trouve tout à fait en dehors des 10% "critiques" :D

EDIT: si tu dois compter le nombre de fois que titi, tata ou brol est utilisé, il est très facile de rajouter un compteur dans l'histoire :D

17/11/2010, 15h39
Steph_ng8

Citation:

Envoyé par guillaume07

modulo qu'il est tout à fait correct d'utiliser la libC intégrer à la biblio du C++ (qui est une version arrangée de la libC) .

Je n'ai jamais dit le contraire.
Seulement si on fait du C++, autant utiliser les outils fournis par le C++… non ?

Citation:
Envoyé par rockt13
est ce que l'idée du Hachage donné plus haut pourrait fonctionner de la sorte.

j'initialise un tableau contenant tous mes HASH
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 double *TAB_HASH = NULL; TAB_HASH = new double[50]; //Je créer les hash correspondants à chaque paramètres possibles TAB_HASH[0]=hash("param1"); TAB_HASH[1]=hash("param2"); TAB_HASH[2]=hash("toto"); etc.. //je fais un switch sur les hash for(k...) { switch(hash(paramName)) { case TAB_HASH[0]: TAB[k]=(float)Obj->param1[k]; break; case TAB_HASH[1]: TAB[k]=(float)Obj->param2[k]; break; case TAB_HASH[2]: TAB[k]=(float)Obj->toto[k]; break; etc... } }
Qu'en pensez vous ?
En théorie, si ta fonction de hachage retourne une valeur différente pour chaque chaîne considérée (donc pas de collision), ça fonctionnera.
Si tu es amené à générer un hash pour une chaîne non prévue, c'est un autre problème…

Mais ce bout de code ne compilera pas.
Comme je le disais plus haut, il ne peut y avoir que des constantes dans les « case ».
Et, jusqu'à preuve du contraire, un élément d'un tableau n'est pas considéré comme une constante.

En effet je viens de tester et il ne compile pas à cause des cases non constants..

Slt , koala01
si j'ai bien compris ton idée consiste à affecter un identifiant unique pour chaque paramètres dans un tableau d'entier => tab
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 //on se retrouve avec un string tab comme cela paramNamesString[0]="toto" paramNamesString[1]="tata" paramNamesString[2]="titi" etc.. //on se retrouve avec un int tab comme cela tab[0]=0; tab[1]=1; tab[2]=2; //Boucle sur tous les objets pour récupérer les valeurs for(k..) { // C'est ici que je ne comprend pas comment utiliser useParam(debut,fin) ? // car à ce stade je dispose de paramName="tata" et je souhaites //exécuter TAB[k]=(float)Obj->tata[k] }

Citation:

Envoyé par rockt13

Slt , koala01
si j'ai bien compris ton idée consiste à affecter un identifiant unique pour chaque paramètres dans un tableau d'entier => tab

Non.
On affecte directement à chaque paramètre l'indice de la chaîne correspondante dans le tableau des chaînes.
On le fait pour tous les paramètres, une fois pour toute au début du programme, avant d'essayer de faire le moindre traitement sur les paramètres.
Une fois que c'est fait, on peut effectuer les opérations intrinsèques à chaque paramètre, en une seule passe.
(Donc deux passes en tout.)

Je vais prendre un exemple pour être plus clair.
Imaginons que l'on a les paramètres suivants, dans l'ordre :
toto param3 tutu titi param1 tutu
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 std::string const paramNamesString[] = {"param0", "param1", "param2", "param3", "param4", "tata", "titi", "toto", "tutu"}; int maxNameStrings = 9; // Inspection des paramètres (...) /* À la sortie on obtient : * tab[0] = 7; | "toto" * tab[1] = 3; | "param3" * tab[2] = 8; | "tutu" * tab[3] = 6; | "titi" * tab[4] = 1; | "param1" * tab[5] = 8; | "tutu" */ // On peut maintenant effectuer les traitements spécifiques à chaque paramètre useParams(tab.begin(), tab.end());

Citation:

Envoyé par koala01

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typenamen iterator
void useParams(iterator b, iterator e)
{
    while(b!=e)
    {
        swich(*b)
        {
             case 0:
                 /* si c'était "toto" */
                 break
             case 1:
                 /* si c'était "tata" */
                 break
             case 2:
                 /* si c'était "titi" */
                 break
             /*... */
             default :
                 /* si ce n'était aucune des chaines envisagées */
        }
        ++it;
    }
}

Je ne sais pas pour toi, mais chez moi les variables qui se déguisent pour se faire passer pour un autre, ça ne passe pas. :roll:
Il faudrait dire à « b » que cela ne sert à rien de se prendre pour « it », ou l'inverse ; ça se remarque tout de suite.
(ou pas…)

Voir 40 message(s) de cette discussion en une page