Discussion :

[DelphiManiac]

...Bon, même si on est toujours en récursif (un peu obligé vu le contexte), on gagne au moins le fait de ne plus repasser inutilement sur des nœuds déjà visités...

Je ne vois pas pourquoi la récursivité serait encore nécessaire avec un tableau ordonné (ou alors j'ai vraiment zappé quelque chose). La récursivité avait pour but de remonter l'arbre de dépendance pour recalculer les ancêtres avant les descendant.

Le but du tableau ordonnée est justement d'effectuer ce classement de dépendance avant. Il suffit donc de parcourir le tableau dans le bon ordre et de calculer les éléments les uns après les autres. Une simple boucle suffit.

Dans tout les cas, le tableau ordonné avec des numéros ne me semble pas la solution la plus adaptée. Le fait de passer par une numérotation reste problématique si l'on a plusieurs éléments modifiés avant de lancer le calcul, cela risque d’engendrer la renumérotation les lignes.

En partant de l'exemple suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
article 1
- composant 1
- composant 2
 
article 2
- composant 1
- composant 3
 
composant 3
- composant 4

Si l'on modifie le composant 1, cela engendre le recalcul d'article 2, on a donc dans notre tableau numéroté

Code :

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

1
2
3
 
1 - composant 1
2 - article 2

Admettons que dans le même traitement, on modifie aussi composant 3, du coup lors de l'ajout de composant 3, il va falloir le glisser entre la ligne 1 et la ligne 2, d'ou renumérotation.


Voici un bout de code qui me semble être correct (pas vraiment testé à fond) et fort possible qu'il y ai plus simple. Cette version est relativement complexe vu que j'ai voulu gérer le fait que plusieurs éléments puissent être modifiés avant que le traitement ne soit lancé.

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
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
stElementATraiter est une structure
    element est un cElement dynamique
    doitEtreCalculé est un booléen
FIN
 
cElement est une Classe
    nomElement est une chaîne
    composants est un tableau associatif de cElement dynamique
    parents est un tableau associatif de cElement dynamique
    GLOBAL 
        listeDesElements est un tableau associatif de cElement dynamique
        elementATraiter est un tableau associatif de stElementATraiter
        ordreTraitement est un tableau de chaîne
FIN
 
PROCEDURE Constructeur(nom est une chaîne)
listeDesElements[nom] = objet
nomElement = nom
 
PROCEDURE Destructeur()
 
PROCEDURE _ajouteComposant(element est un cElement dynamique)
composants[element.nomElement] = element
element.parents[nomElement] = objet
 
PROCEDURE GLOBAL _initTraitement()
TableauSupprimeTout(elementATraiter)
TableauSupprimeTout(ordreTraitement)
 
PROCEDURE GLOBAL _ajouteElementModifie(unElement est un cElement dynamique, chemin est une chaîne = "", bDoitEtreCalculer est un booléen = Vrai)
unComposant est un cElement dynamique
unParent est un cElement dynamique
 
POUR TOUT unComposant DE unElement.composants
    SI Position(chemin, "/" + unComposant.nomElement) = 0 ALORS
        _ajouteElementModifie(unComposant, chemin, Faux)
    FIN
FIN
 
 
_ajouteATraiter(unElement, bDoitEtreCalculer)
 
SI bDoitEtreCalculer ALORS
    POUR TOUT unParent DE unElement.parents
        _ajouteElementModifie(unParent, "/" + unElement.nomElement + chemin)
    FIN
FIN
 
PROCEDURE GLOBAL PRIVÉ _ajouteATraiter(unElement est un cElement, bDoitEtreCalculer est un booléen)
SI elementATraiter[unElement.nomElement]..Occurrence = 0 ALORS
    TableauAjoute(ordreTraitement, unelement.nomElement)
 
    unElementAtraiter est un stElementATraiter
    unElementAtraiter.element = unelement
    unElementAtraiter.doitEtreCalculé = bDoitEtreCalculer
 
    elementATraiter[unElement.nomElement] = unElementAtraiter
SINON
    SI bDoitEtreCalculer ALORS
        elementATraiter[unElement.nomElement].doitEtreCalculé = bDoitEtreCalculer
    FIN
FIN
 
PROCEDURE GLOBAL _afficheCalculAEffectuer()
POUR TOUT unNomElement DE ordreTraitement
    SI elementATraiter[unNomElement].doitEtreCalculé ALORS
        Trace(elementATraiter[unNomElement].element.nomelement)
    FIN
FIN

et pour tester ce bout de code :

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
 
article1 est un cElement("article1")
article2 est un cElement("article2")
 
composant1 est un cElement("composant1")
composant2 est un cElement("composant2")
composant3 est un cElement("composant3")
composant4 est un cElement("composant4")
 
article1._ajouteComposant(composant1)
article1._ajouteComposant(composant2)
 
article2._ajouteComposant(composant1)
article2._ajouteComposant(composant3)
 
composant3._ajouteComposant(composant4)
 
cElement._initTraitement()
cElement._ajouteElementModifie(composant4)
cElement._ajouteElementModifie(composant1)
cElement._afficheCalculAEffectuer()

le résultat sera

Code :

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

1
2
3
4
5
composant4
composant3
composant1
article2
article1

Sur la fin de l'exemple, on utilise _initTraitement pour réinitialiser avant de lancer un nouveau traitement, _ajouteElementModifie pour ajouter un élément qui a été modifié et _afficheCalculAEffectuer pour afficher les traitements à effectuer.

Le principe général est de mémoriser les dépendances lors de l'ajout des éléments et ensuite de parcourir ces dépendances pour construire l'arbre de résolution. Cette version par contre plante lamentablement si l'on a défini un ensemble d’éléments qui contient une référence circulaire.

N'hésitez pas à faire des tests et me dire si ça correspond et si ça fonctionne.

[droliprane]

Je ne vois pas pourquoi la récursivité serait encore nécessaire avec un tableau ordonné (ou alors j'ai vraiment zappé quelque chose). La récursivité avait pour but de remonter l'arbre de dépendance pour recalculer les ancêtres avant les descendant.

Bonjour Delphimaniac,

en fait je disais juste que pour constituer le tableau, on a quand même besoin d'utiliser la récursivité pour explorer les arbres.

quant à ta solution, effectivement je trouve ça plutôt compliqué même si ça semble bon, mais cela vient surtout du fait que j'ai trop peu l'habitude d'utiliser les classes, et la poo.

En fait, dans la pratique, je ne peux pas détecter que 2 composants ont été modifiés coup sur coup et en tenir compte dans un seul et même traitement. A chaque modification d'un composant, j'ai un traitement automatique, threadé, de recalcul du cout des parents, qui se fait tout seul. Donc dans un cas comme celui que tu évoque, les 2 calculs vont se faire en parallèle, même si effectivement le deuxième calcul aurait pu profiter du premier afin de ne pas tout recalculer.

Quant aux cycles, j'ai également un thread de vérification (avant valorisation) qui vérifie que tout nœud de mon arbre a bien un suivant qui existe, et qu'il n'y a pas de cycle (A->B->....->....->N->B)

[droliprane]

alors quelques nouvelles :

j'y vais en douceur, j'ai implémenté la solution de mettre à plat toute mon arborescence dans un tableau intermédiaire, trié par ordre croissant selon le rang de l'article (je pars de 1 depuis une feuille, et j'incrémente à chaque niveau jusqu'à atteindre le produit fini). Si je repasse sur un noeud déjà visité, alors je conserve le rang le plus élevé. Ca me semble plus pertinent de parcourir des composants vers les finis parce que finalement quand on modifie un article on veut propager les modifications de coût sur les parents, et pas les sur enfants.

J'ai comparé le résultat avec l'analyseur de performance, pour calculer 203 articles, 22,4s contre 39,7s avant (méthode qui occasionnait des calculs redondants). C'est déjà plus de 40% de gagné.

Je cherche encore à optimiser la collecte dans le tableau intermédiaire, pour être certain de n'avoir que des articles qui verront leur cout changer, mais je ne suis pas sur que cela soit possible.

EDIT : je suis maintenant à 16 secondes en optimisant mes requêtes sql, et en faisant un maximum de calcul dans la requête au lieu de le faire par code.
Exemple, avant je faisais :

Code :

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

1
2
3
4
5
6
7
Sql = "SELECT nmcl_qte_lien, art_prix_revient FROM nmcl, art WHERE nmcl_article = " + aid + " AND nmcl_op = " + op + " AND nmcl_fourniture = art_id"
HExécuteRequêteSQL(Rs2,Cnx,hRequêteDéfaut ,Sql)
TANTQUE PAS HEnDehors(Rs2)
	//trace(Rs2.art_reference + " " + Rs2.nmcl_qte_lien + " x " + Rs2.art_prix_revient)
	cout_fournitures = cout_fournitures + (Rs2.nmcl_qte_lien * Rs2.art_prix_revient)
	HLitSuivant(Rs2)
FIN

Maintenant, je fais :

Code :

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

1
2
3
4
5
6
Sql = "SELECT (nmcl_qte_lien * art_prix_revient) AS cout_fourniture FROM nmcl, art WHERE nmcl_article = " + aid + " AND nmcl_op = " + op + " AND nmcl_fourniture = art_id"
HExécuteRequêteSQL(Rs2,Cnx,hRequêteDéfaut ,Sql)
TANTQUE PAS HEnDehors(Rs2)
	cout_fournitures = cout_fournitures + Rs2.cout_fourniture
	HLitSuivant(Rs2)
FIN

C'est radical comme amélioration !

Je me demande s'il n'y aurait pas encore du temps à gagner en exécutant les requêtes en mode hRequêteSansCorrection, systématiquement ?