Discussion :

[Ekinoks]

Bonjour,

J'ai une question toute simple dont je n'arrive pas a trouver la réponse...

Imaginons que l'on a une libraire C++ de ce type:

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
 
template <int DEG>
class Tree {
    struct Node {
        std::array<std::unique_ptr<Node>, DEG> next;
        bool val=false;
    };
    Node root;
public:
    void add(std::vector<int> mot) {
        Node *pos = &root;
        for(auto a: mot) {
            if( !pos->next[a] )
                pos->next[a] = std::make_unique<Node>();
            pos = pos->next[a].get();
        }
        pos->val = true;
    }
};

L'utilisation de cet arbre est facile si on connait avant la compilation le degré maximal de chaque nœud.
La question que je me pose est de savoir si il possible d'utiliser cette classe sans la modifier dans un cadre dynamique ?
C'est a dire choisir cette taille a l'exécution.

Connaissez-vous un moyen simple de faire ça ?

Merci pour votre aide

[JolyLoic]

Non, à moins de toute templater par deg, et d'avoir un programme qui contient toutes les possiblités, et de brancher dynamiquement sur celle qui t'intéresse...

Code :

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

1
2
3
4
5
switch(dynDeg){
  case 1: runAlgo<1>();
  case 2: runAlgo<2>();
  case 3: runAlgo<3>();
}

Sinon, pour du dynamique, le plus simple est de remplacer array par vector.
Mais il y des des classes autres que array qui peuvent aider dans le cas où la plupart des Tree sont en dessous de Deg, mais quelques rares sont au dessus. Regarde par exemple http://llvm.org/docs/ProgrammersManu...-smallvector-h comme source d'inspiration.

[Ekinoks]

Merci JolyLoic pour ta réponse

Arf dommage qu'on ne puisse pas... J'avais aussi pensé à la solution d'un switch, mais c'est quand même sacrément moche.
Étant donné que les templates sont fait pour faire du code plus générique, c'est quand même fou que les templates ne puissent pas être initialisés dynamiquement... C'est un sacré frein a la généricité non ?

Ok, donc si j'utilise des vector a la place, le code devient:

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
class Tree {
    struct Node {
        std::vector<std::unique_ptr<Node>> next;
        bool val=false;
        Node(unsigned int deg) {
            next.resize(deg);
        }
    };
    Node root;
    unsigned int deg;
public:
    Tree(unsigned int deg) : root(deg), deg(deg) {
 
    }
    void add(std::vector<int> mot) {
        Node *pos = &root;
        for(auto a: mot) {
            if( !pos->next[a] )
                pos->next[a] = std::make_unique<Node>(deg);
            pos = pos->next[a].get();
        }
        pos->val = true;
    }
};

Si je fais un benchmark en remplissant l'arbre avec 1000 chaines de longueurs 1000, j’obtiens :

Avec template + std::array: 56ms
Sans template + vector: 85ms
Sans template + classique array: 78ms

Une idée pour avoir les mêmes performances que la solution template, mais en fixant le degré de manière dynamique et sans utiliser de switch?

[JolyLoic]

Ca dépend de la forme de ton arbre... Mais un truc comme le SmallVector pourrait aider.