Discussion :

[oodini]

Bonsoir,

Disons que j'ai un vecteur non mutable d'objets contenant pas mal de propriétés.
Je dois parcourir consécutivement cette liste d'objets, et faire des traitements en fonction de la suite d'objets de ce vecteur.
Le résultat de ces traitement produit un unique objet résultat, qui va éventuellement être "augmenté" lors du parcours de chaque objet.
En parallèle de la mise à jour de cet objet, des variables d'état du traitement, extérieures au vecteur d'entrée et à l'objet résultat, seront mises à jour par la consultation des objets et le traitement en question.

Ce traitement n'est pas du tout parallélisable, car les traitements pour un objets donné dépendront de la valeur des objets qui le précèdent (pas de tous, mais des quelques précédents).

C'est donc plus ou moins équivalent à une fonction du type (c'est conceptuel, à la louche) :

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
Result maFonction(const std::vector<Objet>& sequence)
{
    Result r;
 
    int a, b, c, d;    // variables d'état
    const Objet* previousElem = nullptr;
 
    for (const auto& elem : sequence)
    {
          // lecture de certaines données de elem
 
          // énorme quantité de if/else, avec :
          // - utilisation de previousElem
          // - utilisation des états
          // - mise à jour des états
          // - mise à jour de r
 
          objet = &elem;
    }
 
    return r;
}

Un bête codage impératif m'amènerait à un complexe arbre de décision (pas tant lié au nombre d'objets qu'aux nombreuses propriétés de chacun), avec des if/else en pagaille.

Il me faut donc sortir des paradigmes habituels, dont on a tous une vague connaissance, mais qu'on a peu souvent exploré : programmation logique (Haskell ?), détournement d'une machine à états...

Les traitements sont algorithmiquement primitifs, et la complexité se résume en fait à ces if/else, qu'on peut voir comme des règles. Idéalement, il serait apprécié qu'elles puissent être définies dans un fichier externe, et dans un langage simple.

Qu'auriez-vous à me suggérer ?

Il n'est pas du tout sûr que le C++ soit le langage le plus à même de répondre à mon besoin (malheureusement).

[dragonjoker59]

Est-ce que le Design Pattern Visitor conviendrait?

[koala01]

Salut,

Des solutions, il y en a en pagaille, et ca va d'une fonction récursive au patron de conception visiteur en passant par solutions bien plus complexes comme le duck-typing associé à un patron de conception proche du chain of responsability, par la mise en place d'un système proche de la manière dont on implémenterait AST ou l'utilisation d'un système proche d'un ECS, j'en passe et de meilleures.

Le problème, c'est que, sans avoir plus de précision, il nous sera totalement impossible de t'aider à choisir une solution plutôt qu'une autre, "simplement" parce que toutes les techniques envisageables n'ont pas forcément les mêmes finalités ni les mêmes contraintes.

Dés lors, si tu pouvais nous donner un exemple des données que tu dois traiter (en tout cas, des propriétés qui t'intéressent pour ces données) et du genre décision que tu dois prendre, cela nous aiderait surement énormément à t'orienter dans "la bonne voie"

[stendhal666]

Je dois parcourir cette liste d'objets, et faire des traitements en fonction de la suite d'objets de ce vecteur. Ce traitement n'est pas du tout parallélisable, car les traitements pour un objets donné dépendront de la valeur des objets qui le précèdent (pas de tous, mais des quelques précédents).

Comme le dit Koala, ta description est bien abstraite. De ce que tu dis: traitements non parallélisables dépendant des traitements précédents, je pense tout de suite aux expressions régulières. Il y a bien des façons de s'y attaquer. J'avais trouvé un article qui traitait le sujet en profondeur: https://swtch.com/~rsc/regexp/regexp1.html. L'auteur fait une analyse intéressante des machines à état, en particulier leurs variantes déterministes/non déterministes.

Dans un style beaucoup plus léger, il y a le premier chapitre de Beautiful code où Kernighan développe une approche récursive très élégante, avec quelques limites. Le chapitre est disponible sous forme d'article sur le site de Princeton: http://www.cs.princeton.edu/courses/...beautiful.html

Normalement ton problème devrait être plus simple car si le traitement ne dépend que des éléments précédents et pas des éléments futurs, tu ne devrais pas être forcé au back-tracking.

Il me faut donc sortir des paradigmes habituels, dont on a tous une vague connaissance, mais qu'on a peu souvent exploré : programmation logique (Haskell ?), détournement d'une machine à états...

Qu'auriez-vous à me suggérer ?

Il n'est pas du tout sûr que le C++ soit le langage le plus à même de répondre à mon besoin (malheureusement).

Je ne sais pas si j'aurais classé Haskell du côté "programmation logique" (je ne sais pas si le terme est réservé mais je l'aurais employé plutôt pour la famille Prolog) mais certaines particularités des langages fonctionnels permettent de réduire la complexité liée à un arbre de décision. Pour un exemple plus ou moins pertinent selon les données concrètes de ton problème, tu peux jeter un oeil aux red-black trees d'Okasaki. Le pattern-matching y est utilisé de façon très ingénieuse.

[oodini]

Dés lors, si tu pouvais nous donner un exemple des données que tu dois traiter (en tout cas, des propriétés qui t'intéressent pour ces données) et du genre décision que tu dois prendre, cela nous aiderait sûrement énormément à t'orienter dans "la bonne voie"

Ce n'est pas évident, car c'est très métier et complexe. J'essaye de trouver un en exemple équivalent, mais ce n'est pas évident.
J'espère que la modification de mon message initial pourra t'éclairer.
Mais je vais essayer de gamberger pour trouver un exemple parlant.

Des solutions, il y en a en pagaille, et ca va d'une fonction récursive au patron de conception visiteur en passant par solutions bien plus complexes comme le duck-typing associé à un patron de conception proche du chain of responsability, par la mise en place d'un système proche de la manière dont on implémenterait AST ou l'utilisation d'un système proche d'un ECS, j'en passe et de meilleures.

Pour le visiteur, ça ne me parait pas adapté. On n'est pas dans la problématique ouvert/fermé.
Pour la chaîne de responsabilité, à moins de créer des objets matérialisant les "choix", et qui se renvoient la balle, je ne vois pas trop. Mais je n'ai pas une assez bonne connaissance des design patterns (mes employeurs me découragent toujours d'en utiliser : trop compliqué pour la maintenance...pfff). Mais l'AST pourrait être un solution.
L'ECS, je ne sais pas ce que c'est.

@stendhal666 : je vais prendre le temps de lire tes liens, et je te répondrai au plus tard ce soir !

[koala01]

Ce n'est pas évident, car c'est très métier et complexe. J'essaye de trouver un en exemple équivalent, mais ce n'est pas évident.
J'espère que la modification de mon message initial pourra t'éclairer.
Mais je vais essayer de gamberger pour trouver un exemple parlant.

Oui, je sais ce que c'est... c'est parfois pas évident d'extraire une partie métier pour en donner un exemple précis

Pour le visiteur, ça ne me parait pas adapté. On n'est pas dans la problématique ouvert/fermé.

Ce n'était qu'un exemple de solution, pour bien montrer qu'il y en avait en masse

Pour la chaîne de responsabilité, à moins de créer des objets matérialisant les "choix", et qui se renvoient la balle, je ne vois pas trop. Mais je n'ai pas une assez bonne connaissance des design patterns

j'ai dit "proche du DP" Je veux dire par là que, si tu peux déterminer les conditions dans lesquelles chaque traitement est observé, tu peux assez facilement faire en sorte de tester une condition d'exécution du traitement à la fois et, si tu n'est pas dans les bonnes conditions, tu passes la main
Tu pourrais d'ailleurs aussi envisager d'avoir un tableau de std::function dont chaque élément "pointerait" vers un traitement spécifique et de boucler sur tous ces éléments "tant que le dit élément n'a pas dit qu'il a pris le traitement en charge".

(mes employeurs me découragent toujours d'en utiliser : trop compliqué pour la maintenance...pfff).

Hein c'est quoi ces conneries... Ils peuvent aussi te décourager d'utiliser boost ou la SL, tant qu'il y sont !!!

Mais l'AST pourrait être un solution.

Peut être, mais attention, sa mise en place ne sera peut-être pas si évidente que cela

L'ECS, je ne sais pas ce que c'est.

recherche entity component system sur internet, cela te donnera une bonne idée de ce que c'est

[dragonjoker59]

Ils peuvent aussi te décourager d'utiliser boost ou la SL, tant qu'il y sont !!!

Dans ma précédente boîte ils ne voulaient pas voir ça, mais demandaient l'utilisation de ATL/MFC...