Discussion :

[tachaout]

Bonjour,

je dois créer un arbre d'objets à partir d'une liste. Le principe est le suivant:
Pour chaque objet O de la liste

si O existe déjà dans l'arbre (sa valeur) alors

on passe à l'objet suivant de la liste

sinon

créer un nouvel objet O' (avec new) qui est copie de O

Insérer O' dans l'arbre

Passer à l'objet suivant de la liste

FinSi

FinPour

Mon problème est que les multiples appels à "new" retardent énormément l'exécution. Je crois savoir qu'on pouvait s'allouer des blocs entiers de mémoire
et aller piocher dedans quand on a besoin de faire un "new" pour un nouvel objet.

Quelqu'un aurait-il l'amabilité de nous expliquer comment ça marche.

[Invité]

Bonjour,
Ca m'étonnerait assez que vous réussissiez à faire un algorithme d'allocation d'espace mémoire plus rapide que celui qui existe déjà.
Par contre, si vous faites beaucoup de "new + delete", là ça vaut le coup de réserver un tableau à l'avance.
Je pense que le mieux serait que vous montiez votre code.

[Joel F]

Alloue un bloc d'octet nu une bonne fois pour toute et utilise le new de placement pour construire tes objets dans la mémoire préallouée.

boost::pool résout déjà ce genre de problème.

[tachaout]

Merci pour ces premières réponses.
Je mets une partie du code permettant de préciser le problème. Il s'agit
de construire un arbre préfixe à partir d'une liste de mots. J'ai pensé
m'allouer un vecteur de taille n d'objets et aller piocher dedans. Quand le vecteur est épuisé, on augmente sa taille ex: on y ajoute n cases. Comme ça, si au total j'ai besoin de faire m appels à "new", avec le vecteur, j'en ferai seulement m/n fois.

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
 
list<String> lesMots; //exemple: les mots du dictionaire
 
class noeud
{
public:
	char lettre;
	list<noeud *> les_fils; // la liste des fils
};
 
list<noeud *> arbreP;
 
void inserer_dans_arbre(unsigned int i, String &v, list<noeud *> &racine,  unsigned int &k){
	// i est la position dans le mot
	// v est le mot
	// racine est la racine du sous-ararbre dans lequel on insère
	// k est la taille du mot
	list<noeud *>::iterator it=racine.begin();
	while(it!=racine.end() && (*it)->lettre!=v[i]){
		it++;
	}
	if(it!=racine.end()){//il y est, donc juste passer à la lettre suivante
		if(i+1<k){//on n'a pas épuisé le mot
			inserer_dans_arbre(i+1, v, (*it)->les_fils, k);
		}
	}
	else{//il n'y est pas
		//////////////////////////////////////////////////////////////////////
		noeud * p=new(noeud); //c'est la partie couteuse
		/////////////////////////////////////////////////////////////////////
		p->lettre=v[i];
		racine.push_back(p);
		if(i+1<k){//on n'a pas épuisé le mot
			inserer_dans_arbre(i+1, v, p->les_fils, k);
		}
	}
}
int main(){
	//On récupère la liste des mots. Ensuite on crée l'arbre comme suit
	for(list<String>::iterator it=LesMots.begin(); it!=LesMots.end(); ++it){
		size_t k=(*it).size();
		inserer_dans_arbre(0, (*it), arbreP, k);
	}
	return 0;
}

[Flob90]

Si ce sont des petits objet, loki::SmallObject peut t'aider.

@Pierre Dolez: Le système d'allocation n'est pas parfait surtout pour les petits objets, pour ca qu'il existe plétore d'allocateur pour eux (j'ai cité Loki mais il y en a peut-etre dans boost).

[Invité]

Oui, ça ressemble tout à fait à une structure de liste chainée.
Ce qui me gène un peu dans l'organisation, la classe Noeud comporte 2 informations la lettre (1 octet) et un pointeur sur la liste des noeuds fils 4 octets. C'est à dire que l'espace utilisé, sauf la lettre, ne sert qu'à décrire l'arbre.
Pour un essai de rapidité, essayez de remplacer

Code :

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

1
2
3
		noeud * p=new(noeud); //c'est la partie couteuse
// par 
                noeud *p=(noeud*)malloc(sizeof(noeud));

D'autre part, vous passez des paramètres à la fonction par référence, c'est à dire que leur valeur sera modifiée au retour, est-ce souhaité? ne vaudrait-il pas mieux mettre const ?
Avez-vous un fichier d'essai?
Je suppose que le but est d'utiliser l'arbre, une fois réalisé, ça ne me semble pas trop grave si sa création demande un peu de temps, pourvu que l'utilisation est rapide.

[tachaout]

j'ai essayé de remplacer

Code :

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

1
2
3
noeud * p=new(noeud);
par
noeud *p=(noeud*)malloc(sizeof(noeud));

il semble qu'il y a un problème avec l'appel de p->les_fils;
ça fait une erreur d'exécution. On dirait qu'il ne la crée pas cette liste.
j'ai par exemple testé :
cout<<p->les_fils.size()<<endl;
l'exécution s'arrête

Sinon, je suis en train de me documenter sur les allocateurs, j'avoue que
je ne connaissais pas <memory> (débutant )

Merci pour les bons tuyaux

[Invité]

Bonsoir,
Ca ne m'étonne qu'à moitié.
En effet les deux lignes sont équivalentes. Il y aurait pu avoir une petite différence de temps d'exécution : information intéressante, mais c'est plus grave, vous adressez probablement des régions mémoire interdites.
J'ai presque terminé de le réécrire à ma sauce, à demain.

[Davidbrcz]

En effet les deux lignes sont équivalentes

Absolument pas !!!! new appelle le constructeur de l'objet, malloc ne fait que réserver de la mémoire. Les comportements NE SONT PAS DU TOUT équivalents, ce qui explique le plantage décrit (la mémoire pour le noeud est réservée mais aucun n'objet n'est construit, en particulier les_fils).

Sinon, tout a déjà été dit par Joel Et Flob90 (allocateur spécialisé dans loki ou boost, placement new si on veut faire les choses à la main)

[Goten]

boost::pool est plus que controversé aux dernières nouvelles...

[Flob90]

@Goten: Tu aurais un document/une discussion sur le sujet ?

[Goten]

Non, je l'ai juste croisé sur la ML plusieurs fois. (certaine personne parlait de le deprecated il me semble) car free() (enfin, l'équivalent sémantique, je me rappelle plus le nom exact) est vraiment lent IIRC!.

[Joel F]

Oui je m'en rappelles. Y a un bug dans la desallcoation d'une variante de pool.
Llib en elle meme n'a pas été rafraichie depuis un bout de temps.

Patches welcome.

[Invité]

@Davidbrcz

Citation:
En effet les deux lignes sont équivalentes
(réponse)
Absolument pas !!!! new appelle le constructeur de l'objet, malloc ne fait que réserver de la mémoire. Les comportements NE SONT PAS DU TOUT équivalents, ce qui explique le plantage décrit (la mémoire pour le noeud est réservée mais aucun n'objet n'est construit, en particulier les_fils).

New appelle le constructeur de l'objet, mais justement il n'y en pas.
Les_fils est déclaré, son type, mais ni initialisé, encore moins construit.
Tel que je vois partir ce sujet, ce sera un joli débat entre spécialistes.
tachaout est débutant, si vous préférez que je me retire tout de suite, dites-le, et proposez-lui des verrues à C++ (standard ou périmé ou historique, on ne sait plus)

[Davidbrcz]

New appelle le constructeur de l'objet, mais justement il n'y en pas.

Si. Il est juste synthétisé par le compilateur quand le le programmeur n'en fournit pas (tout comme l'est le constructeur de copie, operator= et le destructeur). C'est le gang des "Big Four". Cf la norme pour les détails.

Les_fils est déclaré, son type, mais ni initialisé, encore moins construit.

Si, si, il l'est (cf au dessus).

tachaout est débutant,

débutant n'est pas synonyme d'incompétent ! Et au vu de son utilisation de la STL, je pense qu'il est sur la bonne voie pour apprendre.

et proposez-lui des verrues à C++ (standard ou périmé ou historique, on ne sait plus)

Loki ou boost des verrues du C++ ? Soit j'ai très mal compris, soit c'est vraiment une preuve que vous n'avez jamais regardé en détail aucune de ces deux bibliothèques.

[Invité]

Effectivement, je n'ai jamais regardé ces bibliothèques.
Donc, le me sens incompétent pour continuer à le renseigner.
PS et je ne les regarderai jamais.

[Davidbrcz]

Effectivement, je n'ai jamais regardé ces bibliothèques.
Donc, le me sens incompétent pour continuer à le renseigner.
PS et je ne les regarderai jamais.

Et pourquoi donc ne pas regarder ce qu'elles offrent ? Ce sont des très bons outils écrits par des gens extrêmement compétents , qui offrent des fonctionnalités fortes intéressantes et surtout très utiles dans un grand nombre de cas.

[Invité]

Et pourquoi regarder?
J'ai tout ce qu'il me faut.

[tachaout]

Donc, le me sens incompétent pour continuer à le renseigner.

ça serait dommage de priver un "débutant" de tes conseils à cause de discussions entre "mentors" sachant qu'il y a certainement des visiteurs du forum encore plus "débutants"

[Invité]

Bon, alors je répond. Voici le code
J'utilise la bibliothèque Borland (VCL)
Certaines lignes de l'entête sont peut-être inutiles.
J'utilise 2 classes de Borland
AnsiString, très voisin de string, mais il faut vérifier si le 1er caractère est de rang 0 ou de rang 1.
TList, c'est une liste de pointeurs.
La structure NOEUD définit le lattre concernée et un pointeur sur la liste éventuelle des fils. Ce pointeur existe toujours, mais la liste peut être vide.
Cette structure est traitée pas le compilateur comme une classe.
Elle comporte un constructeur qui crée la liste, et un destructeur.
J'ai fait quelque changements, par exemple la longueur du mot n'est pas passée en paramètre.
Pour être tout à fait franc, je n'ai pas compris le but de ce calcul, donc je ne peux pas vraiment vérifier qu'il est bon.

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
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
#include <vcl.h>
 
#include <vcl\Classes.hpp>
#include <vcl\SysUtils.hpp>
#include <vcl\Windows.hpp>
#include <vcl\System.hpp>
#include <conio.h>
#include <stdio.h>
 
typedef struct NOEUD
{
	char lettre;
	TList *les_fils; // la liste des fils
        NOEUD(char L)
        {
          lettre = L;
          les_fils = new TList();
        }
        ~NOEUD(){/* à faire*/}
}TabNOEUD;
typedef TabNOEUD* ptrNoeud;
 
int inserer_dans_arbre(unsigned int rang,
                       const AnsiString &v,
                       TList *racine)
{
        int i=rang;
	// i est la position dans le mot  (rang)
	// v est le mot
	// racine est la racine du sous-ararbre dans lequel on insère
	unsigned int k=v.Length();// k est la taille du mot
        char Lettre=v[i];
        int ir;
        ptrNoeud it=NULL;
        for ( ir=0; ir< racine->Count; ir++)
        {
          it=(ptrNoeud)racine->Items[ir];
          if (it->lettre == Lettre) break;
        }
        if (ir < racine->Count)
        {
          if (++i < k && it != NULL)
            inserer_dans_arbre(i, v, it->les_fils);
        }
	else
        {//il n'y est pas
		//////////////////////////////////////////////////////////////////////
	  ptrNoeud p=new NOEUD(Lettre); //c'est la partie couteuse
		/////////////////////////////////////////////////////////////////////
          racine->Add(p);
          if (++i < k )
            inserer_dans_arbre(i, v, p->les_fils);
	}
        return 0;
}
 
voidl Afficher(ptrNoeud noeud)
{
  TList *Fils=noeud->les_fils;
  if (Fils != NULL)
  {
    printf("\n Lettre=%c %d fils",noeud->lettre, Fils->Count );
    for (int i=0; i<Fils->Count; i++)
    {
      ptrNoeud unFils =(ptrNoeud)Fils->Items[i];
      Afficher(unFils);
    }
  }
}
int main(){
	//On récupère la liste des mots. Ensuite on crée l'arbre comme suit
        ptrNoeud arbreP = new NOEUD(0); // le premier niveau de noeuds
        for (int i=0; i< 11; i++)
        {
          AnsiString v;
          switch(i)
          {
            case 0:  v="zero"; break;
            case 1:  v="un";  break;
            case 2:  v="deux";  break;
            case 3:  v="trois";  break;
            case 4:  v="lundi"; break;
            case 5:  v="mardi"; break;
            case 6:  v="mercredi"; break;
            case 7:  v="jeudi"; break;
            case 8:  v="ventredi"; break;
            case 9:  v="samedi"; break;
            case 10:  v="dimanche"; break;
          }
          inserer_dans_arbre(1, v, arbreP->les_fils);
          // le premier caractères est 1 et non 0 pour un AnsiString
        }
        Afficher(arbreP);
        while (!kbhit()); // ou system("pause");
	return 0;
}

La fonction kbhit() attend la frappe d'un caractère. On peut remplacer cette ligne pas "system("pause");