Discussion :

[dividee]

eyquem, j'ai testé ton code avec une liste de 4500 mots, et ça a mis près de 5 minutes (rien que pour la dernière boucle, la génération de la matrice). Mon code, pour le même échantillon, prend moins d'un seconde. L'utilisation mémoire est aussi plus élevée (114 MB max contre 78 MB max)

Le problème est que pour chaque mot (4500 dans mon test), tu parcours toute la liste liBINX (près de 150000 éléments), cela fait donc 675 millions d'itérations, et pour chaque itération, il faut en général 2 comparaisons de chaînes (if mot in binome).

Au total il y a donc 2 x 150 000 chaînes dans liBINX; chaque chaîne contient l'un des 4500 mots; en moyenne (sur toutes les itérations), la chaîne testée sera égale au mot seulement 1 fois sur 4500; cela fait donc 99,9778 % d'itérations qui ne produiront rien (enfin, en réalité un tout petit peu moins car le test (mot in binome) n'effectuera pas la seconde comparaison si la première est vraie), et ce pourcentage augmente si on augmente le nombre de mots. Ce sont ces itérations-là que mon algo évite de faire, alors même si le traitement par itération est un peu plus lourd, et la symétrie pas exploitée, on est largement gagnant...

En fait, cette discussion aurait autant sa place dans le forum algo que dans le forum python.

PS: le fichier mat.log n'est pas un fichier word, c'est un simple fichier texte.

[ekremyilmaz]

c terminé, j'ai rendu le projet!!

merci pour tous les gars

[eyquem]

Mon code reposait sur un double pari, celui que 2 hypothèses soient vérifiées:
- qu'il y ait peu de couples de mots co-occurents (dice strictement > 0) relativement à leur nombre maximal possible, c'est à dire une taille de liBINX "raisonnable".
- "raisonnable", ça voulait dire dans mon esprit que la taille de liBINX serait de taille suffisamment contenue pour qu'une list comprehension ne perde pas son avantage de rapidité par rapport à une utilisation de dictionnaire lors de la création de la liste des co-occurents d'un mot.

Mais ces deux hypothèses ne sont pas vérifiées.

Pour 4500 mots, le nombre max est (4500 x 4499 )/ 2 = 10 122 750.
Or 150 000 couples constatés, cela fait 1,5 % du maximum théorique, c'est donc effectivement peu, en relatif; mais en absolu cela fait beaucoup, surtout en parcourant 4500 fois cet ensemble avec 3 comparaisons à la clé. Il n'y a en effet pas seulement les 2 comparaisons de if mot in binome mais aussi celle contenue dans binome[binome[0]==mot], qui refait d'ailleurs ce que if mot in binome vient de faire.
J'ai bien essayé d'évaluer ce nombre de couples sur la base d'une longueur moyenne de 20 mots par phrase (statistique trouvée sutr internet) mais cette information n'était pas suffisante. Et comme je n'arrive pas à ouvrir mat1, je n'ai pas pu faire un test sur un échantillon de bonne taille comme tu l'as fait.

Second problème, c'est que je me faisais jusqu'à présent des illusions sur l'avantage de rapidité des list comprehension par rapport aux dictionnaires:
je voyais l'exécution d'une list compréhension un peu comme un passage du héros de BD Flash à la vitesse de l'éclair au milieu d'une liste.
Quant aux dictionnaires, j'avais l'idée que le fait que les éléments d'un dictionnaire ne soient pas ordonnés avait pour conséquence qu'il lui faut d'abord chercher dans la liste de ses clés quand on lui demande une des valeurs, et donc que l'obtention d'une valeur d'un dictionnaire devait être plus longue que la recherche directe de cette valeur dans une liste sans passer par une clé.

Je constate sur les résultats que nous avons obtenu que ces deux idées sont fausses.
Quand on dit que les list comprehension sont rapides, je pense maintenant que ce doit être relativement à une boucle for, mais elles prennent leur temps aussi dans l'absolu.
Quant aux dictionnaires, l'accès à une valeur doit être beaucoup beaucoup plus rapide que je ne l'imaginais.

Ce qui fait que même si je trouve mon algorithme plus facilement lisible, le tien est supérieur car le critère important pour le problème à résoudre, c'est bien le temps d'exécution. J'ai essayé de modifier mon code pour éviter de faire les comparaisons présentes dans ma list comprehension, mais ça conduit inévitablement à recourir au dictionnaire dico3. Il est clair maintenant qu'il n'y a pas d'autre solution que de passer par le dico3 que tu utilises.

----------------------

Cependant je persiste à penser qu'on peut et qu'il est mieux d'éviter de passer par un dico2 pour créer dico3.
Et je propose donc un code, reprenant celui de dividee, devant prendre la main après que le code d'ekrenmyilmaz aura créé dico3: , sans créer dico2.

code de ekremyilmaz:
2 fichiers texte avec des délimiteurs {S}
---> dico1 = { 1:[A,B,C,D,E] ; 2:[A,C,D,E] ; 3:[B,D,E]}
puis
---> dico3 = { A:{B:1,C:2,D:2,E:2} , B:{A:1,C:1,D:2,E:2} , C:{A:2,B:1,D:2,E:2} , D:{A:2,B:2,C:2,E:3} , E:{A:2,B:2,C:2,D:3} }

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
 
dico3 = {}
N = defaultdict(int)
i = 0
print 'Longueur du dictionnaire à traiter : ',len(dico1)
print '\ntop départ                   temps t0'
t0 = clock()
for limots in dico1.values():
    i += 1
    if i%2000==0:
        print str(i)+' ème élément de dico3   ', round(clock()-t0,4),'secondes'
    for mot in limots:
        N[mot] += 1
        if not dico3.has_key(mot):
            dico3[mot] = defaultdict(int)
        lis = limots[:]
        lis.remove(mot)
        for autre_mot in lis:
            N[autre_mot] += 1
            dico3[mot][autre_mot] += 1
        del lis
 
del dico1 # plus besoin
 
def dice(A,B,X): # A,B,X = mot,motcooc,entier
    return float(X+X)/float(N[A]+N[B])
 
# calcul du 'dice' et extractions des 'm' meilleurs résultats:
outputname = "matricecooccurrenceTest"
f = file(outputname, "w")
m = 20
 
for mot, words in dico3.iteritems():
    licoocX = [  ( float(X+X)/float(N[mot]+N[motcooc]) , motcooc )  for motcooc, X in words.iteritems()]
    # licoocX : liste de doublets (valueDice,co-occurent de mot)
    licoocX.sort(reverse=True)
    slicoocs = [ c for d,c in licoocX[0:m] ]
    f.write('<' + mot + '>' + '##'.join(slicoocs) + '</'+mot+'>\n')
 
f.close()

J'ai introduit

Code :

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

1
2
3
        lis = limots[:]
        lis.remove(mot)
        for autre_mot in lis:

au lieu de

Code :

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

1
2
        for autre_mot in limots:
            if autre_mot<>mot:

Au lieu de répéter une comparaison if sur tous les autre_mot , on exécute une seule fois remove(mot).
J'aimerais bien savoir si ça influera sur la durée de traitement.
NB : pour pouvoir le faire il faut que les valeurs de dico1 soient des listes.

---------

Voilà. Je me suis bien amusé et ai bien appris sur ce problème.
Je retiens defaultdict() qui est très intéressant à connaître.
Et j'aurai plus de considération envers les dictionnaires désormais, c'est promis.

[eyquem]

Pour remplir le dictionnaire N (nombres d'occurences des mots), il vaut mieux faire comme l'a fait dividee, c'est à dire après avoir créé un dictionnaire dont les clés sont les mots, en l'occurence dico3.
Ça évite ainsi d'ouvrir 672 011 fois une case ou une autre de N pour y faire += 1. Avec len() , on ne fait que 4500 fois fois N[mot] = len(dico3[mot])

Donc après correction, revoici mon code.
Au passage , pas besoin de la définition de fonction dice() puisque j'ai intégré le calcul dans le main code.

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
dico3 = {}
i = 0
print 'Longueur du dictionnaire à traiter : ',len(dico1)
print '\ntop départ                   temps t0'
t0 = clock()
for limots in dico1.itervalues():
    i += 1
    if i%2000==0:
        print str(i)+' ème élément de dico3   ', round(clock()-t0,4),'secondes'
    for mot in limots:
        if not dico3.has_key(mot):
            dico3[mot] = defaultdict(int)
        lis = limots[:]
        lis.remove(mot):
        for autre_mot in lis:
            dico3[mot][autre_mot] += 1
        del lis
 
del dico1 # plus besoin
 
N = {}
for mot in dico3.iterkeys():
    N[mot] = len(dico3[mot])
 
# calcul du 'dice' et extractions des 'm' meilleurs résultats:
outputname = "matricecooccurrenceTest"
f = file(outputname, "w")
m = 20
 
for mot, words in dico3.iteritems():
    licoocX = [  ( float(X+X)/float(N[mot]+N[motcooc]) , motcooc )  for motcooc, X in words.iteritems()]
    # licoocX : liste de doublets (valueDice,co-occurent de mot)
    licoocX.sort(reverse=True)
    slicoocs = [ c for d,c in licoocX[0:m] ]
    f.write('<' + mot + '>' + '##'.join(slicoocs) + '</'+mot+'>\n')
    print '<' + mot + '>' + '##'.join(slicoocs) + '</'+mot+'>'
f.close()

Remarque: les mots du texte qui n'apparaissent que dans des phrases où ils sont le seul mot ne donnent pas lieu à la création d'un couple clé:valeur dans dico3 dans ce code.

[dividee]

J'ai utilisé dico2 car je voulais présenter un code complet, exécutable à partir de mat1.log, et on est bien obligé dans ce cas de passer par dico2 (ou un structure de donnée équivalente) pour pouvoir générer dico1. Si, effectivement, ekremyilmaz disposait déjà de dico1, comme il le laisse sous-entendre, cela peut sembler inutile, mais j'imagine que produire ce dico prenait déjà pas mal de temps, et c'est donc raisonnable de le décharger dans un fichier afin de ne pas devoir le reconstruire à chaque exécution (au passage, il aurait été plus efficace d'utiliser pickle). Donc comme dico2 était de toute façon disponible je n'ai pas hésité à l'utiliser; ton code montre qu'on peut s'en passer, mais à première vue le temps d'exécution reste du même ordre de grandeur:

Temps de génération de dico3 avec 4500 mots:
mon code: 1,5s (+1,2s pour le chargement de dico2, +2,5s pour la création de dico1)
ton code: 2s

Donc si dico2 est de toute façon disponible, mon code est plus rapide. Si seul dico1 est disponible, j'ai mesuré le temps pour recréer dico2 à partir de dico1: 0,6s. Donc mon code, adapté à tes hypothèses, prend 2,1s; le tien est donc un petit peu plus rapide dans ce cas-là.

Le temps d'accès à un élément d'un dico est constant (sauf dans des cas pathologiques que je n'ai jamais rencontré), car un dictionnaire en Python est implémenté au moyen d'une table de hachage (en C, et très optimisé). Le temps d'accès à un élément donné est un peu plus lent que l'accès à un élément d'une liste, car il faut calculer la fonction de hachage, mais dès qu'il faut consulter plus de 2 ou 3 éléments d'une liste pour trouver le bon, et que le dictionnaire permet de le trouver directement, ce dernier est plus rapide.

J'ai fait un petit test, et une compréhension de liste est effectivement plus rapide qu'une boucle for, d'un facteur 3 environ lorsqu'il n'y a pas de calcul à effectuer (genre: [e for e in l]), mais cet avantage diminue si il y a des calculs (genre: [(float(X+X)/float(N[mot]+N[motcooc]) for ...]).

[eyquem]

Je suis bien d'accord que comme nous ne disposons pas au départ d'un fichier contenant dico1, on est bien obligé de partir de mat1, dont on ne peut tirer que dico2.
Moi même pour tester mes codes je crée le dico1 en faisant mat1 --> dico 2 --> dico1.

Mais dans le cadre d'une réponse à quelqu'un dont le projet est de passer de ses 2 fichiers avec délimiteurs {S} à ce qu'il appelle la matrice de cooccurence, j'estime que dico1 doit être considéré comme la donnée de départ.
En fait je trouve que le raisonnement d'ekren consistant à penser s'appuyer sur dico2, en ne voyant pas, comme toi tu l'as vu par contre, qu'il lui faut dico3 et non pas dico2, n'est pas bonne et qu'elle dénote un manque de vision globale. Je pense lui faire une bonne réponse en lui faisant remarquer qu'on peut se passer de dico2, ça élargit l'approche. On n'est pas obligé de rester coincé dans les problèmes tels qu'ils sont posés.




Je ne comprends pas bien les temps que tu donnes . Il s'agit de

mat1 ---> dico2 en 1,2 s ?
dico2 ---> dico1 en 2,5 s ?
dico1 et dico2 ---> dico3 ---> matrice en 1,5 s ?

Si c'est bien ça, alors
dico2 ---> dico1 et dico2 ---> dico3 ---> matrice serait 4 secondes ?

Et pour mon code, c'est 2 s pour

dico1 ---> dico3 ---> matrice ?

Je ne m'attendais pas à voir le temps d'exécution divisé par 10 avec mon code. Mais il me semble que
dico 1 ---> dico3
devrait logiquement être un tantinet plus rapide que
dico1 ---> dico2 + dico1 ---> dico3.
C'est ceci que je pense.

Or avec ton code, tu fais tourner:
dico2 ---> dico1 et dico2 ---> dico3 ---> matrice
Et moi je dis qu'il faut faire
dico1 ---> dico3 ---> matrice

Ce sont des programmes non strictement comparables.



Merci pour les explications sur les dicos et les listes qui précisent bien les choses sur un point important.

[dividee]

Je n'avais pas mesuré le temps de génération de la matrice; vu qu'on utilise la même méthode, je m'attendais à ce que les temps soient fortement semblables.
Les temps que j'ai mesurés sont:

Code :

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

1
2
3
4
5
mat1 --> dico2 : 1,2s
dico2 --> dico1 : 2,5s
dico1 & dico2 --> dico3: 1,5s
dico1 --> dico3: 2s (ton code)
dico1 --> dico2: 0,6s

Donc si on part de dico1 au lieu de mat1:

Code :

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

1
2
dico1 --> dico3: 2s (ton code)
dico1 --> dico2 --> dico3: 1,5s +0,6s = 2,1s (mon code)

Pour info, la génération de la matrice (dico3 & N (=réutilisation de dico2 dans mon code) --> matrice) prend 0,25s avec ton code comme avec le mien, pour l'échantillon de 4500 mots; mais avec la matrice de 44000 mots, ce temps domine les autres (j'avais environ 5 min pour la génération de la matrice et 1min40 pour toutes les autres étapes).

[ekremyilmaz]

vous avez surement raison que de passer de dico1 à dico3, c'est la meilleure solution mais j'étais dans l'urgence, vu que le calcul était assez long pour créer le dico 1, j'ai décidé de le stocker dans un fichier pour ensuite faciliter le calcul de la matrice.

tout n'a pas été optimal mais je peux vous assurer que la méthode de dividee est celle qui a été la plus efficace pour répondre dans l'urgence à mon besoin.

Bien sur que l'on peut encore optimiser le code. Mais quand Eyquem dit qu'il me manque une vision globale, il faut considérer le temps qu'il me restait vu que j'ai bloqué énormément sur la matrice de cooccurrence pendant 1 semaine, il me restait très peu de jour.

Donc parfois, pour répondre à un besoin dans l'urgence, il faut adopter des choix qui fonctionnent

Mais on va continuer à élaborer un algo efficace.