simplifier un code en remplaçant un switch

**yan** · 14/08/2009, 09h39

Bonjour,
j'ai fait une portion de code qui me permet de trier un vecteur d'une structure. Je doit pouvoir choisir quel membre à utiliser pour le trie. Cela donne :

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
34
35
36
37
38
39
switch(m_sortFlag)
    {
        case DESCENDINGORDER | IDMAILBOX:
            qStableSort 
                    (
                        m_internal.begin(),
                        m_internal.end(),
                        std::binary_negate<compareIdMailBox>(compareIdMailBox()) 
                    );
 
            break;
        case ASCENDINGORDER | IDMAILBOX:
            qStableSort 
                    (
                        m_internal.begin(),
                        m_internal.end(),
                        compareIdMailBox() 
                    );
 
            break;
 
        case DESCENDINGORDER | IDEMAIL:
           qStableSort 
                    (
                        m_internal.begin(),
                        m_internal.end(),
                        std::binary_negate<compareIdEmail>(compareIdEmail()) 
                    ); 
            break;
        case  ASCENDINGORDER | IDEMAIL:
           qStableSort 
                    (
                        m_internal.begin(),
                        m_internal.end(),
                        compareIdEmail() 
                    ); 
            break;
...
}

Ce commence à être lourd en écriture.
Comme tout doit être connue à l'exécution, je ne voie pas trop comment me passer de ce switch.
Je pensais faire une fonction template pour simplifier l'écriture du trie (et donc au lieu de plusieurs foncteur, j'en aurais qu'un mais template).
Après je ne voix pas pour le switch... J'ai l'impression que cela serait possible avec les template variadique, mais comme visual de fait encore du c++0x, je peut pas tester.

Si quelqu'un à une idée.

**Arzar** · 14/08/2009, 11h13

Bonjour,
Si tu es autorisé à utiliser boost, tu pourrais peut-être stocker le prédicat dans une boost::function (ou carrément dans une std::function depuis VS2008 SP1) et sortir le tris hors du switch :
(code pas testé)

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
 
std::vector<A> m_internal;
std::function<bool (const A&, const A&)> SortFunc;
switch(m_sortFlag)
{
   case DESCENDINGORDER | IDMAILBOX:
      SortFunc = std::binary_negate<compareIdMailBox>(compareIdMailBox());
      break;
 
   case ASCENDINGORDER | IDMAILBOX:
      SortFunc = compareIdMailBox();
      break;
 
   case DESCENDINGORDER | IDEMAIL:
      SortFunc = std::binary_negate<compareIdEmail>(compareIdEmail());
      break;
 
   case ASCENDINGORDER | IDEMAIL:
      SortFunc = compareIdEmail();  
      break;
}
 
std::stable_sort(m_internal.begin(), m_internal.end(), SortFunc);

**yan** · 14/08/2009, 11h33

Je suis sous 2005 et c'est trop tard pour boost

.
:Merci: pour l'info sur std::function.

Juste pour information et curiosité perso,
le fait de faire comme cela, est-ce que le compilo va pouvoir optimiser au maximum le trie? Comme tout inliner si besoin?
Ou le sort sera générique par rapport à std::function?

**Arzar** · 14/08/2009, 12h26

Envoyé par yan

Juste pour information et curiosité perso,
le fait de faire comme cela, est-ce que le compilo va pouvoir optimiser au maximum le trie? Comme tout inliner si besoin?

Errr j'ai bien peur que non. D'après la doc de boost :

With a properly inlining compiler, an invocation of a function object requires one call through a function pointer.

"invocation of a function object" je suppose qu'ils désignent par ça l'appel au foncteur stocké dans la boost::function ?

Il semblerait donc qu'un bon compilateur puisse au maximum réduire une boost::function à un appel de pointeur de fonction...

**yan** · 14/08/2009, 13h32

Envoyé par Arzar

Il semblerait donc qu'un bon compilateur puisse au maximum réduire une boost::function à un appel de pointeur de fonction...

c'est bien ce que je pensais . :Merci:

**Klaim** · 17/08/2009, 02h14

Note: c'est std::tr1::function , dans <function> du VS2008 SP1, et pas std::function.

Invité · 17/08/2009, 11h01

Sans boost, tu peux faire cela avec un bête foncteur (une classe avec surcharge du () ). Tu transformes les paramètres de tri en données membres, que tu passes à l'instanciation de la classe, et tu déplaces le switch dans l'opérateur () surchargé.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
class Sorter {
private:
  int SortType;
public:
  Sorter(int st) : SortType(st) {}
  bool operator()(type &t1,type &t2) { 
    switch SortType {
       case ... : return...
    }
  }
};

Ca n'élimine pas exactement le switch (de toutes façons, tu ne pourras complètement éliminer cette condition: elle existe dans le problème réel), mais ca l'isole dans le foncteur de tri, c'est plus propre.

A l'appel tu fais juste

Code :

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

1
2
 
stable_sort(v.begin(),v.end,Sorter(sorttype));

En théorie, cet appel peut être inliné, mais il n'est pas certain que ce soit une bonne chose, parce que le switch le sera aussi... Sur quicksort, c'est presque certainement une mauvaise chose, sur un stable_sort, qui normalement utilise heapsort, je ne sais pas, faut tester... (mais de toutes façons, ce ne sera pas plus rapide que ton code original)

Ensuite, tu peux templatiser ta classe Sorter et tout cela... Dans ton cas, je transformerais le SortType en champ de bits, avec un bit controlant le tri, un autre la nature de l'objet à trier. Du coup, la classe foncteur aura un constructeur prenant plusieurs paramètres, et ce sera plus intuitif à la relecture.

Mais bon, à moins que je n'ai pas compris ton problème, c'est exactement le domaine d'application (et l'intérêt) des foncteurs et de la surcharge de ().

Francois

**yan** · 17/08/2009, 11h44

Envoyé par fcharton

Ca n'élimine pas exactement le switch (de toutes façons, tu ne pourras complètement éliminer cette condition: elle existe dans le problème réel), mais ca l'isole dans le foncteur de tri, c'est plus propre.

j'y avais pensée, mais je me suis dit que cela allez rajouter un switch dans chaque appel au foncteur (puisque le type n'est pas fixé à la compilation), et donc plomber les perf pour rien (d'un côté pour ce trie, ça devrais pas être visible puisque c'est pour une ihm).
Je me trompe?

Invité · 17/08/2009, 12h26

Envoyé par yan

j'y avais pensée, mais je me suis dit que cela allez rajouter un switch dans chaque appel au foncteur (puisque le type n'est pas fixé à la compilation), et donc plomber les perf pour rien (d'un côté pour ce trie, ça devrais pas être visible puisque c'est pour une ihm).
Je me trompe?

Non, tu as raison.

L'approche foncteur permet de nettoyer ton code, et de le rendre plus maintenable, mais elle va en réduire la vitesse.

Maintenant, il faudrait voir de combien, parce que

1- si tu es dans une IHM et que ce que tu tries n'est pas très gros (genre qq milliers d'enregistrements), tu ne vas probablement rien voir
2- si ta fonction de comparaison sous jacente est lente (parce que tu travailles avec des structures complexes, ca semble être le cas ici, d'après les noms de tes fonctions) le switch ne changera pas grand chose
3- la comparaison n'est pas toujours (en fait pas souvent) le principal facteur de la vitesse d'un tri.
4- si l'appel au tri est dans une boucle, celle ci se trouve raccourcie, et ca peut gagner du temps...

Egalement, si les performances de ton tri se révèlent cruciales, il faut te poser une question supplémentaire : as tu besoin d'un tri stable? parce qu'en général, ca a un effet assez violent... (stable_sort est implémenté comme un heapsort, là ou le tri tout bête est un quick sort, et la différence de vitesse est de l'ordre de 30%...)

Donc, tests, tests, tests... (le code n'est pas lourd à écrire, un coup de profiler dessus, et tu seras très vite fixé)

Francois

**yan** · 17/08/2009, 13h33

Envoyé par fcharton

1- si tu es dans une IHM et que ce que tu tries n'est pas très gros (genre qq milliers d'enregistrements), tu ne vas probablement rien voir
2- si ta fonction de comparaison sous jacente est lente (parce que tu travailles avec des structures complexes, ça semble être le cas ici, d'après les noms de tes fonctions) le switch ne changera pas grand chose

c'est un test de int ou de string donc, c'est pas violent. Au pire on peut imaginer 50000 item.
Je ne pensez pas que stable_sort avait autant de différence qu'avec le sort.
C'est toujours le problème, lisibilité vs rapidité. Içi, a mon avis se sera bien assez rapide pour un humain.
Je vais simplifier avec ta proposition, c'est quand même moins casse gueule pour les futurs développeurs.

Invité · 17/08/2009, 14h18

Ouais, c'est ma théorie personnelle... L'interface (IHM), faut que le code soit ultra propre, parce que c'est toujours ce qu'on doit refaire, toujours dans l'urgence (et en été, quand le type qui a écrit l'original est en vacances au trou du huc du monde)...

Ce serait un débat intéressant, d'ailleurs... Dans quelle mesure le C++ moderne rend la maintenance plus facile.

Francois