Sujet Précédent Sujet Suivant

Problème de taille pour rech. dichotomique C

Fermé
dodie - 23 juil. 2003 à 11:23
 dodie - 18 août 2003 à 07:44
Bonjour, j'ai une petit problème pour ma recherche dichotomique en C.
Je dois effectuer une recherche dichotomique dans un dictionnaire stocké dans un fichier texte. On m'a conseillé de passer mon fichier en tableau, donc si je ne me trompe pas en mémoire vive.
La dessus j'y suis arrivée, seulement j'ai un autre problème...
Je ne peut pas traiter plus de 140 000 mots et mon dictionnaire en contient presque 380 000. Le problème vient peut etre du fait que j'ai utilisé un tableau à deux dimentions... MAis je ne sais pas comment faire autrement.

J'avais également pensé à utiliser plusieurs tableaux pour partitionner mon dictionnaire, mais ici encore, j'ai une erreur à l'execution, et je suis presuqe certaine que c'est du à la taille de mes tableaux. Donc il est posible que ce soit un problème du au fait que je n'ai pas assez de mémoire sur mon ordi (mais je ne sais même pas combien de mémoire vive j'ai sur l'ordi et je ne sais pas comment le vérifier )

Si vous avez une idée a me soumettre pur régler mon problème ou une autre solution pour me permettre d'effectuer une recherche dichotomique sur un fichier texte, je vous en serai reconnaissante.

Je vous envoie le code de mon programme en espérant qu'il soit clair. 

#include<stdio.h>

#define MAX 140000 

#define MAX_LEN 14





 verification_mot(char mot[15]){

FILE* fic = fopen("dico.txt", "rt"); // "rt" pour dire READ TEXT 



if (fic!=NULL) { 

   int trouve,mot_trouve,i=0,j,y=0;

   char tableau[140000][MAX_LEN]; avec plus de 140000

//le programme ne marche pas

 //  char tableau2[140000][MAX_LEN];  ne fonctionnent pas

 //  char tableau3[140000][MAX_LEN];

   char ligne1[15];

  

    while (!feof(fic) && y<140000) 

   {

        j=0;

        fscanf(fic, "%s", ligne1); 

         y++;

   

         while(ligne1[j]!='\0') 

        {

             tableau[i][j]=ligne1[j];

             j++;

             if (ligne1[j]=='\0') tableau[i][j]='\0';

          }

       i++;

       if (y==140000) printf("%s\n",tableau[y-1]);

//pour connaitre le dernier mot traité

    }

    

    

   fclose(fic);   

}



main(){

verification_mot("coucou");

system("PAUSE");

      return 0;}



La verification du mot n'a pas ncore été traitée, pour lemoment je cherche juste à régler mon problème de tableau...
Si vous pouvez m'aider, merci d'avance.
A voir également:

10 réponses

Réponse 1 / 10
Nico
23 juil. 2003 à 11:34
salut

il est clair que la taille de ton tab est conséquente : 140000 * 14 ce qui fait deja 1 960 000 que tu multiplis par 256 car tab de caractere ce qui fait 501 760 000 octets - pas mal.

j'ai pris ton code pour le tester, je te recontacterais

A@++
0
Réponse 2 / 10
Nico
23 juil. 2003 à 11:35
a oui autre chose,

ta fonction verification_mot n'est pas défini, il faut que tu indiques son type ici void
0
Réponse 3 / 10
Lord Woden Messages postés 89 Date d'inscription vendredi 3 janvier 2003 Statut Membre Dernière intervention 19 janvier 2006 21
24 juil. 2003 à 13:37
Salut,

pour ma part, il y a surtout un élément que je ne comprend pas dans ton programme. L'intérêt de la recherche dichotomique est de limiter les accès aux données pour effectuer une recherche. Or de toute facon tu effectue systématiquement une lecture complète de tes TOUTES tes données avec en plus une fonction (fscan) qui est gourmande en temps CPU.

Bref, tu implémente un algorithme d'une facon contraire à son optique de performance.

Si je peux me permettre voikla une petite suggestion.
Ton problème c'est d'améliorer le temps de recherche.
A contrario, l'espace mémoire sur un disque dur n'est pas un problème (les disques font plusieurs Go maintenant !). Donc gaspille un peu d'espace pour gagner du temps.

En clair, défini une structure de données de taille FIXE pour conserver les mots de ton dictionnaire. Ainsi, tu as une relation directe entre la taille du fichier et le nombre de mots, et surtout dans une recherche dicoto tu as un moyen directe d'incrémentation d'un pointeur de recherche dans ton fichier pour analyser uniquement dans ta boucle de traitement, le mot de test de la recherche dicoto !

Dit moi ce que tu en penses, mais pour moi c'est une méthode qui me paraît pas si pire ;o)
0
dodie
24 juil. 2003 à 16:40
je comprends ce que tu veux dire a propos de la recherche dichotomique et de son utilité, par contre je ne comprends pas ce que tu me suggère pour faire autrement (désolée je ne suis pas très douée en C). Tu me dis de créer une structure de données de taille FIXE, mais ce n'estpas ce qu'est le tableau?
Je ne comprends pas non plus ce que tu me dis à propos d'un moyen direct d'implementation d'un pointeur de recherche dans mon fichier pour analyser uniquement le mot
est ce que ce que tu entends c'est une structure de donnée du type:

typedef struct{
int taille;
int contenu[taille des mots];
} structure

????
Parce que dans ce cas en fait je vois pas trop la différence avec un tableau, mais comme je te l'ai dit, je ne suis pas très douée!!!
Sinon, s'il te plait explique moi, ta solution m'intéresse, mais je ne suis pas encore capable de la mettre en oeuvre...
0
Lord Woden Messages postés 89 Date d'inscription vendredi 3 janvier 2003 Statut Membre Dernière intervention 19 janvier 2006 21 > dodie
25 juil. 2003 à 10:12
Salut,

en fait, la "structure" dont je te parles est une facon de dire que les données de ton dictionnaire sont structurées. Concrètement, il te suffit de produire un petit progz qui te lise donc dictionnaire actuel et qui réécrive en sortie dans un autre fichier mais pour chaque mot la longueur de la chaîne est de MAX_LEN.

Exemple :

Lecture dans le dico actuel :
"Bonjour\n" (Longueur = 8*sizeof(char))
"Dichotomique\n" (Longueur = 13*sizeof(char))

Ecriture dans le nouveau dico:
"Bonjour \n" (Longueur = MAX_LEN*sizeof(char))
"Dichotomique \n" (Longueur = MAX_LEN*sizeof(char))

Ainsi quelque soit le mot, la chaîne de caractère qui contient un mot dans ton fichier dico fait un longueur donnée. Ainsi, lorsque ton obtient un pointeur en lecture sur ton fichier tu obtient en fait un pointeur sur le premier caractère de ton dico. Or, comme tu as avec ton nouveau dico, une longueur constante pour tes chaînes de caractères contenant les mots, tu peut incrémenter ton pointeur de lecture pour qu'il pointe sur le début du mot suivant ou n mot plus loin. Pour cela tu incrémente ton pointeur de la valeur :
n*(MAX_LEN*sizeof(char))
ou n correspond au nombre de mot dont tu veux avancer dans ton dico. Ce nombre te sert notamment comme valeur de recherche pour la dicotomie. En effet, avec ce truc tu sais que le nombre de caractères du dico est égale à la taille du dico diviser par sizeof(char). Ensuite, tes mots font toujours MAX_LEN donc tu as ensuite le nombre de mot N.
A partir de ce nombre de mot N, tu effectue ta dicotomie.

C'était plus claire cette fois ? ;)

@+ Lord Woden ;o)
0
dodie > Lord Woden Messages postés 89 Date d'inscription vendredi 3 janvier 2003 Statut Membre Dernière intervention 19 janvier 2006
25 juil. 2003 à 10:40
Oui, merci cette fois ci j'ai compris. J'ai seulement une question en fait. Est ce que pour rechercher le nième mot de mon fichier, je dois faire un parcours de ce fichier pour y arriver?
@+ dodie
0
batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114 > dodie
25 juil. 2003 à 11:05
Oui, il faudrait que tu comptes les sauts de lignes... Peut-être avec quelques finesses pour ne pas prendre en compte les lignes vides ou les trucs de ce genre.

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
0
Lord Woden Messages postés 89 Date d'inscription vendredi 3 janvier 2003 Statut Membre Dernière intervention 19 janvier 2006 21 > dodie
25 juil. 2003 à 11:40
Salut,

Et bien précisemment NON. C'est tout l'intérêt de la méthode tu ne parcours pas le fichier et tu ne lis que les données qui te permet de faire ton choix de progression de dichotomie.

Pour la recherche dichotomique, à partir des valeurs que je t'ai indiqué et que tu calcules et mets à jour à mesure que tu progresse dans ta recherche, tu met à jour la valeur du pointeur de recherche (simple affectation de variable) après tu analyses le mot dont ton pointeur pointe sur la première lettre et selon l'analyse de ton mot par rapport au mot recherche, tu met à jour la valeur de ton pointeur pour analyser le mot suivant. Enfin la je vais pas te réexpliquer la recherche dichotomique.

@+ Lord Woden ;o)
0
Réponse 4 / 10
mirza
24 juil. 2003 à 13:42
lut Dodie tu dois untiliser un tableau a 2 dimensions MAIS de dimensions NON constantes
En effet tous les mots ne font pas MAX_LEN caractères (certains en font moins)

ok ?
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 10
dodie
24 juil. 2003 à 16:45
j'avais pensé à faire ça mais je ne vois pas comment faire!!!
0
Réponse 6 / 10
batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
25 juil. 2003 à 09:50
Pourquoi tu limites à 140 000 en fait ?!?

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
0
dodie
25 juil. 2003 à 10:35
Je ne peut pas faire plus en fait, au dela de 140 000 mots, mon programme plante. je pense que c'est un problème de mémoire vive...
0
Réponse 7 / 10
batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
25 juil. 2003 à 11:28
Si ton programme plante, c'est que tu as fait une erreur dans ton code... Il n'y aucune raison qu'il plante autre que celle-ci...

Il ne faut pas utiliser fscanf, mais fgets qui est beaucoup plus simple pour ce genre de chose.

Je te donne le code le plus évident pour ce genre de problème : 

FILE *f;

char *tab[];

char buf[BUFSIZ]; //constante définie dans stdio.h

//je te laisse t'occuper de l'ouverture en lecture du fichier,

//du positionnement au début

//(et de la vérif qu'il est bien ouvert, bien sûr)



bon attends, je le fais, je le teste et je te donne le code



@++



Vous hésitez entre Linux et Windows ?

Vous voulez dépenser du temps ou de l'argent ?
0
dodie
25 juil. 2003 à 13:05
j'attend ta réponse avec impatience !!! :-) en attendant je vais essayer de tester l'autre solution qu'on m'a proposé... je vais aussi essayer de voir ce que tu m'as proposé pour voir si toute seule je serais capable de faire ce programme...

@+ dodie
0
Réponse 8 / 10
batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
25 juil. 2003 à 13:04


Alors voilà : 

#include <stdio.h>

#include <string.h>

#include <stdlib.h>



int main(void)

{

	char **tab =NULL;

	char buf[BUFSIZ];

	unsigned int nb_mots = 0;

	unsigned int i ;

	FILE *f = NULL;



	if( (f=fopen("pof.txt", "rt")) == NULL )

	{

		fprintf(stderr, "impossible d'ouvrir pof\n");

		return 1;

	}



	fseek(f,0,SEEK_SET);



	while(fgets(buf, BUFSIZ, f) != NULL)

	{

		if ( buf[ strlen(buf) - 1 ] == '\n')

		{

			buf[ strlen(buf) - 1] = '\0';

		}

		if (strlen(buf) == 0)

		{

			continue;

		}



		tab = (char**) realloc(tab,sizeof(char*) * (nb_mots + 1));

		tab[nb_mots] = (char*) malloc( sizeof(char)* (strlen(buf)+1) );

		if(tab[nb_mots] == NULL)

		{

			fprintf(stderr, "alloc ratée\n");

			return 2;

		}

		

//		fprintf(stderr,"AVANT : nb_mots=<%u> tab=<%s> buf=<%s>\n", nb_mots,tab[nb_mots], buf);



		strcpy( tab[nb_mots], buf);

		

//		fprintf(stderr,"APRES : nb_mots=<%u> tab=<%s> buf=<%s>\n", nb_mots,tab[nb_mots], buf);

		

		++nb_mots;

	}

//juste pour vérifier que c'est ok, tu devras bien sûr enlever cette partie

	printf("Fin de récupération des %u mots\n\n", nb_mots);

	printf("mots trouvés dans le fichier :\n");

	

	for(i=0;i<nb_mots;++i)

	{

		printf("mot %u : <%s>\n", i, tab[i]);

	}

	return 0;

}


0) ce code fonctionne, je viens de le vérifier
1) Actuellement ce prog cherche le fichier pof.txt => reste à faire le nécessaire pour lire le fichier que tu veux...
2) Il ne prend pas les mots vides
3) Je n'ai volontairement pas commenté le code pour ne pas le surcharger, s'il y a quelque chose que tu ne comprends pas, n'hésite pas à poser une question.

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
0
dodie
25 juil. 2003 à 13:07
merci, je le teste tout de suite!
0
Réponse 9 / 10
dodie
25 juil. 2003 à 13:34
super, ça fonctionne même sur mon ordi . Je m'étais donc trompée dans mon code, c'était pas la mémoire . Je te remercie pour le programme. J'ai compris comment il fonctionne mais si tu peux juste m'expliquer ce à quoi correspond 
char buf[BUFSIZ];

car je n'ai jamais vu BUFSIZ... merci encore
@+ tard
Dodie
0
batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
25 juil. 2003 à 13:52
Je l'ai indiqué dans le code, c'est une constante à utiliser quand tu crées des buffers statiques comme ici la variable buf.

Je crois qu'elle vaut la taille du buffer d'entrée du système.
Comme indiqué, elle est définie dans stdio.h

Il y a donc quand même un défaut à ce programme : si un mot est plus long que BUFSIZ caractères, ça va déconner...

Mais pour te rassurer, ya qd même assez peu de chances que tu aies un mot qui dépasse 1024 caractères (la valeur de BUFSIZ définie chez moi)

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
0
dodie > batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008
14 août 2003 à 15:40
Désolée de te déranger encore surtout si longtemps après...
mais je pensais avoir tout compris dans le programme que tu m'as écrit et en fais je ne comprends pas l'utilisation du pointeur double...
char **tab
Pourais tu me l'expliquer s'il te plait car je n'ai pas vu ça en cours...?
merci d'avance!!!
0
IDNoires > dodie
14 août 2003 à 15:43
char **tab = char tab[][]
c'est un tableau a 2 dimensions si je me souviens bien de mes cours de C...
0
Réponse 10 / 10
dodie
18 août 2003 à 07:44
merci!
0

Discussions similaires

Ecran iphone qui est trop grand
patorp -
Proulx -

144 réponses
Curseur plus large que 32x32
Zv -
Zv -

2 réponses
Commande internet correspondance taille US pour jean homme.
Larkos -
Zabou -

5 réponses
unité de taille pour un fichier audio au format MP3
wesh69 -
jeannets -

2 réponses
Remettre l'écran en taille normale
Floriane -
Cindy64000 -

24 réponses