Statique VS dynamique

Version imprimable

09/05/2015, 21h57
mister3957

Statique VS dynamique
Bonjour à tous,

Je me casse les dents sur un truc que je pensais bateau à la base mais que finalement me donne du fil à retordre.

Le contexte est que j'ai plusieurs algorithmes qui agissent sur le même contexte, mais de manière différente.

Les codes ci dessous ne sont pas validés syntaxiquement, car à "main levé", mais c'est pas grave, l'idée reste la même.

La définition d'un algorithme ressemble à ceci :
Code:

1 2 3 4 5 template<int I> class MonAlgo { static bool Do(); // renvoi true s'il a pu améliorer quelque chose, sinon false }
Ici l'énumération des algorithmes disponibles :
enum E_ALGOS
{
MON_ALGO_1,
MON_ALGO_2,
MON_ALGO_3,
MON_ALGO_4
}

Donc l'implémentation d'in algo se résume à :
Code:

1 2 3 4 5 6 7 template<> MonAlgo<MON_ALGO_1> { static bool Do() { // Je fais des trucs // Si j'ai assuré, return true sinon return false } };
Désormais, il faut les faire coucher ensemble, sachant que l'ordre d'exécution est un facteur important au niveau des performances. Alors je veux un système semi configurable par le code qui pourra décrire un ordre d'exécution. Par exemple :
Code:

1 2 3 4 5 6 7 8 9 int Exec_Table = [ MON_ALGO_1, MON_ALGO_3, MON_ALGO_4, MON_ALGO_1, MON_ALGO_2, MON_ALGO_4 ];
Un autre cheminement pourrait donner :
Code:

1 2 3 4 5 6 7 8 9 int Exec_Table = [ MON_ALGO_2, MON_ALGO_1, MON_ALGO_3, MON_ALGO_4, MON_ALGO_3, MON_ALGO_4 ];
Toutes ces valeurs sont statiques, alors j'avais espéré pouvoir obtenir une programmation statique, ainsi :
Code:

1 2 3 4 5 for(int i = 0, i < sizeof(Exec_Table); ++i) { bool b = true; while(b = Exec_Table<i>::Do()) {} // On le ré exécute jusqu'à temps qu'il ne puisse plus offre de solution }
Mais une erreur de compilation m'empêche de faire ceci en m'indiquant que "i" n'est pas statique, ce qui peut se comprendre.

Première question : Etant donné que tout est basé sur du statique, comment faire en sorte que ça le reste dans cette portion de code, et donc que ça compile ?

Maintenant deuxième demande : Je souhaite faire des combinaisons d'algos, à savoir par exemple :
Code:

1 2 3 4 MON_ALGO_1 MON_ALGO_3 MON_ALGO_4
C'est à dire que tant que 3 ou 4 on trouvé un résultat, ce couple doit être ré exécuté jusqu'à tant que ni l'un ni l'autre ne renvoi du positif. Si tel est le cas, on réexécute 1 et si ce dernier trouver quelque chose, on relancer le couple. Le tout s'arrête lorsque 1 ne trouve pas de solution meilleure et que donc il n'y a plus besoin d'exécuter 3 et 4.

J'espère trouver un moyen de faire en sorte que le cheminement soit configurable dans le code, via des tableaux et que le compilateur puisse gérer ça si tant est que l'ensemble soit programmée de manière statique. Mais là je galère un peu comme vous pouvez le constater.

Le premier début de réponse serait de répondre à la première question, à savoir comment rendre ce "i" constant sachant qu'il démarre de 0, valeur constante jusqu'à sizeof(tab) valeur également constante.

Merci beaucoup par avance,

A bientôt :)
09/05/2015, 23h25
Bousk

Salut,

effectivement puisque ton i prend sa valeur à l'exécution tu n'y arriveras pas.
Un moyen pourrait être d'utiliser des variadic templates pour appeler tes algos Call(Algo1, Algo2, ...); Call(Algo2, Algo3, ...);, je promets rien, mais je pense que ça devrait marcher.

Hello,

Une utilisant spécifiquement un tableau pour stocker l'ordre de tes algos je sais pas si c'est possible (peut être à base de constexpr ?).

Si tu peux les passer en paramètre template (à priori pas de soucis, c'est des constantes de compilation), tu peux faire quelque chose du genre

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
#include <initializer_list>
#include <iostream>
 
enum E_ALGOS {
	MON_ALGO_1,
	MON_ALGO_2
};
 
template<int I> struct Exec { };
template<> struct Exec<MON_ALGO_1> { static bool Do() { std::cout << "1\n"; return true; } };
template<> struct Exec<MON_ALGO_2> { static bool Do() { std::cout << "2\n"; return true; } };
 
template <int I> struct Run { static void Do() { while(!Exec<I>::Do()); } };
 
template <int... I>
void foo() {
	// à base d'initializer_list, ordre garanti
	auto list = { (Run<I>::Do(), 0)... };
 
	// à base de lambda, ordre non garanti
	[](...){ }((Run<I>::Do(), 0)...);
}
 
int main() {
	foo<MON_ALGO_1, MON_ALGO_2>();
}

Je ne vois pas pourquoi tu veux obligatoirement du static ? :koi:

Je vois 2 solutions une pure C avec des #define (<- avec cette solution je vais prendre des -1:mrgreen: ) et une avec un foncteur

Solution 1:
Tu peux mettre tout dans un fichier algos.h pour l'inclure là où tu veux

Code:

1
2
3
4
5
6
7
#define ALGO_1 \
     \
    /* XXX */
 
#define ALGO_2 \
     \
    /* XXX */

Et plus loin

Code:

1
2
3
4
5
6
7
8
//  maybe include "algos.h"
 
//  Définition de ton contexte ici
//  int i = 0;
 
    ALGO_2
    ALGO_1
//  ...

Solution 2:
Édit: On fait un tableau de pointeurs de fonctions et ainsi supprimer le switch/ case. Mais tous tes algos doivent avoir la même signature.

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Algos {
// Constructor
public:
 
    Algos() : current_nb_algos(0) {}
 
 
// Public Interface
public:
 
    void set_nb_algos(unsigned short new_number) {
        if (new_number > current_nb_algos) {
            list_algos.reserve(new_number);
        }
 
        if (new_number > 0) { current_nb_algos = new_number; }
    }
 
 
    void add_algo(ALGO_ID algo) {
//      maybe if (algo < NB_ALGOS)
        list_algos.push_back(algo);
    }
 
 
//  void add_algo(unsigned short nb_algos, ALGO_ID algo, ...) { /* */ }
 
 
public:
 
    void operator() () {
//      Soit tous les algos peuvent être inline
//      Ou alors on code les algos dans le switch case
//      Ou un autre truc
 
        std::vector<ALGO_ID>::iterator it = list_algos.begin();
 
        for(unsigned nb = 0; ((nb < current_nb_algos) && (it != list_algos.end())); ++it, ++nb) {
            switch(*it) {
            case ALGO_1:
//             algo_1();
//             or
//             /* XXX */
                break;
 
            case ALGO_2:
//             algo_2();
//             or
//             /* XXX */
                break;
 
            case ALGO_3:
//             algo_3();
//             or
//             /* XXX */
                break;
            }
        }
    }
 
 
public:
 
    typedef enum e_ALGO_ID {
        ALGO_1 = 0,
        ALGO_2,
        ALGO_3,
        NB_ALGOS
    } ALGO_ID;
 
 
private:
 
    std::vector<ALGO_ID> list_algos;
 
    unsigned current_nb_algos;
};

10/05/2015, 09h22
mister3957

Ouais finalement autant se passer du statique, c'est pas ça qui va faire rallonger significativement les performances pour mon problème et ça sera plus facile à gérer le point numéro 2.

C'était au cas où un truc statique était possible sans trop se casser la tête ;)

Merci à vous,

A bientôt

Salut,

Citation:

Tout problème en informatique peut être résolut en ajoutant un niveau d'indirection

Ce n'est pas de moi, mais en voici encore une fois la preuve ;)

Il y a, en effet, tout à fait moyen de gérer les algorithmes à la compilation à l'aide des variadic template à la condition expresse que tu puisse savoir, à la compilation, dans quel ordre il faudra les exécuter ;)

Partons donc d'une légère adaptation de ta classe MonAlgo, pour qu'elle prenne la forme d'un foncteur (c'est, tout simplement, plus facile à manipuler ;) ):
Code:

1 2 3 4 5 6 7 8 template <int i> struct MonAlgo{ enum{value = i}; bool operator()() { std::cout<<"callee called with value"<<value<<"\n"; return true; } };
Puis, créons un autre foncteur qui utilise les variadic templates pour savoir quels algorithmes il doit appeler sous une forme proche de
Code:

1 2 3 4 5 6 7 8 9 template <int i, int ... others> struct Caller{ bool operator()() const{ bool b =MonAlgo<i>()(); //appelle effectivement l'algorithme if(b) return Caller<others ...>()(); // déroule les algorithmes suivants return false; } };
Il n'y a plus qu'à mettre fin à la récursion en spécialisant Caller sous la forme de
Code:

1 2 3 4 5 6 7 template <int i> struct Caller<i>{ bool operator()()const{ return MonAlgo<i>()(); } };
Une fois cela fait, il n'y a plus qu'à créer notre fonction main :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 /* l'énumération que nous allons utiliser */ enum E_ALGO{ MON_ALGO_1 = 1, MON_ALGO_2 , MON_ALGO_3, MON_ALGO_4 }; int main(){ Caller< MON_ALGO_1, MON_ALGO_2, MON_ALGO_3, MON_ALGO_4>()(); return 0; }