Discussion :

[barbare128]

Salut tout le monde,

Il y a un moment que je n'ai pas posté sur ce forum,
ça fait plaisir de voir qu'il y a toujours pas mal de monde prêt
à vous aider



Je suis en train de faire un programme ( sous visual c++ )
qui lis dans un fichier, répertorie les mots trouvés dans une liste chainée triée, et les comptes.

Bref le programme fonctionne très bien sauf pour les gros fichier,
ce qui me pose problème.

La liste chainée est récursive. Mon fichier est un dictionnaire des mots
français. Pour le moment vous me direz pas d'intérêt. ( environ 6Mo,
mais ce n'est pas la quantité de mémoire qui le freine. ).

Ensuite de comparer deux liste chainées, mais bon je pense vous
avez compris, c'est pour faire de la correction d'orthographe.

C'est le stack overflow, après quelques petites recherche, je pense
que c'est le call stack overflow qui lui pose un soucis. Donc si je vire
monde code récursif pour un code linéaire à boucle cela devrais tourner.

j'aimerais passer outre la limitation ( et conserver la récursion ),
ou une autre astuce pour pas trop modifier le code.
( c'est pas un code spécialement long mais bon ... le but est de faire
de <<l'art>> plutôt que code pour du code. ).

Et justement au passage j'ai souvent du code récursif, à dimension limité,
et parfois à dimension inconnue, d'où justement pouvoir récupérer la valeur pour éviter le crash.

Au passage, je cherche quelques exemples de code de tri sur une liste
chainée que l'on passe en arbre pour faire le tri, le cas ou ma liste est pas
triée, j'aimerais faire du code en n(log(n)) plutôt que du n*(n+1)/2.

le proto de ma structure, et de ma fonction d'ajout triée.

Et au passage, le code dois rester sur du C, bien que je travaille
sous visual c++, c'est de << l'entrainement>> pour faire du C embarqué.

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
struct liste{
	char mot[32];
	int nbreocc;
	struct liste *suivant;
};
 
typedef liste *pt;
 
void ajout(char mot[32],pt *L)
{
	if(*L==NULL)
	{
		*L = (pt)malloc(sizeof(liste));
		strcpy((*L)->mot,mot);
		(*L)->suivant=NULL;
		(*L)->nbreocc = 1;
		return;
	}
	if( strcmp((*L)->mot,mot)>0 ) 
	{
		pt peaux;
		peaux=(pt)malloc(sizeof(liste));
	        peaux->suivant= *L;
		*L=peaux;
		strcpy((*L)->mot,mot);
		(*L)->nbreocc = 1;
		return;
	}
	else ajout(mot,&((*L)->suivant));
}

merci d'avance

[anacharsis]

salut !
si tu veux faire de la correction orthographique, ce n'est pas d'un dico dont tu as besoin, mais d'un lexique des flexions. j'ai personnellement utilisé

Lexique des formes fléchies du français - Dicollecte v4.3

qui pèse 38 Mo, 538985 flexions, mais qui contient des renseignements assez utiles (comme le compte des emplois sur google, wikipedia, littérature et la fréquence).
la recherche dans une liste chaînée est très lente par rapport à une recherche dichotomique (bsearch dans stdlib qui t'oblige à considérer la longueur d'un mot comme point le plus pertinent dans ta recherche).
le tri d'une liste chaînée (celle du lexique) ne présente aucun intérêt dans un système embarqué : le tri doit avoir été fait avant l'embarquement. pour ce qui est de la liste des mots dont on veut vérifier l'orthographe, pourquoi pas, mais je ne vois pas.

A+

[barbare128]

salut !
si tu veux faire de la correction orthographique, ce n'est pas d'un dico dont tu as besoin, mais d'un lexique des flexions. j'ai personnellement utilisé

Lexique des formes fléchies du français - Dicollecte v4.3

qui pèse 38 Mo, 538985 flexions, mais qui contient des renseignements assez utiles (comme le compte des emplois sur google, wikipedia, littérature et la fréquence).
la recherche dans une liste chaînée est très lente par rapport à une recherche dichotomique (bsearch dans stdlib qui t'oblige à considérer la longueur d'un mot comme point le plus pertinent dans ta recherche).
le tri d'une liste chaînée (celle du lexique) ne présente aucun intérêt dans un système embarqué : le tri doit avoir été fait avant l'embarquement. pour ce qui est de la liste des mots dont on veut vérifier l'orthographe, pourquoi pas, mais je ne vois pas.

A+

C'est un TP d'informatique, disons que j'ai poussé un peu car j'ai des exams d'ici quelques jours qui demandent à savoir faire la comparaison de deux listes chainées et du tri d'arbre binaire. ( et bien sur on l'a pas fait en cour )

Et le but c'est faire de l'embarqué, l'an prochain, donc je suis limité au langage c, pas droit au c++ .

Oui je m'amuse pas à faire de la correction orthographique sur de l'embarqué

C'est juste de l'entrainement quoi, j'aimerais comprendre pourquoi ça plante,
et comment corriger

[exe2bin]

Je pense que la science algorithmique a déjà tout trouvé alors vas plutôt voir sur des sites comme celui ci :

http://www.greyc.ensicaen.fr/ensicae...ne/AlgoTri.pdf

[anacharsis]

presque tout ! il y a encore 1 M$ à prendre à la Cray fundation ...

A+

[barbare128]

quand mon programme plante, il me mets la flèche sur la sortie de ça ( malloc.c )

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
__forceinline void * __cdecl _heap_alloc (size_t size)
 
{
 
    if (_crtheap == 0) {
        _FF_MSGBANNER();    /* write run-time error banner */
        _NMSG_WRITE(_RT_CRT_NOTINIT);  /* write message */
        __crtExitProcess(255);  /* normally _exit(255) */
    }
 
    return HeapAlloc(_crtheap, 0, size ? size : 1);
}

Sachant que ça marche très bien avec d'autre fichiers, je vois pas trop le problème ...

[anacharsis]

j'ai regardé ton code de près, il n'y a rien de faux dans ce que j'ai lu si ce n'est un typedef avant struct liste, je pense que ton problème est dans la partie de ton code que je n'ai pas lue : une initialisation oubliée comme

Code :

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

pt L = NULL...

A+

[baccali]

Salut,

Tu m'étonnes que tu aies un call stack overflow! Du code pour du code comme tu dis à juste titre, c'est pas le top! Mais sans vouloir te vexer c'est quand même là exactement ce que tu fais là!

Ici un algorithme récursif est la pire des choses à faire! Je te donne un exemple où ton algo de tri récursif pourrait être utile, basé sur l'algorithme "diviser pour régner".

Tu as une chaine de charactère que tu dois mettre en ordre. Tu divises la chaine en 2 et tu lances ta fonction sur chaque moitié.

Sauf que toi tu lances un appel de fonction et tout ce que ça implique, sur une base UNAIRE, ce qui veut dire que si ton fichier contient 20000000 de mots, tu lances ta fonction 20000000 de fois. Hors chaque appel de fonction consomme en mémoire. La liste d'argument passé, la place pour la valeur de retour (même si ici apparemement elle ne retourne rien mais c'est pour te dire) etc... sont placé sur la stack.

Donc en gros si ton fichier contient 20000 mots, tu bloques au minimum 20000 mots sur la stack (et ce quelque soit la convention d'appel de fonction, __stdcall, __cdecl etc...). C'est pour cela que ton programme plante avec les gros fichiers seulement.

Bref, tu l'auras compris, ici du code récursif est probablement la pire des choses à faire, niveau performances comme niveau conso en mémoire.

Penses plutôt à une fonction comme les gestionnaires de processus de Linux (Windows aussi de ce que j'ai entendu mais ces fonctions ne sont pas documentées) ou autres qui traitent ce genre de liste chainée par un algo linéaire.

Cordialement.

[barbare128]

merci baccali, je m'en doutais, mais je n'en étais pas sur.

Au passage, comment je peux gérer les caractères accentués ?

[Kirilenko]

Pour gérer les caractères accentués sous Windows, tu peux utiliser le type wchar_t (C99) ou tu utilises la norme C11 qui prend en charge l'Unicode. Après, si c'est dans une optique d'embarqué, je ne sais pas...

[anacharsis]

Au passage, comment je peux gérer les caractères accentués ?

ne telance pas là-dedans si tu n'a pas une idée précise de ce que tu veux faire : souhaites-tu une proximité entre cote, côté, COTE, CÔTÉ. ça complique un peu les choses ... tu peux utiliser des caractères accenté puisqu'ils ont un code, mais on est bien loin du petit problème de liste chaînée. supprimer les appels récursifs terminaux figure dans pas mal de publications depuis longtemps et la recherche d'un mot dans une liste chaînée reste toujours très consommatrice de temps. faut passer aux arbres !

j'ai des exams d'ici quelques jours qui demandent à savoir faire la comparaison de deux listes chainées et du tri d'arbre binaire.

reviens à ce qui est urgent !

A+