optimiser un algorithme

Version imprimable

10/06/2010, 02h03
étoile de mer

optimiser un algorithme

Bonjour à tous,
ça fait des mois que je bosse sur ce problème, mais jusqu'à ce jour, je ne trouve pas une solution :
J'explique
J'ai deux fichier texte : un en français et l'autre en anglais sachant que chacun des fichier contient plus que 500000 ligne (donc vous pouvez imaginer dès maintenant les problème liés à la vitesse, la mémoire,..) :?

voilà un exemple des 2 fichier :

Fichier FR:
Bonjour les amis
Bonjour les bons amis

Fichier ANG :
Good morning friends
Good morning friends of world.

Donc le but ce ce programme c'est d'extraire des rgles de cette forme là :
2mot contigues FR->1mot ANG (valeur de prob)

Mot1 : 1er mot des 2 mots contigues en FR
Mot 2 : 2eme mot des 2 mots contigues en FR
Mot3 : Mot en anglais
telque valeur de pro =(pMot1Mot3 * log2(pMot1Mot3 / (pMot1 * pMot3)) )+ (pMot1Mot2Mot3 * log2( (pMot1Mot2Mot3 * pMot1) / (pMot1Mot2 * pMot1Mot3) ))
tel que :
*) pMot1Mot3 = nombre de lignes où apparaisent les mot1 et mot3 ensemble / nombre total de ligne de fichier
*) pMot1 = nombre de lignes où apparaisent les mot1 / nombre total de ligne de fichier
*) pMot3 = nombre de lignes où apparaisent les mot3 / nombre total de ligne de fichier
*) pMot1Mot2Mot3 = nombre de lignes où apparaisent les mot1 , mot2 et mot3 ensemble / nombre total de ligne de fichier
*) pMot1Mot2 = nombre de lignes où apparaisent les mot1 et mot2 ensemble / nombre total de ligne de fichier.

Donc en suivant cet exemple on trouve ca comme resultat :

Bonjour les->good(0.52148)
Bonjour les->morning (0.5412)
Bonjour les-> friends (0.325147)
Bonjour les->of (0.65812)
Bonjour les-> world (0.82452).

Franchement j'ai essayé pas mal de fois avec différents structures de données, mais le problème reste le même c'est la lenteur d'exécution, il reste environ 5ou 6 jours tourner.
Alors que mon boss m'a dit de chercher une solution le plus rapidement possible de tel façon il tourne que pendant des heures.

Est ce que vous pouvez me donner des idées svp?

Merci

Je serai reconnaissante

Bonjour,

Petites questions en vrac, désolé si certaines semblent trop naïves.

Le compilateur est-il bien réglé en mode release
Des fioritures sont-elles présentes ? (barre de défilement trop souvent rafraichie, de trop nombreux printf...)
L'accès au fichiers est il optimisé (pas d'utilisation d'appels système)
Les valeurs utilisés dans plusieurs calculs sont elles stockées plutôt que re-calculées à chaque fois ? *
La formule est elle optimisée ? **
Comment est calculé log2 ?

* Par exemple, si on travaille sur (bonjour, les, good) puis sur (bonjour, les, morning) on peut réutiliser pMot1, pMot2 et pMot1Mot2. (et les logarithmes associés, voir ce qui suit)

** Sachant que log(A*B) = log(A) + log(B), on peut écrire :
Code:

1 2 3 4 5 6 7 8 pro =(pMot1Mot3 * log2(pMot1Mot3 / (pMot1 * pMot3)) ) + (pMot1Mot2Mot3 * log2( (pMot1Mot2Mot3 * pMot1) / (pMot1Mot2 * pMot1Mot3) )) pro = pMot1Mot3 * (log2(pMot1Mot3) - log2(pMot1) - log2(pMot3)) + pMot1Mot2Mot3 * ( log2( pMot1Mot2Mot3 ) * log2(pMot1) - log2(pMot1Mot2) - log2(pMot1Mot3) )
On voit ici qu'on peut même précalculer log2(pMot1) et log2(pMot1Mot3), pour voir si on y gagne.

Citation:
Envoyé par mabu
Bonjour,

Petites questions en vrac, désolé si certaines semblent trop naïves.

Le compilateur est-il bien réglé en mode release
Des fioritures sont-elles présentes ? (barre de défilement trop souvent rafraichie, de trop nombreux printf...)
L'accès au fichiers est il optimisé (pas d'utilisation d'appels système)
Les valeurs utilisés dans plusieurs calculs sont elles stockées plutôt que re-calculées à chaque fois ? *
La formule est elle optimisée ? **
Comment est calculé log2 ?

* Par exemple, si on travaille sur (bonjour, les, good) puis sur (bonjour, les, morning) on peut réutiliser pMot1, pMot2 et pMot1Mot2. (et les logarithmes associés, voir ce qui suit)

** Sachant que log(A*B) = log(A) + log(B), on peut écrire :
Code:

1 2 3 4 5 6 7 8 pro =(pMot1Mot3 * log2(pMot1Mot3 / (pMot1 * pMot3)) ) + (pMot1Mot2Mot3 * log2( (pMot1Mot2Mot3 * pMot1) / (pMot1Mot2 * pMot1Mot3) )) pro = pMot1Mot3 * (log2(pMot1Mot3) - log2(pMot1) - log2(pMot3)) + pMot1Mot2Mot3 * ( log2( pMot1Mot2Mot3 ) * log2(pMot1) - log2(pMot1Mot2) - log2(pMot1Mot3) )
On voit ici qu'on peut même précalculer log2(pMot1) et log2(pMot1Mot3), pour voir si on y gagne.
Bonjour Mabu,
Je te remercie pour ta reponse et d'avoir pris la peine de lire mon message

Le compilateur est-il bien réglé en mode release
Des fioritures sont-elles présentes ? (barre de défilement trop souvent rafraichie, de trop nombreux printf...)

Concernnat des 2 point ils sont bien reglés oui , je suis sûre de ça,
Mais

L'accès au fichiers est il optimisé (pas d'utilisation d'appels système)
Comment est calculé log2 ?
L'accès au fichiers est il optimisé (pas d'utilisation d'appels système)

Je ne suis pas sûre de ça :(

et

Citation:

* Par exemple, si on travaille sur (bonjour, les, good) puis sur (bonjour, les, morning) on peut réutiliser pMot1, pMot2 et pMot1Mot2. (et les logarithmes associés, voir ce qui suit)

Je ne vois pas trop comment faire ça.
(je pense que je vais tout recommencer dès le debut
Pour les Log2, ya un probleme? :roll:, j'utilise la biblio math.h et je mets Log2 directement

Merci beaucoup

10/06/2010, 11h08
Invité(e)
Citation:
Envoyé par étoile de mer

Citation:

L'accès au fichiers est il optimisé (pas d'utilisation d'appels système)

Je ne suis pas sûre de ça :(
Pour travailler avec les fichiers, utilises tu open/read... qui sont des appels systèmes à éviter donc, ou plutôt fopen/fread... ?

Citation:

Pour les Log2, ya un probleme? , j'utilise la biblio math.h et je mets Log2 directement

Je pose la question car j'ai déjà vu écrit :

Code:

#define log2(x) log(x)/log(2)

ce qui n'est pas un modèle d'optimisation.
10/06/2010, 11h45
diogene

@mabu :
La formule alternative pour pro est sans doute plus lente à exécuter que la formule d'origine :
Elle demande le calcul de 5 log() et 8 opérations "élémentaires" (5 +- et 3*) alors qu'à l'origine il suffisait de 2 log() et 8 opérations "élémentaires" (2+-, 2* et 4/). Le temps de calcul des log() est certainement pénalisant.

@étoile de mer :
Probalement, le temps pour établir les différents paramètres pMot1Mot2Mot3, pMot1Mot2, pMot1Mot3,... doit être bien supérieur à celui du calcul de pro une fois ces paramètres obtenus.
10/06/2010, 13h24
étoile de mer

Citation:

Envoyé par diogene

@mabu :
@étoile de mer :
Probalement, le temps pour établir les différents paramètres pMot1Mot2Mot3, pMot1Mot2, pMot1Mot3,... doit être bien supérieur à celui du calcul de pro une fois ces paramètres obtenus.

Merci Diogene,
Je ne vois pas ce que tu veux dire, tu peux s'il te plait m'expliquer un peu?
Merci
10/06/2010, 13h52
étoile de mer

Re,
Juste j'ai encore reflechi comment encore optimiser. MAis je sais pas si je suis sur le bon chemain.
Comment trouverez vous ma nouvelle idée expliquée ci dessous? :roll:

Je cree une table de hachage dans laquelle je vais stocker la structure de donnée Regles:
Regle{
Char* 2Mot FR,
char * mot ANG
}

Cette table sera remplie lors de la lecture du fichier,

Apres je crée encore une table de hachage 1 pour stocker les MOT1FR, MotANg et leurs nombre d'occurence
meme chose , une autre table pour Mot2FR, MotANG..

Comme ca pour le calcule de la formule j'accede directement à l'information
Non? :roll:

Comment vous voyez mon idée, idiote ? :aie:

Merci de me repondre
10/06/2010, 22h15
LittleWhite

Bonjour à tous,

Je dois aussi apporter ma pierre ici.

Citation:

L'accès au fichiers est il optimisé (pas d'utilisation d'appels système)

L'optimisation des fichiers en enlevant les appels système a été faite depuis le début ( ce que j'appelle souvent les fichiers virtuels ).

Citation:

Comment est calculé log2 ?

Normalement on utilise le bon log2, par là, je veux dire que c'est celui de la math.h, et même que pour avoir celui là, il faut compiler avec -std=c99

Citation:

Le compilateur est-il bien réglé en mode release

Oui très bien réglé d'après moi ... il a le classique -O3, et l'additionnel -DNDEBUG ( vue qu'il y a des assertions partout ... c'est mieux ).

Citation:

Des fioritures sont-elles présentes ? (barre de défilement trop souvent rafraichie, de trop nombreux printf...)

Peut être quelque printf en trop ... surtout que j'utilise le \r .... qui bufferise ... donc je ne sais pas si c'est une cause de ralentissement critique.

Maintenant, ce que j'ai à dire en plus

Actuellement, les structures sont faites à la mains. Je veux dire par là, que l'on se bat avec des listes dynamiques ( une histoire de réalloc, et non de listes chainées ), et des tables de hachage. Les tables de hachage ... sont fixes, et puis la fonction de hachage n'est peut être pas la meilleure ...
Du coup, mon idée serait de passer sur le C++, non pas pour l'objet, mais pour la bibliothèque standard. Est ce que c'est une bonne initiative ou pas du tout?
Est ce qu'il y a aussi bien en C ... comme bibliothèque pour les structures de donnée. Qui marche sur Linux et Windows ( au moins ).

Deuxième point, je voulais limité le calcul des lignes communes ( la probabilité des Mot1Mot3, et celle des Mot1Mot2Mot3, et celle des Mot1Mot2 ). Pour faire ceci, je voulais faire une table de hachage ( ou deux ). Mais lors de mon essai, elles m'ont prises trop trop de mémoire. Pour tant je ne stocké que trois pointeurs et 12 octets dans une structure. Enfin la mémoire par en fumée ...
Et puis avec cette méthode, c'est que lorsque nous allons faire le calcul des 6FR -> 6EN ( taille de séquences de 6 mots ), presque autant de séquences va être trouvé que le nombre de mots dans les fichiers ( les fichiers font près de 15 Millions de mots ).
La structure annoncé par étoile de mer, aura le même problème je crois. Car elle dépendera de 15 Millions de mots * 2 ...

Je perd aussi du temps a essayer de garder une liste trié des 100000 meilleures ( * 100 ) résultat. Car en fait, c'est une liste trié de 100000 listes triés :'(.
Je me demande si avec une bibliothèque de structure de donnée, je ne pourrais pas avoir mieux ( je pense que si ).

Voilà, je suis ouvert à toute idée :)
10/06/2010, 22h29
orfix

Citation:

Envoyé par LittleWhite

Est ce qu'il y a aussi bien en C ... comme bibliothèque pour les structures de donnée. Qui marche sur Linux et Windows ( au moins ).

Oui la GLib par exemple.

Citation:

Envoyé par http://library.gnome.org/devel/glib/stable/glib.html

GLib is a general-purpose utility library, which provides many useful data types, macros, type conversions, string utilities, file utilities, a main loop abstraction, and so on. It works on many UNIX-like platforms, Windows, OS/2 and BeOS. GLib is released under the GNU Library General Public License (GNU LGPL).
11/06/2010, 07h30
LittleWhite

Citation:

Envoyé par ssmario2

Oui la GLib par exemple.

Je viens de parcourir la documentation, et il me manque juste un truc ... les listes ( Arrays ) d'éléments, mais qui sont uniques.
Quel est le mieux, si je veux implémenter un tel truc:
- Vérifié à chaque inclusion s'il l'élément est déjà présent, et réagir en conséquence
- A la fin, faire un tri, viré les doublons ?

( Je crois que la deuxième méthode est mieux ... )
13/06/2010, 21h32
étoile de mer

Bonsoir,
Là j'utilise les GHashTable de la glib.
Mais mon probleme c'est que ces tables de hachage prennent vraiment trop de mémoire,
quelqu'un possède une idée pour remédier à ce probleme ? :roll:

Merci
15/06/2010, 23h11
salseropom

Citation:

Envoyé par LittleWhite

Je viens de parcourir la documentation, et il me manque juste un truc ... les listes ( Arrays ) d'éléments, mais qui sont uniques.
Quel est le mieux, si je veux implémenter un tel truc:
- Vérifié à chaque inclusion s'il l'élément est déjà présent, et réagir en conséquence
- A la fin, faire un tri, viré les doublons ?

( Je crois que la deuxième méthode est mieux ... )

Salut, je m'éloigne sûrement du coeur de ton problème, mais en C++, les std::map pourront t'aider. Tout est déjà codé.
En revanche, je n'ai pas analysé les temps de calculs. Es-tu obligé de faire ton programme en C ? Ne peux-tu pas migrer en C++ (uniquement parce que les std::map sont déjà implémentées en C++) ?

Bon courage
15/06/2010, 23h24
LittleWhite

Citation:

Envoyé par salseropom

Salut, je m'éloigne sûrement du coeur de ton problème, mais en C++, les std::map pourront t'aider. Tout est déjà codé.
En revanche, je n'ai pas analysé les temps de calculs. Es-tu obligé de faire ton programme en C ? Ne peux-tu pas migrer en C++ (uniquement parce que les std::map sont déjà implémentées en C++) ?

Bon courage

Oui les std::map, j'y pensais ... mais finalement je suis resté en C , et j'ai pris la glib ( qui aide beaucoup, tout de même ). Donc je pense qu'il n'y a pas trop de différence entre std::map et les GHastTable.

Mais le problème reste entier ... les tables sont vraiments trop grosses :p ... mais bon je ne pense pas que l'on puisse faire mieux.
L'idée serait aussi d'avoir un truc rapide ... en utilisant peu de table ... mais je n'arrive pas à imaginer une telle solution ...