Piste d'amélioration d'une chaînes d'objets

On Nov 2, 9:53 am, val...@gmail.com wrote:

J'ai créé un système de nœuds (une sorte d'arbre), ou chacun
peut avoir entre 1 et 4 fils via des pointeurs. Pour s'évaluer
le nœud racine appelle classiquement ses fils tours à tours
qui renvoient une valeur (tout est fait en chaine).

Malheureusement, le temps d'exploration de l'arbre est de plus
en plus long ( > linéaire ) lorsque sa taille grandit. Je m'y
prends peut être mal, je voulais donc avoir des conseils sur
ce genre de structures. Notamment, je me demandait si les
créer dans des zones contiguës de la mémoire pouvait améliorer
leur temps de recherche.

Sans plus de détails, c'est difficile à dire, mais s'il faut
visiter chaque nœud de l'arbre pour avoir la valeur, le mieux
que tu pourras faire, c'est bien O(n).

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

In article <17286d47-685f-48f6-8fef-f8023e97c789@e1g2000pra.googlegroups.com>,
<valasg@gmail.com> wrote:

Salut

J'ai créé un système de nœuds (une sorte d'arbre), ou chacun peut
avoir entre 1 et 4 fils via des pointeurs. Pour s'évaluer le nœud
racine appelle classiquement ses fils tours à tours qui renvoient une
valeur (tout est fait en chaine).

Malheureusement, le temps d'exploration de l'arbre est de plus en plus
long ( > linéaire ) lorsque sa taille grandit. Je m'y prends peut être
mal, je voulais donc avoir des conseils sur ce genre de structures.
Notamment, je me demandait si les créer dans des zones contiguës de la
mémoire pouvait améliorer leur temps de recherche.

Tu n'en dis absolument pas assez sur ce que tu essaies d'implementer comme
algorithme pour qu'on puisse t'aider.

En particulier, tu dis que le temps d'exploration de l'arbre est >lineaire
lorsque l'arbre grandit. Par rapport a quoi comme taille ? si tu veux
parcourir tout un arbre, le mieux que tu auras, comme le dit James, c'est
du O(n), avec n le nombre total de noeuds dans l'arbre.

Est-ce que c'est ce que tu observes, ou est-ce que c'est pire ?

Est-ce que ta structure est un arbre veritable, sans boucles ? ou un graphe
acyclique oriente (un DAG) avec partage de donnees ? ou un graphe avec de
peu nombreux cycles ? ca peut orienter pour ton parcours ?

Apres, la 2e question, c'est est-ce que tu as besoin de parcourir tout
l'arbre systematiquement ? tu fais quoi avec ces valeurs ? est-ce que tu
as besoin de toutes les valeurs de tous les noeuds de facon independante,
ou est-ce que tu les combines pour obtenir un resultat final ? dans le second
cas, si tes noeuds changent peu souvent par rapport aux parcours de l'arbre,
tu dois pouvoir gagner enormement en creant un cache de valeurs...

Alors pour faire simple mes noeuds dérivent tous de cette classe

class CNode
{
protected:

string _name;
double _value;
bool _is_computed;

virtual void Compute() = 0;

public:

virtual void Reset() = 0;
double GetValue();

CMCLNode( const string& Dame );
~CMCLNode() {}
};

double CMCLNode::GetValue()
{
if ( !_is_computed )
{
Compute();
_is_computed = true;
}
return _value;
}

en gros je crée plein de noeud, reliés entre eux via des pointeurs, et
je fais

node->GetValue() ;

pour évaluer la racine qui va évaluer le rester de l'arbre en cascade
en jouant sur la variable is_computed pour ne pas repasser 2 fois dans
le meme noeud
(qui peuvent être recombinés)
puis

node->Reset() pour remettre à 0 les noeuds de proche en proche

le tout répété un grand nombre de fois

J'observe que justement le temps croît bcp plus que linéaire qd le
nombre de noeuds augmente linéairement
Je soupçonne le cpu de perdre de plus en plus de temps à recherche des
noeuds lorsqu'ils sont très éloignés dans la mémoire

Merci pour vos suggestions
G

Gégé <valasg@gmail.com> writes:

Merci pour vos suggestions

Faire la même chose pour reset que pour compute, éviter de passer plusieurs
fois dans les descendants d'un même noeud.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Le reset est codé de la même facon dans les classes filles

void CNode_A::Reset()
{
if ( _is_computed )
{
_is_computed = false;
_prev_node->Reset();
_next_node->Reset();
}
}

par contre quoiqu'il arrive, je vais dans l objet, même s'il est deja
évalué pour tester ce is_computed
Ça serait peut être mieux de faire le test en restant dans le noeud
qui possède les liaisons ...

void CNode_A::Reset()
{
if ( !_is_prev_node_computed ) _prev_node->Reset();
if ( !_is_next_node_computed ) _next_node->Reset();
}

Gégé <valasg@gmail.com> writes:

Le reset est codé de la même facon dans les classes filles

void CNode_A::Reset()
{
if ( _is_computed )
{
_is_computed = false;
_prev_node->Reset();
_next_node->Reset();
}
}

par contre quoiqu'il arrive, je vais dans l objet, même s'il est deja
évalué pour tester ce is_computed
Ça serait peut être mieux de faire le test en restant dans le noeud
qui possède les liaisons ...

void CNode_A::Reset()
{
if ( !_is_prev_node_computed ) _prev_node->Reset();
if ( !_is_next_node_computed ) _next_node->Reset();
}

Ca ne changera pas la complexité, hors c'est un problème de complexité que
tu dis avoir.

Avec ce que tu expliques, Compute() et Reset() sont appelés pour chaque
noeud autant de fois qu'il y a d'arc entrant dans ce noeud. Comme le
nombre d'arcs sortant par noeud est borné, cela veut dire que le nombre
moyen d'arc entrant l'est aussi. Je ne vois donc pas de raison d'un
comportement non linéaire (l'action des caches peut changer la pente quand
le nombre de noeuds augmente, mais c'est tout).

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Donc si je comprends bien, la structure de mon arbre ne semble pas
être la cause de ces lenteurs .... il faut peut être que je remette en
cause les caculs effectués par mes noeuds. Ce que je constate c'est le
temps total, pas seulement le temps de parcours de l'arbre ... je vais
refaire des tests plus unitaires, et je vous tiens au courant.

Pour info, c'est un Montecarlo que je simule, les feuilles sont des
nombres aléatoires générés avec GSL. La moyenne de toutes mes racin es
sera donc la valeur de mon intégrale finale. Le nombre de noeuds est
en relation avec le pas de temps de ma discrétisation.

J'ai réduit les calculs des nœuds au plus simple : évaluation du nœ ud
fils et assignation d'une valeur constante.
Voici 2 tests caractéristiques :

* 14610 created nodes : 1285.68 Ko => exec_time = 4.718 sec ( 20000
itérations )
* 7310 created nodes : 643.28 Ko => exec_time = 1.61 sec ( 20000
itérations )

Quand je double ma structure, mon temps d exécution triple ....


void CNode_A::ComputeFixing()
{
double s = _node->GetValue(); // <<<<< qui est lui meme de
type CNode_A
value = 100;
}

J'avoue que je suis très perplexe ...

Gégé a écrit :

J'ai réduit les calculs des nœuds au plus simple : évaluation du nœud
fils et assignation d'une valeur constante.
Voici 2 tests caractéristiques :

* 14610 created nodes : 1285.68 Ko => exec_time = 4.718 sec ( 20000
itérations )
* 7310 created nodes : 643.28 Ko => exec_time = 1.61 sec ( 20000
itérations )

Quand je double ma structure, mon temps d exécution triple ....

[snip]

J'avoue que je suis très perplexe ...

Si tu utilises gcc, essayes d'utiliser gprof pour voir où ton programme
passe son temps.

Tu gagnera du temps par rapport à des essais globaux comme ça. Et puis
gprof c'est juste une option de compilation.

--
Michael

Effectivement ce genre d'outils peut m'être très utile ! Merci.
Malheureusement, j'utilise VC2005, tu connais un équivalent ?