les tableaux dynamiques

Version imprimable

Voir 40 message(s) de cette discussion en une page

12/12/2009, 14h04
étoile de mer

les tableaux dynamiques

bonjour à tous,
J'ai une question à proppos des tableaux dynamiques:
J'ai crée une tableau de hachage où j'ai stockes des paires de mots à partir d'un fichier texte lu, et là on me conseille de faire des tableau dynamiques pour cette table de hachage ou je vais stocker des pointeurs de structures de mots.
Là franchement je vois pas pourkoi des tableau et pourquoi pas un seul tableau dynamiques .
merci
12/12/2009, 14h20
AndreiS

Si je comprends bien, c'est le problème de conflits de hachage: la fonctionne de hachage peut retourner le même résultat pour deux mots différents. Donc dans ton tableau pour chacun 'hash' tu stockes plusieurs paires de mots et quand on cherche la valeur pour une clé, il faut que tu vérifie tous les pairs stockées pour son 'hash'.

tableau de structure dynamique

Re,
Là j'ai creé un tableau dynamique
Code:

1 2 3 4 5 6 struct tableauDynamique_struct { int *tab; size_t taille; size_t capacite; };
où je vais stocker la listes de structure
Code:

1 2 3 4 5 6 struct Dsequence { MotCompact *p2seq; MotCompact *pMotGauche; MotCompact *pMotDroit; };
je trouve un probleme dans l'operation du remplissage du tableau :
en fait je parcours la table de hachage qui contient des paires de mots et là je dois remplir la structure par ces paire de mots
voilà la fonction où je bloque qui ajoute un element au tableau dynamique
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 int TableauDynamique_struct_ajouter(struct tableauDynamique_int *pThis,char *seq,char *pMotGauche,char *pMotDroit)) { assert(pThis->taille <= pThis->capacite); /* Agrandir le tableau si besoin est. */ if(pThis->taille == pThis->capacite) { size_t nouvelleCapacite = (pThis->capacite < 4 ? 4 : (size_t)(pThis->capacite*1.5)); if(realloc_int(&pThis->tab, nouvelleCapacite) >= 0) { pThis->capacite = nouvelleCapacite; } else return -1; } /* ajouter */ pThis->tab[ pThis->taille++ ] = nouvelleValeur; return 0; }
pour ajouter je vois pas quoi faire?:calim2:
des idées svp?
merci

Bonjour,

Pour le fonction d'ajout, il y a deux manières de voir la chose.

Une que je dirai de dangereuse, qui serai de remplir une structure avec directement les pointeurs qui sont passer à la fonction:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
int TableauDynamique_struct_ajouter(struct tableauDynamique_int *pThis,char *seq,char *pMotGauche,char *pMotDroit))
{
     // ...
 
     /* ajouter */
     {
          Dsequence ds;
          ds.p2seq = seq;
          ds.pMotGauche = pMotGauche;
          ds.pMotDroit = pMotDroit;
 
         pThis->tab[ pThis->taille++ ] = ds;
     }
}

Sinon, avec une gestion de la mémoire moins risqué, mais qui prend un peu de temps, et qui faut faire aussi très attention à la libération:

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
 
int TableauDynamique_struct_ajouter(struct tableauDynamique_int *pThis,char *seq,char *pMotGauche,char *pMotDroit))
{
     // ...
 
     /* ajouter */
     {
          Dsequence ds;
          ds.p2seq = malloc ( strlen(seq) * sizeof(char) );
          if ( ds.p2seq == NULL )
         {
                  return -1;
         }
         strcmp(ds.p2seq, p2seq);
 
          ds.pMotGauche = malloc ( strlen(pMotGauche) * sizeof(char) );
          if ( ds.pMotGauche == NULL )
         {
                  return -1;
         }
         strcmp(ds.pMotGauche, pMotGauche);
 
          ds.pMotDroit = malloc ( strlen(pMotDroit) * sizeof(char) );
          if ( ds.pMotDroit == NULL )
         {
                  return -1;
         }
         strcmp(ds.pMotDroit, pMotDroit);
 
         pThis->tab[ pThis->taille++ ] = ds;
     }
}

Sinon, AndreiS a soulevé un bon point, qu'il ne faut pas oublier dans les table de hachage. Lorsque l'on tombe sur deux mêmes clés, il faut garder les deux valeurs pour cette clé ( utilisation d'une liste chainée de préférence ).

13/12/2009, 14h22
étoile de mer

Re,
Là on ma dit qu'il faut plusieurs tableau dynamiques, parce que c'est sur ça que repose une table de hachage: Elle sert à répartir les données sur différents conteneurs de même type, pour accélérer la recherche. :roll:
13/12/2009, 16h56
Médinoc

attention étoile de mer, "tab" n'a pas le bon type ici.
Il faut un pointeur de struct Dsequence, pas un pointeur de int...
13/12/2009, 17h23
étoile de mer

Merci Médinoc :)

Code:

int TableauDynamique_struct_ajouter(struct tableauDynamique_int *pThis,char *seq,char *pMotGauche,char *pMotDroit))

c'est dans cette ligne l'erreur?
j'ai pênsé que c'est le type du retour qui est un entier non?
13/12/2009, 18h07
Médinoc

pThis doit être de type struct tableauDynamique_struct *, et je ne suis pas sûr des paramètres de type char*.

Pour référence, voici notre conversation sur MSN:

pour ça, je propose de créer une nouvelle table de hachage, une simple cette fois-ci.
pk?
je vois pas lutilité
parce qu'on a besoin de rapidement retrouver la fréquence d'un 2-mot à partir de deux 1-mot, non?
là jai deja 2 tableau
remplie
une avec les 2mot
et lautre avec les mots
mais il faut retrouver *rapidement* un 2-mot... oui
bien sur
Sinon, on peut se contenter d'un tableau trié et d'une recherche dichotomique, mais ça risque de prendre du temps. et cette table de hach va contenir koi? les 2mots ou bien les mot?
C'est pour quoi je préconisais une table de hachage, répartissant sur des tableaux triés de pointeurs sur MotComplet Les 2-mot
oui
Conteneur principale: Table de hachage Sous-conteneur de la table de hachage: Tableaux dynamiques triés (qu'on compactera peut-être après avoir créé la table, pour une meilleure localité) Clé: char const * (2-mot) Valeur: MotCompact*
oui..
c un peu compliké là non?
En plus, il ne devrait pas y avoir de doublons pour les 2-mots, on pourra donc créer la table de hachage sans recherche, et ne trier les tableaux qu'à la fin
ça simplifie la création de la table
Déjà, il nous faut une structure pour les tableaux dynamiques
On peut repartir du code que j'avais fait pour tableaudynamique_int, que je n'utilise plus
On va en faire un tableaudynamique_ptrMotComplet
tu as fait ca dans lautre projet?
je ne crois pas
Mais dans la "mauvaise" version de NombreLignesCommunes, on utilisait un tableaudynamique_int ce doit être une structure du genre: int *pValeurs size_t taille size_t capacite
ok
mais là je trouve une difficulté comment imaginer cette table de hachage
avec le tableay dynamique
Un simple tableau de structures tableauDynamique_ptrMotCompact au lieu d'un tableau de listes chaînées.
Et on peut mettre sans problème un taux de croissance supérieur au nombre d'or (genre 2) si on compacte le tout à la fin de toute façon...
ok
ok
reste un autre souci là
par example jai la 2seq
bonjour les
qui est de type MotComapct
faut que je detremine NbreLigneComun (bonjour , good)
tu vois
nombreLigne commun(Motcompact, motCompact)
et la jai bonjour et de type cahr*
char*
il te faudra aussi bonjour tout seul?
oui
et
Je croyais qu'on avait juste besoin de retrouver "bonjour les" à partir de "bonjour" et "les"... :(
tu vois?
je fait deux parcours de 2 tableau : 2seq et 1mot
Mais j'ai du mal à voir ce qu'il faut exactement
tu as compris ce ke jeux dire ?
Ne faudra-t-il pas de toute façon, à un moment donné, faire un parcours quadratique (en n²) ? je c pas ..
:(
je te passe un exemple
bonjour les good bonjour les morning
jai 2 tableau
un qui conteitn 'bonjour les' et l'autre contient 'good' et 'morning'
là je calcule les 2 regles
bonjour les ->good
&
bonjour les ->morning
tu vois?
putain c'est compliqué ton truc
pk?
pour les regles?
oui
pour le calcul?
Je n'arrive pas à voir comment on peut réduire cela à un simple parcours quadratique
français x anglais
oui
si on doit repartir sur 4 boucles imbriquées, c'est l'enfer
oui ..
:(
d'un autre côté, on peut aussi essayer un truc spécial pour les 2seq
?
comment
plutôt qu'un tableau de pointeurs MotComplet, un pointeur de structure {
MotComplet *p2seq MotComplet *pMotGauche MotComplet *pMotDroit
}
Et on fait plusieurs étapes
1) On remplit la table de hachage avec les 2seq lus dans le fichier
oui
2) On fait un parcours quadratique des mots dans sa langue, et à chaque fois on cherche {mot1, mot2} dans la table de hachage, et on remplit la structure
Comme ça, à partir de 2 mots, on peut retrouver le 2seq*
Et à partir d'un 2seq, on peut retrouver les 2 mots
c possible?
Sans jamais avoir à sortir d'un parcours quadratique (enfin, parcours quadratique + recherche dichotomique hachée, donc un temps entre O(n²) et O(n²*log n)
c'est à dire moin lent?
C'est ça: On essaie de ne jamais avoir 4 boucles imbriquées.
oui
Avec ça, on en aura 2 (ou 2 et demie), maximum
Plus bien sûr, la boucle supplémentaire pour NbLignesCommunes, mais vu qu'on l'aura optimisée...
Donc, il faut procéder en plusieurs étapes.
ok
1° La structure avec les trois pointeurs
2° Le tableau dynamique de structures "trois pointeurs"
3° La table de hachage char const* -> structures "trois pointeurs" (pas besoin de dupliquer la chaîne, vu que les MotCompact ne sont jamais détruits)
4° Trier les tableaux de la table de hachage
5° Optimiser la table de hachage en regroupant tous les tableaux en un seul grand (mais on peut réutiliser la même structure tableauDynamique pour ça)
6° Parcours quadratique des mots d'une langue pour régler les pointeurs dans les structures "trois pointeurs"
6.5 faire la même chose avec l'autre langue
7 On essaie de voir ton algo de calcul des règles, maintenant qu'on a les données accessibles rapidement.
Note bien ça quelque part
Genre en commentaire dans un fichier du second projet lui-même.
13/12/2009, 20h18
étoile de mer

Citation:

je ne suis pas sûr des paramètres de type char*.

Ok, ya un souci avec ce type char*?:calim2:
13/12/2009, 22h46
LittleWhite

Puis je me permettre:
"Je suis de plus en plus perdu"
13/12/2009, 23h22
Médinoc
Résumé pour LittleWhite:
- On a un programme qui lit deux fichiers texte, et compte pour chaque mot et séquence de deux mots, les endroits où il apparait (plus précisément, les lignes où il apparait)
- Ce programme est dérivé d'un ancien programme similaire, qui inscrivait ces données dans des fichiers binaires. On a gardé ce système, car ça permettait de recharger les données sous un nouveau format, bénéficiant d'une meilleure localité mémoire. Notamment, on passe de plusieurs tables de hachage contenant d'innombrables listes chaînées à quelques grands tableaux.
- Récemment, on a partagé le projet en 2, pour mieux séparer les traitements et les types de données:
  - Le "premier" projet lit le fichier texte, travaille avec les listes chaînées et les tables de hachage complexes (il y avait 2 niveaux de hachage pour les séquences de deux mots), puis écrit les fichiers binaires.
  - Le "second" projet lit les fichiers binaires et en fait quatre tableaux de structures MotCompact en mémoire (si je me souviens bien).
- Maintenant, on travaille sur le second projet.
- Problème, le projet reste lent parce qu'il y a des boucles imbriquées dans le traitement. Une des causes est l'absence de possibilité de recherche dans les tableaux de MotCompact.
- C'est pour ça que j'ai eu l'idée d'une nouvelle table de hachage pour les séquences de deux mots: Une table simple cette fois-ci, dont les sous-conteneurs sont des tableaux dynamiques (triés) au lieu des listes chaînées. (il y a une table de séquences de deux mots par langue)
- Ce conteneur ne contiendra pas directement les structures MotCompact, mais des structures ici appelées Dsequence, qui contiennent des pointeurs.
- Le projet donne plusieurs avantages pour la table de hachage et les tableaux: La table est remplie en une fois et ne change plus jamais ensuite, et chaque fichier binaire ne contient pas de doublons.
- Donc, j'ai décidé que le plus économique pour remplir la table serait d'ajouter simplement chaque élément à la fin du tableau dynamique correspondant (étapes 1 à 3 sur ma liste), sans se préoccuper du tri (ça marchera parce qu'il n'y a pas de doublon).
- Ensuite, pour pouvoir faire une recherche dichotomique sur les tableaux, on les trie tous. (étape 4)
- Et si on n'a pas encore assez de localité mémoire, (ou si on bouffe trop de mémoire, tout simplement) on peut aussi remplacer tous ces tableaux par un seul grand. Cela réduira la place utilisée par les tableaux, vu que cette fois-ci, la taille mémoire réservée sera égale au nombre d'éléments vraiment contenus dans le tableau (ce n'est pas le cas avant, car on agrandit les tableaux par bloc, histoire de ne pas faire un realloc() à chaque ajout) (étape 5).
- Chaque structure Dsequence ne contient pas seulement un pointeur vers la structure MotCompact correspondant à la séquence de deux mots hachée: Elle contient en plus un pointeur vers la structure MotCompact du premier mot de la séquence, et la même chose pour le second.
- L'étape 6 consiste à remplir ces deux pointeurs, en parcourant les tableaux de structures MotCompact pour les mots individuels d'une langue donnée. Cela nécessite tout ce qu'on a fait avant, puisque l'algorithme donne à peu près ça:
  - POUR chaque MotCompact X du tableau pour les mots seuls
  - POUR chaque MotCompact Y du tableau pour les mots seuls
  - Rechercher la structure Dsequence pour (X, Y) dans la table de hachage
  - Régler ses pointeurs.
- Ensuite, on refait la même chose pour l'autre langue.
- Avec ça, on devrait avoir tout ce qu'il faut pour l'algo de calcul des règles, vu qu'à partir de "X Y" on peut rapidement retrouver le MotCompact de (X, Y) ainsi que celui de X et celui de Y.

état d'avancement:

état d'avancement:
1-création de la structure du tableau dynamique :

Code:

1
2
3
4
5
6
struct tableauDynamique_struct
{
	int *tab;
	size_t taille;
	size_t capacite;
};

2- la structure Bisequence :

Code:

1
2
3
4
5
6
struct  BiSequence
{
    MotCompact  *seq;
    MotCompact  *MotGauche;
    MotCompact  *MotDroit;
};

3- Creation d'un tableau dynamique :

Code:

1
2
3
4
5
6
7
//constructeur pour TableauDynamique_struct
void TableauDynamique_struct_ctor(struct tableauDynamique_struct *pThis)
{
	pThis->tab = NULL;
	pThis->taille = 0;
	pThis->capacite = 0;
}

Code:

1
2
3
4
5
6
7
8
//destructeur
void TableauDynamique_struct_dtor(struct tableauDynamique_struct *pThis)
{
	free(pThis->tab);
	pThis->tab = NULL;
	pThis->taille = 0;
	pThis->capacite = 0;
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int TableauDynamique_struct_ajouter(struct TableauDynamique_struct *pThis, struct BiSequence const* pcNouveau)
{
	assert(pThis->taille <= pThis->capacite);
 
	/* Agrandir le tableau si besoin est. */
	if(pThis->taille == pThis->capacite)
	{
		size_t nouvelleCapacite = (pThis->capacite < 4 ? 4 : (size_t)(pThis->capacite*1.5));
		if(realloc_struct(&pThis->tab, nouvelleCapacite) >= 0)
		{
			pThis->capacite = nouvelleCapacite;
		}
		else
			return -1;
 
	}
 
pThis->tab[pThis->taille++] = *pcNouveau;
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define DECLARE_REALLOC(name, type) \
	int realloc_ ## name (type **ppMem, size_t nNew);
 #define IMPLEMENT_REALLOC(name, type) \
	int realloc_ ## name (type **ppMem, size_t nNew)\
	{\
		int ret = -1;\
		type * pNew = realloc(*ppMem, nNew * sizeof(**ppMem));\
		if(pNew != NULL || nNew==0)\
		{\
			*ppMem = pNew;\
			ret = 0;\
		}\
		return ret;\
	}
IMPLEMENT_REALLOC(struct, struct BiSequence)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//création de la table de hachage
typedef tableauDynamique_struct tableHachage_struct[TAILLEHASH];
 
 
tableHachage_struct * CreerSimpleTableHachage()
{
	tableHachage_struct * THash = allocExit( sizeof * THash);
	size_t i;
	for(i=0;i<TAILLEHASH; i++)
	{
	TableauDynamique_struct_ctor(&THash[i]);
	}
	return THash;
}

Code:

1
2
3
4
5
6
7
8
9
10
 
// fonction de hachage 
unsigned int Hash_string (char * m1, char * m2)
{
unsigned int val1, val2, val;
val1=Hash_chaine(m1);
val2=Hash_chaine(m2);
val=val1+val2;
return val% TAILLEHASH;
}

Code:

1
2
3
4
5
6
7
8
9
10
/* Hache une chaîne de caractères. */
unsigned int hash_chaine(const char * chn)
{
	unsigned int val = 0;
	for (; *chn != '\0'; ++chn)
	{
		val = *chn + 31 * val;
	}
	return val % TAILLEHASH;
}

Code:

1
2
//Ajout à la table de hachage:
 TableauDynamique_struct_ajouter( &table[clé], newValue );

15/12/2009, 19h22
Médinoc

Tu n'as pas besoin de Hash_string (et qu'est-ce que c'est que ce nom?) dans le code actuel.

Ok,'on n'a pas besoin d'une fonction qui hache DEUX chaînes et additionne leurs valeurs de hachage
Code:

1 2 3 4 5 6 7 8 9 10 /* Hache une chaîne de caractères. */ unsigned int hash_chaine(const char * chn) { unsigned int val = 0; for (; *chn != '\0'; ++chn) { val = *chn + 31 * val; } return val % TAILLEHASH; }
Code:

1 2 //Ajout à la table de hachage: TableauDynamique_struct_ajouter( &table[clé], newValue );
Code:

int TableHachage_BiSequence_ajouter(struct TableHachage_BiSequence *pThis, MotCompact* pNouveau)

|erreur: incompatible types in assignment

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int TableauDynamique_struct_ajouter(struct TableauDynamique_struct *pThis, struct BiSequence const* pcNouveau) { assert(pThis->taille <= pThis->capacite); /* Agrandir le tableau si besoin est. */ if(pThis->taille == pThis->capacite) { size_t nouvelleCapacite = (pThis->capacite < 4 ? 4 : (size_t)(pThis->capacite*1.5)); if(realloc_struct(&pThis->tab, nouvelleCapacite) >= 0) { pThis->capacite = nouvelleCapacite; } else return -1; } pThis->tab[pThis->taille++] = *pcNouveau; }
Au niveau de la derniere instruction j'ai une erreur de type
|erreur: incompatible types in assignment

et là :

Code:

if(realloc_struct(&pThis->tab, nouvelleCapacite) >= 0)

attention : passing argument 1 of ‘realloc_struct’ from incompatible pointer type|

Une idée svp?
merci

15/12/2009, 20h50
Pouet_forever

A ce que j'ai compris pThis->tab[] est de type int et *pcNouveau est de type MotCompact* (pointeur sur le premier type de ta structure)
Je pense que ton souci se situe à ce niveau là :)

Pour ta fonction realloc_struct il faudrait le prototype pour pouvoir t'aider :)
15/12/2009, 21h13
étoile de mer
oui, je vois l'erreur : le tableau c'est pas un tableau d'entier mais un tableau de structure, donc je pense qu'il doit etre comme ca ::roll: (je ne suis pas sûre)
Code:

1 2 3 4 5 6 struct TableauDynamique_struct { struct TableauDynamique_struct *tab; size_t taille; size_t capacite; };
15/12/2009, 21h18
Pouet_forever

Ca ne change pas le problème, pcNouveau est de type 'struct BiSequence const*' et non 'struct TableauDynamique_struct *' ;)

C/C : Pour ta fonction realloc_struct il faudrait le prototype pour pouvoir t'aider :)
15/12/2009, 21h25
étoile de mer

ca va avec ces 2 erreurs , mais il ya 2 autres:
//création de la table de hachage

Code:

typedef tableauDynamique_struct tableHachage_struct[TAILLEHASH];

|erreur: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘tableHachage_struct’|

Voir 40 message(s) de cette discussion en une page