Optimiser une fonction C++Résolu

Question

Salut, J'aimerais savoir comment optimiser une de mes fonctions (trop gourmande à mon gout). Elle ne représente qu'une petite partie de mon projet mais le rend bien bancal à cause de son temps d'execution. Le projet : J'ai plusieurs cv::Rect qui representent, seul ou à plusieurs, une ligne de caractère sur une image. J'ai créer un arbre qui me donne toute les possibilités de link d'un Rect avec un autre (une petite heuristique me permet de choisir etc...). 'casesVect' contient tous les chemins entre la racine et chaque feuille de l'arbre (list pour tous les cas, vect pour stocker un cas). C'est ici qu'intervient 'sortCases'. Cette fonction me permet de diviser un cas en X cas sous une certaine condition (donc de créer X nouveau cas). Cette condition est que deux Rect (ou plus) soit linkés à un même Rect. (petit dessin ): RECT A-----------RECT C .........____--- ....___--- RECT B-----------RECT D Ici, A et B sont link avec C. De ce cas doit en sortir 2; A->C,B->D et B->C. Bien sur, puisqu'un malheur n'arrive jamais seul, lors de l'execution, ces fonctions sont de plus en lente à s'executer. Je n'ai pas de fuite mémoire et mon CPU block à 100%. Si vous avez le pourquoi du comment je prend aussi ;D Merci d'avance !!! Je travaille sous mac en utilisant la lib opencv. PS : Je sais pas vraiment si je suis dans la bonne section void ReceiptSection::sortCases(const std::list >& casesVect, std::list >& newCasesVect) { int cptCase=1; std::list > tmpCases; for (std::list >::const_iterator casesIt=casesVect.begin(); casesIt!=casesVect.end(); ++casesIt, cptCase++) { std::map scores; std::vector::const_iterator mainCaseIt=(*casesIt).begin(); // The first node is the root and don't have any block or line ++mainCaseIt; LOG("---------------- For case " << cptCase << " : ", 4); // calculates the number of times the block is matched for (std::vector::const_iterator aCaseIt=mainCaseIt; aCaseIt!=(*casesIt).end(); ++aCaseIt) { scores[(*aCaseIt)->block] = 0; } for (std::vector::const_iterator aCaseIt=mainCaseIt; aCaseIt!=(*casesIt).end(); ++aCaseIt) { scores[(*aCaseIt)->block] += 1; } for (std::map::iterator scoresIt=scores.begin(); scoresIt!=scores.end(); ++scoresIt) { if ((*scoresIt).second > 1) // nbMatch == 1 means that no division is needed { divideCase(*casesIt, (*scoresIt).first, (*scoresIt).second, tmpCases); } else { tmpCases.push_back(*casesIt); } // Verifies if the new cases already are in casesVect and push them in if necessary for (std::list >::iterator tmpIt=tmpCases.begin(); tmpIt!=tmpCases.end(); ++tmpIt) { bool verif = false; for (std::list >::iterator newIt=newCasesVect.begin(); newIt!=newCasesVect.end(); ++newIt) { if (*tmpIt == *newIt) { verif = true; } } if (verif == false) { newCasesVect.push_back(*tmpIt); } } } } } void ReceiptSection::divideCase(const std::vector& myCase, const cv::Rect* myRect, int nbMatch, std::list >& tmpCases) { std::map* > casesMap; int cpt=0; for (int i=0; i()); casesMap[i] = &(tmpCases.back()); casesMap[i]->push_back(newNode); // Insert a Node as 'root' at the begining } std::vector::const_iterator nodeIt=myCase.begin(); ++nodeIt; for (; nodeIt!=myCase.end(); ++nodeIt) { if ((*nodeIt)->block == myRect) { (casesMap[cpt])->push_back(*nodeIt); cpt++; } else { for (int i=0; ipush_back(*nodeIt); } } } } struct Node { std::vector* line; cv::Rect* block; std::vector next; };

cptpingu · Accepted Answer

Bonjour. Je n'ai pas de fuite mémoire As-tu passé un valgrind avant de l'affirmer ? ces fonctions sont de plus en lente à s'executer. As-tu passé un callgrind dessus ? (Via valgrind --tool=callgrind, et peut être visualisé par Kcachegrind) Je n'ai pas regardé ton projet de fond en comble. Je vais te lister simplement les petits détails qui me paraissent perfectibles: - std::list > => std::list* > pourrait déjà te faire gagner pas mal. En effet, plus loin dans le code tu fais: "tmpCases.push_back(*casesIt);" donc tu copies un tableau en entier à pas mal de tour de boucle au lieu d'un pointeur. - for (std::list >::const_iterator casesIt=casesVect.begin(); casesIt!=casesVect.end(); ++casesIt, cptCase++) Je l'écrirais comme ceci: // Dans un header, on essaie de nommer au maximum les choses typedef std::vector nodes_type; typedef nodes_type::iterator nodes_iterator; typedef nodes_type::const_iterator nodes_const_iterator; typedef std::list nodes_list_type; typedef nodes_list_type::iterator nodes_list_iterator; typedef nodes_list_type::const_iterator nodes_list_const_iterator; // dans le code nodes_list_const_iterator end = casesVect.end(); // Préfère mettre le .end() en dehors de la boucle, pour éviter de potentiel réappel de la fonction. for (nodes_list_const_iterator casesIt = casesVect.begin(); casesIt != end; ++casesIt, cptCase++) { //... } - // calculates the number of times the block is matched for (std::vector::const_iterator aCaseIt=mainCaseIt; aCaseIt!=(*casesIt).end(); ++aCaseIt) { scores[(*aCaseIt)->block] = 0; } for (std::vector::const_iterator aCaseIt=mainCaseIt; aCaseIt!=(*casesIt).end(); ++aCaseIt) { scores[(*aCaseIt)->block] += 1; } La première boucle ne sert à rien (une map intialisera déjà à 0, car elle utilise le constructeur "int()", qui met à 0. Tu pourrais directement écrire: nodes_const_iterator end = casesIt->end(); for (nodes_const_iterator aCaseIt = mainCaseIt; aCaseIt != end; ++aCaseIt) ++scores[(*aCaseIt)->block]; for (std::list >::iterator newIt=newCasesVect.begin(); newIt!=newCasesVect.end(); ++newIt) { if (*tmpIt == *newIt) { verif = true; } } Ici, tu fais une boucle pour savoir si au moins un élément est concordant. Tu pourrais t'arrêter directement quand tu en trouves un, inutile de continuer après. if (*tmpIt == *newIt) { verif = true; break; // Sors de la boucle. } - Pas gênant, mais moche :p => if (verif == false) => if (!verif) - Ceci est dangereux: Node* newNode; Préfère: Node* newNode = 0; - Pour ceci: tmpCases.push_back(std::vector()); Voir la remarque sur le pointeur au lieu du tableau directement. - Pour ceci: struct Node { std::vector* line; cv::Rect* block; std::vector next; }; Pourquoi écrire "std::vector*" au lieu de "std::vector" ? Je ne vois pas l'utilité d'un pointeur ici. (Je n'ai pas tout le code, il se peut que ça te soit nécessaire ailleurs). ________________________________________________________________________ Historique de mes créations, et quelques articles: [ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio] Merci d'utiliser Réponse acceptée si un post répond à votre question

wilvart · Answer

Merci de ton aide ! Il est vrai que n'ayant pas la totalité du code sous les yeux, il devait être difficile pour toi de comprendre où aller. En tout cas tes conseils sont très bons! J'ai donc effectué les changements suivants : - Suppression de la boucle // calculates the number of times the block is matched for (std::vector::const_iterator aCaseIt=mainCaseIt; aCaseIt!=(*casesIt).end(); ++aCaseIt) { scores[(*aCaseIt)->block] = 0; } - Ajout du break (trop trivial celui-là, je vais me crever un oeil pour pas l'avoir vu..) - Initialisation du pointeur Node* newNode = 0; Pour le reste, la structure de mon projet ne permet pas de passer par des pointeurs plutôt que des recopies. std::list > => std::list* > pourrait déjà te faire gagner pas mal. En effet, plus loin dans le code tu fais: "tmpCases.push_back(*casesIt);" donc tu copies un tableau en entier à pas mal de tour de boucle au lieu d'un pointeur. Je vais me perdre si j'utilise ça et je n'aurais pas vraiment gagner en perf // Dans un header, on essaie de nommer au maximum les choses typedef std::vector nodes_type; typedef nodes_type::iterator nodes_iterator; typedef nodes_type::const_iterator nodes_const_iterator; typedef std::list nodes_list_type; typedef nodes_list_type::iterator nodes_list_iterator; typedef nodes_list_type::const_iterator nodes_list_const_iterator; // dans le code nodes_list_const_iterator end = casesVect.end(); // Préfère mettre le .end() en dehors de la boucle, pour éviter de potentiel réappel de la fonction. for (nodes_list_const_iterator casesIt = casesVect.begin(); casesIt != end; ++casesIt, cptCase++) { //... } Pour ce qui est de valgrind, je ne connais que de nom et vais m'y intéresser un peu plus en profondeur. J'ai par contre modifié un peu sortCases afin de lui éviter de traiter des infos pour rien et ça donne de bons résultats. ... ... ... if ((*scoresIt).second > 1) // nbMatch == 1 means that no division is needed { divideCase(*casesIt, (*scoresIt).first, (*scoresIt).second, tmpCases); LOG("---------------- case has been divided", 3); for (std::list >::iterator tmpIt=tmpCases.begin(); tmpIt!=tmpCases.end(); ++tmpIt) { addCaseTo(*tmpIt, newCasesVect); } } else { addCaseTo(*casesIt, newCasesVect); } } } } void ReceiptSection::addCaseTo(const std::vector& aCase, std::list >& newCasesVect) { // Verifies if aCase already is in newCasesVect and push it in if necessary bool verif = false; for (std::list >::iterator newIt=newCasesVect.begin(); newIt!=newCasesVect.end(); ++newIt) { if (aCase == *newIt) { verif = true; break; } } if (verif == false) { newCasesVect.push_back(aCase); } } Encore merci pour ton aide !

wilvart · Answer

Et une connerie de plus, Pour le reste, la structure de mon projet ne permet pas de passer par des pointeurs plutôt que des recopies. [quote]std::list > => std::list* > pourrait déjà te faire gagner pas mal. En effet, plus loin dans le code tu fais: "tmpCases.push_back(*casesIt);" donc tu copies un tableau en entier à pas mal de tour de boucle au lieu d'un pointeur./quote Ca doit se faire :P

Optimiser une fonction C++

3 réponses

Votre réponse

Discussions similaires