optimisation fichier long

**ekremyilmaz** · 29/11/2008, 16h21

Bonjour, avant d'expliquer mon pb,
je vous montre un exemple :
j'ai un fichier
<motA>1##2##3##4</motA>
<motB>1##4##8</motB>
<motC>5##8##10</motC>
<motD>35##32##10</motD>
<motE>52##81##102</motE>
je dois comparer
<motA> avec <motB>
<motA> avec <motC>
<motA> avec <motD>
<motB> avec <motC>
<motB> avec <motD>
<motC> avec <motD>

donc

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
 
f = openFile("mat1.log")
lp = f.readlines()
fg = openFile("mat1.log")
d = fg.readlines()
n=1
chaine=[]
countList={}
for i in lp:
	listeA = re.findall('<.*?>(.*?)</.*?>',i)
	element = re.findall('<(.*?)>',i)
	chaine.append("<" + element[0] + ">")
	for j in d[n:]:
		listeB = re.findall('<.*?>(.*?)</.*?>',j) #recupère la liste entre les balises
		elementj = re.findall('<(.*?)>',j)#récupère l'élement de la balise
		diceValue = dice(creerListe(listeA[0]),creerListe(listeB[0])) 
#creerListe qui transforme la chaine 5##8##10 en une liste de 3 élements
		if diceValue > 0.0 and diceValue < 1.0:
                        countList[elementj[0]]=diceValue
	lcountlist = countList.items()
	lcountlist.sort(key=operator.itemgetter(1),reverse=True)
	lcountlist = lcountlist[:m]
	for alllist in range(len(lcountlist)):
		if alllist != len(lcountlist) - 1:
			chaine.append(lcountlist[alllist][0]+"##")
			else:
				chaine.append(lcountlist[alllist][0])
		chaine.append("</" + element[0] + ">\n")
		n+=1
		cp+=1
	f1 = open("matricecooccurrenceTest.log","w")
	f1.writelines(chaine)
	f1.writelines(chaineAutre)
	f.close()
	f1.close()
	fg.close()

le code est trop long je trouve.
c'est un très gros fichier,je sais pas si mon algo est optimale, mais là, j'ai lancé le fichier pendant 16h
et il n'a meme pas traité 50000 mots.
il y a au total 150000 mots (lignes) à traiter.

**oiffrig** · 29/11/2008, 17h24

Déjà, compile tes regex

Code :

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

1
2
r1 = re.compile('<.*?>(.*?)</.*?>')
r2 = re.compile('<.*?>(.*?)</.*?>')

(ensuite, tu utilises par exemple listeA = r1.findall(i))
Ensuite, je doute que ce soit raisonnable pour un gros fichier de le lire avec readlines(), qui plus est, deux fois !
Tu peux itérer sur les lignes du fichier

Code :

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

1
2
for ligne in fichier:
    traiter(ligne)

Ou bien utiliser readline() qui renvoie une ligne à la fois et passe automatiquement à la suivante
De même pour l'écriture, mieux vaut écrire au fur et à mesure.
Ensuite, tu effaces ton fichier de sortie à chaque itération, ce qui n'est pas très judicieux je pense.

**ekremyilmaz** · 29/11/2008, 17h30

non j'efface les fichiers à la fin,
c'est juste le copier /coller sur l'interface qui est mal passé

!!

merci, je vais essayer tes recommandations

**ekremyilmaz** · 29/11/2008, 17h42

en fait, dans mon cas lire le fichier ligne par ligne n'est pas très judicieux.
car étant donné que je dois comparer chaque ligne entre elle:

comme
ligne1 avec ligne2
ligne1 avec ligne3
ligne1 avec ligne4
ensuite
ligne2 avec ligne3
ligne2 avec ligne4

si je lis ligne par ligne.
je vais comparer
ligne1 avec ligne1
ligne1 avec ligne2
etc..
ligne2 avec ligne1
ligne2 avec ligne2
etC...
la complexité est O(n²)
et là c lourd.
j'ai voulu les mettre dans readlines() pour avoir une liste
et ensuite avec liste[n:]
ça m'évite de comparer les valeurs précédentes.

**ekremyilmaz** · 29/11/2008, 18h03

j'ai une fonction creerListe

Code :

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

1
2
3
def creerListe(list):
	l = list.split("##")
	return l

à chaque r1.findall(i)
il me retourne la chaine qui se trouve entre les balises <i>
par ex : 1#2#3#4
et là, je souhaite mettre chaque élément dans une liste = ["1","2","3","4"]
à ton avis, le split c'est une bonne solution ou ça ralentit aussi, car il arrive parfois qu'il y ait une chaine avec 400 mots séparé des #. (y en a meme plusieurs cas similaires)

**ekremyilmaz** · 29/11/2008, 18h09

en fait split ou pas split, c pareil,
j'ai enlevé tout le code à l'intérieur de la seconde boucle.
ça rame tjs autant.
je crois
que c les boucles imbriquées, ça prend énormément de temps.

là je vois pas trop comment faire

!!

**oiffrig** · 29/11/2008, 18h13

(Petite note, les 2 méthodes sont en O(n²) en nombre de lignes lues)
Ce que je te conseille, c'est de traiter d'abord une fois le fichier (tous les découpages à faire) comme ça tu n'auras plus qu'une liste de listes à parcourir après.

Pour le découpage, tu peux te limiter à une regex :
Si ligne contient la ligne à traiter :

Code :

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

1
2
3
rx = re.compile('<(.*?)>(.*?)</.*?>')
#dans ta boucle de traitement:
element = rx.findall(ligne) #liste (nom, valeur)

**ekremyilmaz** · 29/11/2008, 18h23

si j'ai bien compris, je dois parcourir le fichier une fois pour récupérer dans une liste toutes les lignes
par ex:
liste = ["<a>1#2#3</a>","<b>2#4#1</b>"]

mais après je ne vois pas la solution, car je vais tout de même devoir faire une double imbrication pour comparer chaque mots entre eux.

à moins que parcourir une liste, ça prend moins de temps ?

**eyquem** · 29/11/2008, 18h25

À vue de nez, c'est sûr et certain que ça ne peut que ramer. Python et les ordinateurs sont puissants, mais il ne faut quand même pas exagérer dans ce qu'on leur demande. Je peux me tromper mais il me semble que ton code est bourré de mauvaises pratiques, et plus grave, que c'est l'algorithme lui-même qui me semble mauvais. Il va falloir te faire à l'idée que ton code est à reprendre de fond en comble. À mon humble avis.

Avant tous les autres problèmes, il y a que tu ne donnes pas assez de renseignements sur ce projet de programme.

Quelle est la structure excate du fichier "mat1.log" à examiner ? Le peu que je comprends du code ne colle pas avec ce que tu en dis.

Qu'est ce que le programme est censé faire d'un point de vue général ?

Je vois
if diceValue > 0.0 and diceValue < 1.0
dice (Qu'est ce que c'est ce truc de "dice" ?)
sort.
Question importante: un tri de quelque chose doit il être réalisé à un moment ou un autre lors de l'exécution ? Ce tri a-t-il une importance centrale dans le programme ? Si oui, il faut penser l'algorithme autour de cette nécessité.

Un autre point autour duquel concevoir l'algorithme, c'est la grande taille de ton fichier de départ. Ça exclut d'en faire une lecture complète d'un coup avec readlines() car readlines() crée une liste, c'est à dire un objet-liste en mémoire vive de l'ordinateur. Si la liste est énorme et la RAM un peu insuffisante, l'encombrement de la RAM diminue la vitesse d'exécution.
Quelle est la taille de ta RAM et pendant qu'on y est la fréquence de ton CPU (processeur) ?

Faire f.read() au lieu de f.readlines() ne résoudra rien. f.readlines() crée une liste et f.read() crée une chaine de caractères, mais les deux contiendront approximativement le même nombre de caractères.

Il va falloir t'orienter sur une lecture et un traitement par à coups du fichier, et pour faciliter le tritement il faudra vraisemblablement faire appel aux fonctions seek() et tell().

---

Le mieux pour comprendre exactement la structure du fichier serait que tu exécute dessus le petit bout de programme suivant, et ensuite, si tu veux bien nous dire ce que tu veux que le programme fasse sur le fichier, on pourra peut être avancer.

Code :

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

1
2
3
4
5
f = openFile("mat1.log")
lp = f.readlines(1500)
for ln in lp:
    print ln
f.close()

**eyquem** · 29/11/2008, 18h34

Comme te l'a dit oiffrig, il va falloir t'orienter sur une lecture et un traitement par à coups du fichier, c'est à dire ne pas lire le fichier d'un coup d'un seul . Tu ne peux pas y échapper à mon avis.

Rassure toi: pour permettre le traitement, tu pourras faire appel aux fonctions seek() et tell().

**kedare** · 29/11/2008, 18h37

Pense a utiliser psyco aussi

**eyquem** · 29/11/2008, 18h43

Je pense que Psyco sera utile au final mais de mon point de vue ce n'est pas une bonne chose d'accélerer un mauvais programme, ça n'en fait pas un bon.
Même si Psyco abaissait le temps d'exécution de 64 heures à 3 heures, ça resterait mauvais étant donné qu'à vue de nez je dirais que son programme doit pouvoir tourner en 10 minutes maxi si l'algorithme est bien pensé (quoique je m'avance beaucoup étant donné que je ne connais pas vraiment Psyco et que je n'ai encore pas compris ce qu'il veut faire avec son programme).

**ekremyilmaz** · 29/11/2008, 18h50

le fichier mat1.log, je le crée avec une fonction
elle ressemble à ç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
 
<trêve des confiseurs>1872</trêve des confiseurs>
<rêve américain>787##1872</rêve américain>
<désunion>4917</désunion>
<bouddhisme>3344##4805</bouddhisme>
<four>1315##3227</four>
<unité politique>4727</unité politique>
<mirage>2375##3374##5106</mirage>
<marxisme>612</marxisme>
<sécurité>323##331##334##340##344##345##543##1080##1156##1602##1726##2080##2095##2113##2216##2226##2397##2432##3521##3522##3528##3530##3715##3717##3999##4322</sécurité>
<grenier>233</grenier>
<sonder>4571</sonder>
<faune>3815##3817</faune>
<devenir>25##138##181##192##192##203##267##419##510##546##575##623##1099##1110##1135##1147##1166##1275##1324##1325##1356##1360##1605##1629##1633##1662##1676##1677##1678##1747##1761##1799##1837##2006##2104##2113##2127##2149##2150##2287##2339##2469##2550##2585##2833##2875##3059##3071##3095##3154##3156##3164##3195##3365##3535##3617##3624##3712##3773##3775##3869##3918##3920##4042##4147##4519##4523##4653##4819##4877##4937##4993##5037##5313##5316##5346</devenir>
<Oupia>3223</Oupia>
<célébration>2988</célébration>

Les nombres entre les balises correspondent aux numéros de phrases dans laquelle le mot situé entre <> apparait dans le texte.
Donc par exemple : <rêve américain>787##3592</rêve américain>
le mot rêve américain apparait à la phrase numéro 787 et 3592.

Ce que je dois réaliser maintenant, c'est comparer chaque mot un à un.
Par ex :
"trêve des confiseurs avec rêve américain". Donc pour cela je récupére la chaine qui se trouve entre leur balise.
"1872" pour trêve des confiseurs
et "787##1872" pour rêves américains.

là je fais un split(##) pour avoir une liste de numéross

Je dois ensuite utiliser la formule de dice
f = 2*X/(A+B)
avec X = nombre de fois que les deux mots apparaissent ensemble dans le corpus
A = nombre de fois qu'apparait le mot A dans tous le corpus
B = nombre de fois qu'apparait le mot B dans tous le corpus

ICI X = l'intersection des deux listes et donc 1 (valeur commune: 1872)
A = longueur de la liste du mot treve des confiseurs (valeur : 1)
B = longueur de la liste du mot reve américain (valeur 2)
Dice = 2*1/(1+2)

ensuite je met un filtre sur Dice, par ex si 0.0<Dice<1.0, je met dans une dictionnaire temporaire le mot reves americains. (clé = le mot, valeur = dice)

après que j'ai comparé treves de confiseur avec tous les autres mots.

je trie le dico par valeur de dice (décroissante) et je récupérer les m meilleurs mots

j'écris dans un fichier la liste temporaire

<treves de confiseur>reves américains,etc.....</treves de confiseurs>

et ainsi de suite, je compare reves americains avec tous les autres mots du texte .........

<treves de confiseur>reves américains,etc.....</treves de confiseurs> ça veut dire que reves américains apparait souvent avec treves de confiseur, on appelle ça des cooccurrents.

PC Perso :
Ram : 3Go
CPU : Intel Core 2 DUo 2,4 Ghz

donc j'espère que c'est un peu plus clair

**ekremyilmaz** · 29/11/2008, 19h10

juste pour indication,
il y a 44277 mots (donc de lignes)

**eyquem** · 29/11/2008, 20h08

Beaucoup plus clair ! Et ça parait plus simple que je croyais; c'est dommage, ça va être moins amusant de s'occuper de ton code....

Un tuyau: on peut ouvrir plusieurs fois un même fichier (comme tu l'as fait, toi deux fois) et le parcourir avec des pointeurs indépendants. J'avais lu ça dans un message de ce bon vieux forum.
Pour voir ce que ça veut dire, fais tourner ce qui suit.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
f = open('mat1.log','r')
fg = open('mat1.log','r')
rdf = 'go'
while rdf:
    rdf = f.readline()
    print rdf[:-1]
    pf = f.tell()
    fg.seek(pf)
    rdfg = 'go'
    while rdfg:
        rdfg = fg.readline()
        print 'ligne de fg: '+rdfg[:-1]
f.close()
fg.close()

Un conseil au passage: évite d'appeler deux fichier f et fg. Ces deux noms sont trop proches, cela peut entrainer facilement une erreur sans s'en apercevoir; il suffit de vouloir taper fg et d'oublier le g pour mettre une panique de deux heures dans un code.

**alexdevl** · 29/11/2008, 20h24

Bonjour,
Je propose une méthode qui est couteuse en mémoire mais qui ne nécessite (je pense) qu'une seule passe :
Remplir un dico et faire le traitement à partir du dico..

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
 
#!/usr/bin/env python
# -*- coding: iso-8859-1 -*-
 
'''
<motA>1##2##3##4</motA>
<motB>1##4##8</motB>
<motC>5##8##10</motC>
<motD>35##32##10</motD>
<motE>1##2##3##4</motE
'''
 
fo=open("mat1.log","r")
numPhrases={}
motParPhrase={}
 
# type de ligne <motA>1##2##3##4</motA>
for ligne in fo:
    mot=ligne[1:].split(">",1)[0]
    numPhraseSplit=ligne.split(">",1)[1].split("<")[0].split("##")
    for numPhrase in numPhraseSplit:
        if numPhrase not in numPhrases.keys(): numPhrases[numPhrase]=[]
        numPhrases[numPhrase].append(mot) # Dico par num de phrases
    motParPhrase[mot]=numPhraseSplit # Dico par mot
print numPhrases
print motParPhrase
 
# Création d'un dico du type :
# numPhrases={'10': ['motC', 'motD'], '32': ['motD'], '35': ['motD'], '1': ['motA', 'motB', 'motE']...
# motParPhrase={'motA': ['1', '2', '3', '4'], 'motB': ['1', '4', '8'],

**eyquem** · 29/11/2008, 20h39

Mon message précédent n'est pas une bonne piste.
En lisant le fichier avec deux pointeurs différents, on peut y arriver bien sûr, mais cela voudrait dire qu'on ferait sur chaque ligne L une répétition d'instructions pour chacune des lignes [0,L] qui la précède, avec recherche du mot à chaque fois, etc.... le nombre de répétitions étant d'autant plus élévé que la ligne L serait loin dans le fichier.

Il faut faire comme l'a déjà conseillé oiffrig: un premier passage dans le fichier pour créer une liste de listes. Cette liste devrait ne pas être trop grande par rapport à ta RAM, 44277 lignes ce n'est pas grand chose.
Si vraiment cette liste se révélait comme trop grande pour rester en RAM, on pourrait toujours l'écrire dans un fichier puis faire le traitement en lisant ce fichier progressivement.

Mais je crois que l'essentiel n'est pas là. Il va y avoir des calculs qui se répètent, il faut donc réfléchir mathématiquement au problème pour que l'algorithme soit astucieux et évite au programme la répétition de ces calculs. À mon avis. Je vais réfléchir à ça, le problème m'intéresse, mais là je n'ai plus trop le temps.

**eyquem** · 29/11/2008, 20h43

Je pense qu'il faut essayer d'éviter de recourir à des dictionnaires. Je pense qu'à partir d'une liste de listes , il sera possible d'employer des list comprehension qui sont extrêmement rapides.
Il faut réfléchir à l'algorithme.