Comparer des caractères

Bonjour à tous,


J'ai un tableau contenant des "unsigned char", composé de groupes.
Je connais la taille d'un groupe, ainsi que le nombre de groupe contenu dans mon tableau.

A partir de là, je voudrais faire un second tableau d'unsigned char en éliminant les doublons, puis un tableau d'unsigned int pour indicer les groupes.

Par exemple:
http://afilez.free.fr/CharTab.bmp

Ici, on par sur un tableau composé de 3 groupes de 3. Le groupe 1 et le groupe 3 sont similaires.

Donc le nouveau tableau ne contient que 2 groupes, et le tableau d'indices va référencer le premier groupe, puis le deuxième et pour finir encore le premier.

Sachant qu'on aura des tableau d'environ 3000 groupes de 16 à 20 "unsigned char", j'ai besoin de faire les choses de manière propre et optimisée.

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

// Parcours du tableau d'origine groupe par groupe. for(unsigned int uiOriginGroup = 0, uiOriginGroup < uiTotalOriginGroup, uiOriginGroup++) { // Pour chaque groupe, on va chercher s'il n'est pas déjà "recensé" int uiIndex = -1; for(unsigned int uiNewGroup = 0; uiNewGroup < uiNewGroupCount; uiNewGroup++ { bool bTrouve = true; for(unsigned int uiGroupComponent = 0; uiGroupComponent < uiGroupComponentCount; uiGroupComponent++) { if(TableauOrigin[uiNewGroup * uiGroupComponentCount + uiGroupComponent] != TableauNew[uiNewGroup * uiGroupComponentCount + uiGroupComponent] { bTrouve = false; break; } }   if(bTrouve) { iIndex = uiNewGroup; break; } }   if(uiIndex > -1) // On ajoute juste l'indice au tableau des indices else { // On rajoute un nouveau groupe dans la nouvelle table des groupes // On positione l'indices (ou la taille de la nouvelle table - 1) } }

---

Mais du code comme ça ça me paraît trop superficiel pour être performant :s

Est-ce que quelqu'un peut me donner une approche différente vers laquelle je pourrais me tourner?


Merci beaucoup :)


A bientôt

Je partirais à priori vers une solution à base de map, pour éviter la recherche linéaire dans le tableau. Un truc genre :

Code:

---

1 2 3

typedef boost::array<char, 3> Groupe; // Pas std::string pour éviter l'allocation dynamique, si tous les groupes sont de même taille typdef std::map<Groupe, size_t> IndexMap; IndexMap indexMap;

---

Et remplacer la boucle interne de recherche par :

Code:

---

1 2	std::pair<IndexMap::iterator, bool> insertInfo = indexMap.insert(std::make_pair(currentGroup, currentIndex)); currentIndex = insertInfo.first.second; // Retourne l'ancien index si l'insertion a échoué.

---

Par contre, ma solution fait bien plus de choses dans chaque itération, donc je ne sais pas si elle est plus performant pour un jeu de donnée somme toute pas si grand.

Ok, merci beaucoup, c'est noté.


De toute façon je vais en tester plusieurs voir ce qui est le plus rapide.

On va attendre d'autres suggestions ;)


Merci encore