arbre n-aire delete

Version imprimable

arbre n-aire delete

j essaie de coder un arbre n-aire pour un moteur2D, le principe fonctionne bien mais j ai un probleme au niveau du delete (dans le destructeur de CObjectManager et vu que l arbre doit etre creer et effacer a chaque frame je ne peu pas laisser de fuite...
le code est composer de la classe CObject qui represente l element et de CObjectManager qui permet de gerer les elements (CObjectManager contient l element primaire ainsi qu un map de * pour acceder au element plus rapidement)

puis je n ai jamais coder ce genre de truc avant donc y a surement pas mal d erreur de debutant
toute idee d optimisation est la bienvenue! :D

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
 
#ifndef __COBJECT
#define __COBJECT
 
#include <map>
#include <vector>
#include <iostream>
#include <string>
 
class CObject
{
public:
	CObject();
	~CObject();
	CObject &operator=(const CObject &);
 
	std::string ID;
	std::vector<CObject*>	fils;
	CObject*				parent;
	void					Render();
};
 
class CObjectManager
{
public:
	CObjectManager();
	~CObjectManager();
 
	int		AddChild(std::string IDParent, std::string ID);
	int		RemoveChild(std::string ID);
	void	RenderTree();
	void	Reset();
 
	CObject	primaire;
 
private:
	std::vector<CObject*> element_restant;
	std::map<std::string, CObject*> element;
};
#endif

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
#include "CObject.h"
 
CObject::CObject(){
	this->parent = NULL;
}
 
CObject::~CObject(){
}
 
CObject &CObject::operator=(const CObject &source){
	this->ID = source.ID;
	this->fils = source.fils;
	this->parent = source.parent;
    return *this;
}
 
void CObject::Render(){
	std::cout << " < " << this->ID << " (" << this->fils.size() << ") > "; 
}
 
CObjectManager::CObjectManager()
{
	this->primaire.ID = "A";
	this->primaire.parent = NULL;
 
	this->element_restant.push_back(&this->primaire);
	this->element["A"] = &this->primaire;
}
 
CObjectManager::~CObjectManager()
{
	std::map<std::string, CObject*>::iterator it;
	for (it = this->element.begin(); it != this->element.end(); it++)
	{
		if (it->second != NULL)	
		{
			it->second->ID = "Z";
			it->second->fils.erase(it->second->fils.begin(), it->second->fils.end());
			it->second->parent = NULL;
			delete (it->second);
		}
	}
}
//============================
//	Ajoute un child
//============================
int CObjectManager::AddChild(std::string IDParent, std::string ID)
{
	std::map<std::string, CObject*>::iterator it = this->element.end();
 
	it = this->element.find(IDParent);
	if (it != this->element.end())
	{
		std::cout << "\n ID detecte: " << IDParent << " ajout de " << ID << std::endl;
 
		CObject* child = new CObject;
		child->ID = ID;
		child->parent = it->second;
		it->second->fils.push_back(child);
		this->element[ID] = child;
		return 1;
	}
	else return 0;
}
//============================
//	Supprime un child
//============================
int CObjectManager::RemoveChild(std::string ID)
{
	std::map<std::string, CObject*>::iterator it = this->element.end();
	std::vector<CObject*>::iterator vec_it;
 
	it = this->element.find(ID);
	if (it != this->element.end())
	{
		//enlever le fils ?
		//on itere sur le vector du parent
		for ( vec_it = it->second->parent->fils.begin(); vec_it != it->second->parent->fils.end(); vec_it++)
		{
			if ( (*vec_it)->ID == ID)break;
		}
		it->second->parent->fils.erase(vec_it);
 
		this->element.erase(it);
		delete it->second;
 
		return 1;
	}
	else return 0;
}
//====================================
//	Parcour l arbre
//====================================
void CObjectManager::RenderTree()
{
	std::vector<CObject*>::iterator it;
	CObject* current ;
	current = &this->primaire; //commence par le 1 noeud
do
{
	//ajoute les fils de l element a la liste a faire
	this->element_restant.insert(this->element_restant.end(), current->fils.begin(),current->fils.end());
 
	//enleve le 1 elements 
	it = this->element_restant.begin();
	this->element_restant.erase(it);
 
	//effectue le traitement
	current->Render();
 
	//passe a l element suivant
	current = this->element_restant.front();
 
}while(this->element_restant.size() != 0);
}
 
//===================================
//Remet l arbre a 0
//===================================
void CObjectManager::Reset(){
}

12/10/2004, 21h42
JolyLoic

Sans lire en détails, je vois quelques problèmes :

CObject : Tu défini le destructeur et l'opérateur d'affectation. Mais tu ne fais rien d'autre dedans que ce qui y est fait par défaut. Donc, soit tu fais autre chose (et dans ce cas, tu dois définir aussi le constructeur par copie), soit tu n'as pas besoin de les définir.

Dans le destructeur de CObjectManager, tu effaces deux fois les objets : Déjà en direct, ensuite en tant que fils de leurs pères : BOOM

C'est révélateur d'un manque de conception : qui possède (=qui est chargé de leur destruction) les objets ?

Est-ce le noeud père ? Dans ce cas, il suffit dans le destructeur du père de détruire les fils, est dans le destructeur du manager de détruire le noeud racine.

Est-ce la map ? Dans ce cas, le destructeur du père ne fait rien, et on efface simplement les objets dans la map, sans pour chaque objet regarder ses fils

Est-ce les deux ? Pour avoir une propriété partagée, remplace tes CObject* par des boost::shared_ptr<CObject>, qui implémentent cette propriété partagée.
16/10/2004, 11h52
Fry

merci pour ta reponse :)
mais je ne comprend pas pourquoi les object sont delete 2 fois?
sinon j ai inclu la destruction des fils dans le destructeur du pere (CObject) ainsi que l ajout de fils dans CObject aussi
j ai cependant garde la map pour acceder plus rapidement aux objects sans avoir a parcourir tout l arbre ansi que le parcour de l arbre dans CObjectManager...
le code marche mais j ai un gros probleme de rapidite en ajoutant 217 element et en les suprimant ensuite je ne peu le faire que 90 fois par seconde ce qui est beaucoup trop lent :?
est ce qu il est possible de creer les object dans un espace memoire reserve (de la taille du nbre d object max) ce qui permettrait de ne pas avoir a faire de delete juste reecrir par dessus
d ou vient ce pb de rapidite?
16/10/2004, 16h36
JolyLoic

Il existe des techniques pour allouer de la mémoire plus rapidement que ce que permet new quand tu connais des choses sur tes objets. Par exemple quand ils font tous la même taille. Regarde par exemple du côté des memory pools (boost::pool par exemple).
17/10/2004, 18h11
Fry

tout les object n ont pas la meme taille ca depend de la taille du vector vers les fils...

et me suis renseigner sur boost::pool ( typedef boost::singleton_pool<CObject, sizeof(CObject)*500> pool; )

le pb c est que ca ne permet que de faire malloc / free donc il y a un probleme avec le constructeur destructeur de l object

le seul moyen est de remplacer la classe CObject par une structure de taille fixe?
en definissant un nombre fixe pour le tableau de pointeur sur les fils
mais l utilisation de boost est plus rapide qu un de faire soit meme un malloc et de faire des memcpy dans la zone des structure?

est ce qu il est possible d utiliser les classes avec pool::malloc?
17/10/2004, 18h38
JolyLoic
Citation:

Envoyé par Fry

typedef boost::singleton_pool<CObject, sizeof(CObject)*500> pool;

Déjà, il faut à mon avis définir :

Code:

typedef boost::singleton_pool<CObject, sizeof(CObject)> pool; // Pas de *500

Ensuite, pour appeler correctement tes constructeurs/destructeurs, le mieux semble être d'utiliser un placement new :
Code:

1 2 3 4 CObject *ptr = new (pool::malloc()) CObject; // On utilise ptr... ptr->~Cobject(); pool::free(ptr);
Une autre solution, plus simple, consiste à utiliser un object_pool au lieu d'un singleton_pool. Par contre, cette classe ne permet par d'utiliser un pool pour des éléments d'un conteneur de la STL (pas de compabilité avec pool_alloc).
17/10/2004, 18h42
JolyLoic

Citation:

Envoyé par Fry

tout les object n ont pas la meme taille ca depend de la taille du vector vers les fils...

Ca n'empêche pas tes objets d'avoir la même taille, sizeof(vector<T>) est une constante. Par contre, la création de chaque CObjet demande elle aussi une allocation de mémoire, ce qui commence à être lourd.
17/10/2004, 19h40
Fry

je dois vraiment etre un boulet avec cette technique il n y a pas de difference niveau performance... :?
pourtant j ai construit mes object comme indique

en fait la pool ne fonctionne pas comme je pensais, est ce qu il n est pas possible de l utiliser pour allouer une quantite de memoire egal a la taille de chaque object * le nbr max d object
ce qui permettrait d allouer les object directement au dessus de cette memoire (en utilisant des pointeur) et de ne pas s occuper de la desallocation de chaque object en reecrivant a chaque fois par dessus
ca serait plus rapide comme ca?

parcque la je doit avoir des pb de conception parcque faudrait que j arrive a gagner au moins 50fps
17/10/2004, 21h04
JolyLoic

Si tu me passe un code complet (y compris le code de test de perfs), je peux jeter un coup d'oeil dessus, mais sans rien promettre.

voila le code complet (si t a vc.net je peut te passer le project par mail) il faut inclure le repertoire de boost pour utiliser boost::pool

main.cpp

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
#include <windows.h>
#include <iostream>
#include <sstream>
#include "CObject.h"
using namespace std;
 
bool frameRate();
 
int main()
{
	cout << "REALISATION DE L ARBRE DE RENDU" << endl;
	CObjectManager* t = new CObjectManager;	
 
	while (true)
	{
	t->AddChild("A", "B");
	t->AddChild("A", "C");
	t->AddChild("A", "D");
	t->AddChild("A", "E");
	t->AddChild("A", "F");
	t->AddChild("A", "G");
	t->AddChild("A", "H");
	t->AddChild("A", "I");
 
	//rempli child B
	for ( char c = 'A'; c <= 'Z'; c++)
	{
	stringstream buf;
	buf << "B";
	buf << c;
	t->AddChild( "B",  buf.str() );
	}
	//rempli child C
	for ( char c = 'A'; c <= 'Z'; c++)
	{
	stringstream buf;
	buf << "C";
	buf << c;
	t->AddChild( "C",  buf.str() );
	}
	//rempli child D
	for ( char c = 'A'; c <= 'Z'; c++)
	{
	stringstream buf;
	buf << "D";
	buf << c;
	t->AddChild( "D",  buf.str() );
	}
	//rempli child E
	for ( char c = 'A'; c <= 'Z'; c++)
	{
	stringstream buf;
	buf << "E";
	buf << c;
	t->AddChild( "E",  buf.str() );
	}
	//rempli child F
	for ( char c = 'A'; c <= 'Z'; c++)
	{
	stringstream buf;
	buf << "F";
	buf << c;
	t->AddChild( "F",  buf.str() );
	}
	//rempli child G
	for ( char c = 'A'; c <= 'Z'; c++)
	{
	stringstream buf;
	buf << "G";
	buf << c;
	t->AddChild( "G",  buf.str() );
	}
	//rempli child H
	for ( char c = 'A'; c <= 'Z'; c++)
	{
	stringstream buf;
	buf << "H";
	buf << c;
	t->AddChild( "H",  buf.str() );
	}
	//rempli child I
	for ( char c = 'A'; c <= 'Z'; c++)
	{
	stringstream buf;
	buf << "I";
	buf << c;
	t->AddChild( "I",  buf.str() );
	}
 
	if (frameRate())
	{
		cout << "Taille: " << t->GetNumberCObject() << std::endl;
		cout << "\n==============================\n";
		//t->RenderTree();
		cout << "\n==============================\n";
	}
	t->Reset();
	}
 
	delete t;
	cin.ignore();
	getchar();
	return 0;
}
 
bool frameRate() 
{ 
	static int fps = 0;					
	static int lastTime = 0;		   
	++fps; 
	if( ( GetTickCount() - lastTime) > 1000 ) 
	{ 
		std::cout << "\n========================>FPS: " << fps << std::endl;
		lastTime =  GetTickCount();
		fps = 0;   
		return true;
	} 
	else return false;
}

CObject.h

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
 
#ifndef __COBJECT
#define __COBJECT
 
#include <map>
#include <vector>
#include <iostream>
#include <string>
#define __WIN32__
#define  BOOST_NO_STDC_NAMESPACE
#include <singleton_pool.hpp>
 
class CObject
{
public:
	CObject(std::string id);
	~CObject();
 
	CObject*				parent;
	std::vector<CObject*>	fils;
 
	void					AddChild(CObject* child);
	void					Render();
	std::string				ID;
};
 
class CObjectManager
{
public:
	CObjectManager();
	~CObjectManager();
 
	int	AddChild(std::string IDParent, std::string ID);
	void	RenderTree();
	void	Reset();
	int	GetNumberCObject();
 
	CObject*	primaire;
	std::vector<CObject*> element_restant;
	std::map<std::string, CObject*> element;
};
 
typedef boost::singleton_pool<CObject, sizeof(CObject)> my_pool;
 
#endif

Cobject.cpp

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
#include "CObject.h"
 
//====================================================
//	Constructeur de l element
//====================================================
CObject::CObject(std::string id)
{
	this->ID = id;
	this->parent = NULL;
}
//=======================================================
//	Destructeur de l element charge de detruire les fils
//=======================================================
CObject::~CObject()
{
	//std::cout << "Destructeur de " << this->ID << std::endl;
	if (this->fils.size() != 0)
	{
		std::vector<CObject*>::iterator it;
		for ( it = this->fils.begin(); it != this->fils.end(); it++)
			my_pool::free(*it);
	}
}
 
void CObject::Render()
{
	std::cout << " < " << this->ID << " (" << this->fils.size() << ") > "; 
}
 
//===========================================
//	Constructeur du manager
//===========================================
CObjectManager::CObjectManager()
{
	primaire = new ( my_pool::malloc() ) CObject("A");
	this->primaire->parent = NULL;
	this->element["A"] = this->primaire;
	this->element_restant.push_back(this->primaire);
}
//============================================
//	Destructeur du manager
//============================================
CObjectManager::~CObjectManager()
{
	my_pool::free(this->primaire);
}
//============================
//	Ajoute un child
//============================
int CObjectManager::AddChild(std::string IDParent, std::string ID)
{
	std::map<std::string, CObject*>::iterator it = this->element.end();
	it = this->element.find(IDParent);
	if (it != this->element.end())
	{
		CObject* child = new ( my_pool::malloc() ) CObject(ID);
		child->parent = it->second;
		it->second->fils.push_back(child);
		this->element[ID] = child;
		return 1;
	}
	else return 0;
	return 0;
}
//====================================
//	Parcour l arbre
//====================================
void CObjectManager::RenderTree()
{
	std::vector<CObject*>::iterator it;
	CObject* current ;
	current = this->primaire; //commence par le 1 noeud
do
{
	//ajoute les fils de l element a la liste a faire
	this->element_restant.insert(this->element_restant.end(), current->fils.begin(),current->fils.end());
 
	//enleve le 1 elements 
	it = this->element_restant.begin();
	this->element_restant.erase(it);
 
	current->Render();
 
	//passe a l element suivant
	current = this->element_restant.front();
 
}while(this->element_restant.size() != 0);
}
 
//===================================
//Remet l arbre a 0
//===================================
void CObjectManager::Reset()
{
	//effacer object primaire
	my_pool::free(this->primaire);
 
	//recreer object primaire
	primaire = new ( my_pool::malloc() ) CObject("A");
	this->primaire->parent = NULL;
	this->element_restant.push_back(this->primaire);
	this->element["A"] = this->primaire;
}
 
int CObjectManager::GetNumberCObject()
{
	return this->element.size();
}

c cool d essayer d ameliorer mon code :wink:

Je viens de faire un test à la con, en passant le programme de debug à release, je suis passé de 13/14 fps à plus de 300fps...

J'ai aussi remplacé quelques passages d'arguments string par des arguments string const &, mais je ne sais pas si ça joue.

Au fait, j'ai l'impression que tu n'aime pas les fonctions récursives. Pourtant, quand un a un arbre, c'est souvent plus simple à gérer...

Par exemple, pour mes tests, j'ai réécrit la fonction Render ainsi, ce qui fait du code à mon avis plus simple :
Code:

1 2 3 4 5 6 7 8 9 void CObject::Render(int tab) { std::string header(tab, ' '); std::cout << header << " < " << this->ID << " (" << this->fils.size() << ") > " << std::endl; for(std::vector<CObject*>::iterator it = fils.begin() ; it!=fils.end() ; ++it) { (*it)->Render(tab+1); } }

Encore plus fort, pris d'un soupçon, j'ai remplacé ton main par :
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 void FillChild(string const &father, CObjectManager* t) { for ( char c = 'A'; c <= 'Z'; c++) { t->AddChild( father, father+c); } } int main() { cout << "REALISATION DE L ARBRE DE RENDU" << endl; CObjectManager* t = new CObjectManager; while (true) { t->AddChild("A", "B"); t->AddChild("A", "C"); t->AddChild("A", "D"); t->AddChild("A", "E"); t->AddChild("A", "F"); t->AddChild("A", "G"); t->AddChild("A", "H"); t->AddChild("A", "I"); FillChild("B", t); FillChild("C", t); FillChild("D", t); FillChild("E", t); FillChild("F", t); FillChild("G", t); FillChild("H", t); FillChild("I", t); // Suite comme avant
Résultat : 1200 fps

Encore plus fort, je me dis que quand on ajoute n fils à un seul père, il n'est pas utile de rechercher le père à chaque fois. J'écris donc :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 void FillChild(string const &father, CObjectManager* t) { CObject *f = t->element[father]; for ( char c = 'A'; c <= 'Z'; c++) { string childName(father+c); CObject* child = new ( my_pool::malloc() ) CObject(childName); child->parent = f; f->fils.push_back(child); t->element[childName] = child; } }
Résultat : 1700fps

Comme quoi, j'ai eu raison de demander ton programme de test de performances : C'est là qu'il y a beaucoup à gagner ;)

Je n'ai pas pu faire mon dernier test, remplacer

Code:

std::vector<CObject*>

Par

Code:

std::vector<CObject* , boost::pool_allocator<CObject *> >

Car mon compilateur a l'air de ne pas accepter...

19/10/2004, 15h06
Fry
j ai pas compris pourquoi le code est passer de 80 a 2000 fps mais bon c nikel :D
une derniere question ds le code que j ai mis sur le site y a une sacree fuite memoire car en fait j arrive pas a delete les object creer avec
Code:

1 2 primaire = new ( my_pool::malloc() ) CObject("A");
j ai essaye:
Code:

1 2 3 4 5 6 my_pool::free(primaire); //marche bien mais n appel pas le destructeur => child non detruit delete primaire; // plante delete ( my_pool::free() )primaire; // ne compile pas
sans succes quelle est la bonne syntaxe?

sinon en utilisant les new et delete standard ca tourne bien mais ca perd un peu de vitesse
merci de ton aide :D
19/10/2004, 21h22
JolyLoic
Citation:

Envoyé par Fry

une derniere question ds le code que j ai mis sur le site y a une sacree fuite memoire car en fait j arrive pas a delete les object

Effectivement, j'avais corrigé dans mon code, mais j'ai oublié de le signaler, j'avais indiqué la technique un peu plus haut...
Code:

1 2 3 4 5 CObjectManager::~CObjectManager() { primaire->~CObject(); my_pool::free(this->primaire); }
En fait, la syntaxe qui ressemble à l'appel d'un destructeur est la contrepartie du new de placement.