Calcul du nombres de lignes communes entre deux mots

**LittleWhite** · 21/05/2010, 23h43

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** · 22/05/2010, 02h10

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 ;

**Ubiquité** · 22/05/2010, 02h11

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** · 22/05/2010, 02h22

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** · 22/05/2010, 11h38

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

Merci

**mikhailo** · 22/05/2010, 11h46

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.

**LittleWhite** · 22/05/2010, 11h49

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;'

**Médinoc** · 22/05/2010, 11h51

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

**LittleWhite** · 22/05/2010, 11h51

Envoyé par 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.

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

)

**Graffito** · 22/05/2010, 12h30

Si les fichiers sont gros, la solution dans ma première réponse devrait améliorer les performances.

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 )

Quel est l'objectif recherché ?
Si il s'agit de detection de co-occurences (couples de mots voisins) dans un comparateur de document, on peut limiter la comparaison aux documents suffisament proches hors utilisation des co-occurences et utiliser les co-occurences seulement sur ce sous-ensemble de documents "proches".

**LittleWhite** · 22/05/2010, 12h40

Envoyé par Graffito

Si les fichiers sont gros, la solution dans ma première réponse devrait améliorer les performances.

Quel est l'objectif recherché ?
Si il s'agit de detection de co-occurences (couples de mots voisins) dans un comparateur de document, on peut limiter la comparaison aux documents suffisament proches hors utilisation des co-occurences et utiliser les co-occurences seulement sur ce sous-ensemble de documents "proches".

Objectif recherché, bah ... savoir le nombre de ligne commune entre deux mots ... et ce pour tout les mots du fichiers. Il n'y a pas de co-occurences spécifique, car on se base sur une similarité entre deux fichiers ...

**Ubiquité** · 22/05/2010, 13h02

Bien sûr le programme ne tourne pas sur une machine multi-coeurs ?

**LittleWhite** · 22/05/2010, 13h06

Envoyé par Ubiquité

Bien sûr le programme ne tourne pas sur une machine multi-coeurs ?

Pas toujours ....
Mais on pourrait ( enfin je ) lancé un deuxième thread ...

**LittleWhite** · 22/05/2010, 13h07

Envoyé par 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 ;

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...

**Pouet_forever** · 22/05/2010, 13h13

Je pense que le plus simple est d'agir en amont de ta fonction. Si tu as un tableau de Mot, tu les tries par ordre alphabétique, comme ça tu auras un temps beaucoup plus linéaire au moment de la comparaison.
Qu'est-ce que tu utilises comme structure de données pour stocker tes Mot ?

**LittleWhite** · 22/05/2010, 13h18

Envoyé par Pouet_forever

Je pense que le plus simple est d'agir en amont de ta fonction. Si tu as un tableau de Mot, tu les tries par ordre alphabétique, comme ça tu auras un temps beaucoup plus linéaire au moment de la comparaison.
Qu'est-ce que tu utilises comme structure de données pour stocker tes Mot ?

Je n'ai pas besoin de faire un tri alphabétique. Je ne vois pas en quoi cela me servirai ( pour le nombre de lignes communes des mots ).
Pour accéder aux Mot, j'utilise une table de hachage.
Pour savoir l'ordre des mots, j'ai un système qui reproduit virtuellement le fichier.

**Pouet_forever** · 22/05/2010, 13h21

Mea culpa, j'ai mal lu.

**Ubiquité** · 22/05/2010, 13h29

Grossièrement la technique de Graffito (qui est surement la meilleur idée) est de voir si on ne peut pas avancer de N en N au lieu de parcourir la liste de 1 en 1. Comme la liste est triée par ordre de croissant on ne peut pas sauter de ligne intéressante.

**LittleWhite** · 22/05/2010, 13h43

Envoyé par Ubiquité

Grossièrement la technique de Graffito (qui est surement la meilleur idée) est de voir si on ne peut pas avancer de N en N au lieu de parcourir la liste de 1 en 1. Comme la liste est triée par ordre de croissant on ne peut pas sauter de ligne intéressante.

Je vois, mais en fait, je ne vois pas comment on fait pour ne pas se louper, en faisant cette technique.
Je veux dire, je veux bien avancé de deux par deux ... mais comment je ne loupe pas une ligne ( je vais tenter un truc tout de suite ) ... mais je reste perplexe.

**Ubiquité** · 22/05/2010, 13h48

A force de bricolage je t'ai pondu ça :

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
const int N = 10;
 
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 limiteMot1MoinsN =	limiteMot1-N;
	unsigned int limiteMot2MoinsN =	limiteMot2-N;
 
	unsigned int compteur1 = 0;
	unsigned int compteur2 = 0;
 
	unsigned lignesCommunes = 0;
 
	while((mot1->lignes.tableau[compteur1] < mot2->lignes.tableau[compteur2] && compteur1 < limiteMot1 - 1 ) &&
		(mot1->lignes.tableau[compteur1] > mot2->lignes.tableau[compteur2] && compteur2 < limiteMot2 - 1 ))
	{
		while(mot1->lignes.tableau[compteur1] < mot2->lignes.tableau[compteur2] && compteur1 < limiteMot1 - 1 )
				if( compteur1 < limiteMot1MoinsN && mot1->lignes.tableau[compteur1+N] < mot2->lignes.tableau[compteur2])
					compteur1+=N;
				else 
					compteur1++;
 
 
		while(mot1->lignes.tableau[compteur1] > mot2->lignes.tableau[compteur2]] && compteu2 < limiteMot2 - 1 )
				if( compteur2 < limiteMot2MoinsN && mot1->lignes.tableau[compteur1] > mot2->lignes.tableau[compteur2+N])
					compteur2+=N;
				else 
					compteur2++;
 
 
		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;
			}
 
		}
 
 
	}
 
	return lignesCommunes;
}

J'aime bien les gros testes qui tâches.

Pour trouver le meilleur N il faudrait peut-être connaître la valeur moyenne de (lignesCommunes / le nombre de ligne).

Calcul du nombres de lignes communes entre deux mots

C

Discussions similaires

Partager

Partager