Discussion :

[LittleWhite]

Bonjour à tous,

Tout d'abord, le contexte.

J'ai des Mot ( une structure ) qui contient entre autre une chaine de caractère, son nombre d'occurances ( tiens, je ne sais toujours pas écrire ce mot ), et un tableau dynamique qui contient les lignes ou apparait ce mot dans un fichier texte.

Code :

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

1
2
3
4
5
6
7
 
typedef struct Mot
{
	char* mot;	// Garde le mot
	unsigned int nbOccurances; // Nombre d'occurance dans le fichier
	IList lignes; // La liste des lignes ou il apparait.
}Mot;

( Note: Un tableau dynamique est juste une structure qui à une taille, un pointeur, une capacité ( on ne peut pas faire beaucoup plus simple ) )

Maintenant, j'ai deux Mot. Je veux calculer le nombre de ligne commune, entre deux Mot.
J'utilise cette fonction:

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
 
/**
 * Nous avons un avantage pour ces deux fonctions
 * Le liste des lignes sera trié ( car nous lisons un fichier de haut en bas :D )
 * Ce qui fera que la recherche des lignes communes sera facilité ( en terme de calcul )
 */	
unsigned int nbCommunes(const Mot* const mot1, const Mot* const mot2)
{
	// Récupération des tailles des tableaux
	unsigned int limiteMot1 = mot1->lignes.taille;	
	unsigned int limiteMot2 = mot2->lignes.taille;	
 
	unsigned int compteur1 = 0;
	unsigned int compteur2 = 0;
 
	unsigned lignesCommunes = 0;
 
	while ( compteur1 < limiteMot1 || compteur2 < limiteMot2 )
	{
		if ( mot1->lignes.tableau[compteur1] == mot2->lignes.tableau[compteur2] )
		{
			lignesCommunes++;
			// On peut passer à la ligne suivante
			compteur1++;
			compteur2++;
 
			// Si on matche le dernier mot ... on a pas besoin de continuer ( principe d'unicité des elements )
			if ( compteur1 >= limiteMot1 )
			{
				break;
			}
			if ( compteur2 >= limiteMot2 )
			{
				break;
			}
		}
		else if ( mot1->lignes.tableau[compteur1] < mot2->lignes.tableau[compteur2] )
		{
			if ( compteur1 < limiteMot1 - 1 ) // -1 pour pouvoir continuer à utiliser l'élément courant
			{
				compteur1++;
			}
			else
			{
				// Fin de la recherche
				break;
			}
		}
		else // Soit mot1.lignes.tableau[compteur1] > mot2.lignes.tableau[compteur2]
		{
			if ( compteur2 < limiteMot2 - 1 )	// -1 pour pouvoir continuer à utiliser l'élément
			{
				compteur2++;
			}
			else
			{
				// Fin de la recherche
				break;
			}
		}		
	}
 
#ifdef _DEBUG
	printf("(%s,%s) ont %u lignes communes\n",mot1.mot, mot2.mot, lignesCommunes);
#endif
 
	return lignesCommunes;
}

Cette fonction fonctionne ( wouhou ). Aucun bug dedans.
Par contre, elle est super trop trop trop lente. ( Je fais facilement des millions d'appel dessus, et c'est celle qui prend le plus de temps ( c'est vérifié ) ).
Je ne suis pas le meilleur en terme d'optimisation, ainsi donc, je demande votre aide.

Que peut on faire pour optimiser?

( Sachez aussi que j'ai une fonction comparable, pour faire la même chose avec trois Mot différent. ) Bien sur, la fonction va utilisé une liste ( tableau dynamique ) pour stocker les resultats, puis refaire la comparaison avec le troisième mot. ( Vive la perte de temps ).

Je vous remercie d'avance pour toute remarque et aide à l'amélioration de ce code.

LittleWhite

[Graffito]

Mis à part des améliorations de détail du codage, je vois rien d'évident.

Toutefois, On pourrait essayer d'optimiser ainsi :
Lorsqu'on incrémente un seul des indices (disons compteur1++, mais on traitera compteur2++ de façon analogue), on insére l'instruction suivante :

Code :

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

1
2
3
While (Compteur1+N<Limite1 && 
           mot1->lignes.tableau[compteur1+N] < mot2->lignes.tableau[compteur2]) 
       Compteur1=Compteur1+N ;

Faire quelques essais pour trouver la bonne valeur de N (>10 pour un gain significatif ? en dessous de 5 , on gagnera pas grand-chose).
Même Code amélioré:

Code :

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

1
2
3
4
5
6
7
Limite1MoinsN=Limite1-N ;
tableau1Decale= ... // caster tableauDecale sur Mot1->lignes.tableau de façon
                    //  à ce que tableauDecale[i+N]= Mot1->lignes.tableau[i]
...
While (Compteur1<Limite1MoinsN && 
           tableau1Decale[compteur1] < mot2->lignes.tableau[compteur2]) 
       Compteur1+=N ;

[LittleWhite]

Mis à part des améliorations de détail du codage, je vois rien d'évident.

Toutefois, On pourrait essayer d'optimiser ainsi :
Lorsqu'on incrémente un seul des indices (disons compteur1++, mais on traitera compteur2++ de façon analogue), on insére l'instruction suivante :

Code :

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

1
2
3
While (Compteur1+N<Limite1 && 
           mot1->lignes.tableau[compteur1+N] < mot2->lignes.tableau[compteur2]) 
       Compteur1=Compteur1+N ;

Faire quelques essais pour trouver la bonne valeur de N (>10 pour un gain significatif ? en dessous de 5 , on gagnera pas grand-chose).
Même Code amélioré:

Code :

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

1
2
3
4
5
6
7
Limite1MoinsN=Limite1-N ;
tableau1Decale= ... // caster tableauDecale sur Mot1->lignes.tableau de façon
                    //  à ce que tableauDecale[i+N]= Mot1->lignes.tableau[i]
...
While (Compteur1<Limite1MoinsN && 
           tableau1Decale[compteur1] < mot2->lignes.tableau[compteur2]) 
       Compteur1+=N ;

Je suis bien désolé, mais je n'ai pas compris cette histoire d'indice N.
Pouvez vous expliquer, de façon très très claire.
Pour moi il semble que vous loupez des valeurs avec cette histoire de N...

[Ubiquité]

Je penses pas que ca améliore grand chose mais je crois que tu peux déjà supprimer le teste du while vu que tu mets des breaks partout.

Sinon une autre solution algorithmique pourrait être de concaténer les deux listes, les trier (elles contiennent bien des int indice de la place de la ligne dans le fichier ?), et après parcourir la liste pour trouver le nombres d'entiers identique cote à cote mais je pense pas que la complexité soit meilleur...

[Graffito]

Code :

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

concaténer les deux listes, les trier

L'algorithme initial correspond déjà au dernier pas d'un tri-fusion.

J'aurais une solution si la plupart des documents sont petits (ordre de grandeur : moins de 200 lignes).
Est-ce le cas ?

[étoile de mer]

Bonjour à tous,
Je connais le problème de LittleWhite.
Ce sont des fichiers texte de taille de plus de 500 000 lignes

Merci

[mikhailo]

Je crois que etoile de mer a raison; j'ai eu un projet à faire comportant pas mal de traitement des mots et des dictionnaires (faisant 500k lignes environ), et quand j'ai abandonné le fichier texte en le transformant en un char**, le temps d'exécution est passé de 8h à 5-10 minutes.

[Médinoc]

@mikhailo: À ce point du programme, tout est déjà en RAM.

[LittleWhite]

Je crois que etoile de mer a raison; j'ai eu un projet à faire comportant pas mal de traitement des mots et des dictionnaires (faisant 500k lignes environ), et quand j'ai abandonné le fichier texte en le transformant en un char**, le temps d'exécution est passé de 8h à 5-10 minutes.

Je suis déjà avec des fichiers en mémoire.
Lorsque j'enlève mon nbOccurances dans la ligne de calcul, je passe facilement de 4j à 30 minutes.
Du coup, je sais où je dois optimiser ... mais je ne suis pas trop sur du comment.

Est ce que vous faites un algorithme du genre de celui que j'utilise, pour avoir le nombre de lignes communes, ou pas du tout? ( Car votre vitesse m'interesse )

[LittleWhite]

J'aurais une solution si la plupart des documents sont petits (ordre de grandeur : moins de 200 lignes).

Non, nous avons vraiment des grands cas. Je veux dire que par là, il n'est pas rare que la recherche de lignes communes se fasse sur des grands tableaux ( plus de 1000 cases )
J'ai pensé à faire une table de resultats, mais je ne suis pas que cela va beaucoup amélioré.

Je pense ( et je vais bientot l'appliqué ) que le time killer, ce sont les 'break;'