Discussion :

[mister3957]

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:


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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[JolyLoic]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[mister3957]

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