Algo sur liste

Version imprimable

01/02/2013, 16h21
shadow19c

Algo sur liste

Bonjour,
j'ai un petit soucis d'algo sur la comparaison de deux listes, vous allez me dire c'est simple mais voila, je travail sur des gros fichier >1 GB

J'ai deux fichiers qui contiennent des coordonnees:

position ratio
1 0
3 0.6
4 0.3

position ratio
1 0.3
2 1
5 0
L’idée serait que je parcours les deux fichiers, et je compare position par position par exemple la position 1 en faisant ratio1-ratio2 (0-0.3), mon premier problème et comment gérer les positions qui n'existent pas

Deuxième soucis, je voudrais faire la médiane sur des fenêtres de 100.
Donc découper mes positions en range de 100.

Donc j'avais penser a faire la maniére brute, mettre dans deux listes et puis les découper en fenêtres de 100, mais j'ai peur pour saturer la mémoire ?

Est ce que vous pouvez m'aider sur ce sujet la?

Merci

Bonjour,
Je propose le programme suivant,
nom_f1 et nom_f2 sont les noms des fichiers d'entrée.
nom_fs est le nom du fichier résultat

Pour essayer ce programme j'ai fait une fonction ''cre_files'' avec en paramètres la taille en Mo des fichiers.

Alex

Code:

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
 
import random
 
 
def cre_files(nmega,nom_f1,nom_f2):
    """ Creation des fichiers d'essai, le parametre est la taille en mega Octet"""
    nlignes=nmega*15
    with open(nom_f1,"w") as fo1:
        fo1.write("")
        i=1
    for n1 in range(nlignes):
        a=""
        for n2 in range(10000):
            if random.randint(0,10)<7:
                a+=str(i)+" "+str(random.randint(0,10)/10.0)+"\n"
            i+=1
        with open(nom_f1,"a") as fo1:
            fo1.write(a)
    print"fin1"
 
    with open(nom_f2,"w") as fo1:
        fo1.write("")
        i=1
    for n1 in range(nlignes):
        a=""
        for n2 in range(10000):
            if random.randint(0,10)<7:
                a+=str(i)+" "+str(random.randint(0,10)/10.0)+"\n"
            i+=1
        with open(nom_f2,"a") as fo1:
            fo1.write(a)
    print"fin2"
 
 
def cre_bilan(nom_f1,nom_f2,nom_fs):
    with open(nom_f1,"r") as f1,open(nom_f2,"r") as f2,open(nom_fs,"w") as fs:
        ligne_f2=f2.readline()
        num_l2=int(ligne_f2.split(" ")[0])
        for ligne_f1 in f1: # Parcour du fichier f1.txt
                num_l1=int(ligne_f1.split(" ")[0])
                while num_l1>=num_l2 and ligne_f2!="" :
                    if num_l2==num_l1: # Si egal rajout au fichier de sortie
                        fs.write(str(num_l2)+" "+str(float(ligne_f1.split(" ")[1])-float(ligne_f2.split(" ")[1]))+"\n")                
                    ligne_f2=f2.readline()
                    if ligne_f2!="":    # Si la fin du fichier f2 n'est pas atteinte
                        num_l2=int(ligne_f2.split(" ")[0])
 
    print "fin bilan"
 
nom_f1="f1.txt"
nom_f2="f2.txt"
cre_files(1,nom_f1,nom_f2) # 1=taille en Mo du fichier d'essai
 
nom_fs="fs.txt"
cre_bilan(nom_f1,nom_f2,nom_fs)

Voici l'algo :

Code:

1
2
3
4
5
6
 
Pour chaque ligne de f1
    Tant que numéro de ligne de f1 >= numéro de ligne de f2
        si numéro de ligne de f1 = numéro de ligne de f2
            Traitement
        Lecture de la ligne suivante de f2

Citation:

Envoyé par shadow19c

mon premier problème et comment gérer les positions qui n'existent pas

Bonjour
Ce problème est traité avec une technique connue sous le nom "d'appareillage". Mais elle ne fonctionne que si les fichiers sont triés

L'algo est simple
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 flag f1=True flag f2=True tant que faire si flag f1 alors lire ligne fichier 1 si fin fichier 1 sortie sinon mettre flag f1 à faux fin si si flag f2 alors lire ligne fichier 2 si fin fichier2 sortie sinon mettre flag f2 à faux fin si si info1 = info2 alors faire ton travail si info1 <= info2 alors mettre flag f1 à vrai si info2 <= info1 alors mettre flag f2 à vrai fin faire
De cette façon, tant que l'une des deux infos est plus petite que l'autre, le fichier en question continue à être lu/traité jusqu'à ce que son info atteigne puis dépasse celle de l'autre. Ensuite c'est l'autre qui est alors lu/traité...

04/02/2013, 10h58
shadow19c

Bonjour,
merci pour tous vos messages.
Jai retenu vos deux algos (Sve@r et alexdevl ), par contre je voulais savoir pour faire les fenetres glissantes de 100, est ce que vous pensez que ca serait mieux deque ?

Par ce que l'idée est d'ensuite faire des fentres de 100, et calculer la mediane...

Merci
04/02/2013, 21h01
Sve@r

Citation:

Envoyé par shadow19c

Bonjour,
merci pour tous vos messages.
Jai retenu vos deux algos (Sve@r et alexdevl ), par contre je voulais savoir pour faire les fenetres glissantes de 100, est ce que vous pensez que ca serait mieux deque ?

Par ce que l'idée est d'ensuite faire des fentres de 100, et calculer la mediane...

Merci

Bah je pense qu'avec l'appareillage, quand info1 = info2 tu remplis ton tableau et dès que ton tableau atteint 100, tu calcules la médiane puis tu le remets à 0 (gaffe toutefois quand tu sors du tant que car le tableau aura été partiellement rempli...)

Bonjour,

Voici avec la création d'un fichier de moyennes toute les 100 valeurs

Alex

Code:

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
69
70
71
72
 
#!/usr/bin/env python
#coding=utf-8
 
import random
 
def cre_files(nmega,nom_f1,nom_f2):
    """ Création des fichiers d'essai, le paramètre est la taille en mega Octet"""
    nlignes=nmega*15
    with open(nom_f1,"w") as fo1:
        fo1.write("")
        i=1
    for n1 in range(nlignes):
        a=""
        for n2 in range(10000):
            if random.randint(0,10)<7:
                a+=str(i)+" "+str(random.randint(0,10)/10.0)+"\n"
            i+=1
        with open(nom_f1,"a") as fo1:
            fo1.write(a)
    print"fin1"
 
    with open(nom_f2,"w") as fo1:
        fo1.write("")
        i=1
    for n1 in range(nlignes):
        a=""
        for n2 in range(10000):
            if random.randint(0,10)<7:
                a+=str(i)+" "+str(random.randint(0,10)/10.0)+"\n"
            i+=1
        with open(nom_f2,"a") as fo1:
            fo1.write(a)
    print"fin2"
 
 
def cre_bilan(nom_f1,nom_f2,nom_fs,nom_fm):
    """ Création du bilan
    nom_f1,nom_f2 : fichiers d'entrée
    nom_fs : fichier de sortie, calcul f1-f2 si num ligne f1 num ligne f2
    nom_fm : fichier de sortie, médianes sur 100 valeurs de fs
    """
    with open(nom_f1,"r") as f1,open(nom_f2,"r") as f2,\
                                open(nom_fs,"w") as fs,open(nom_fm,"w") as fm:
        ligne_f2=f2.readline()
        num_l2=int(ligne_f2.split(" ")[0])
        valeurs_med=[]
        for ligne_f1 in f1: # Parcour du fichier f1
                num_l1=int(ligne_f1.split(" ")[0])
                while num_l1>=num_l2 and ligne_f2!="" : # Parcours de f2
                    if num_l2==num_l1: # Si égalite
                        difference=float(ligne_f1.split(" ")[1])-float(ligne_f2.split(" ")[1])                    
                        # rajout au fichier de sortie
                        fs.write(str(num_l2)+" "+str(difference)+"\n")
                        # Traitement des médianes             
                        valeurs_med.append(difference)
                        if len(valeurs_med)==100 :
                            fm.write(str(sum(valeurs_med)/100)+"\n")
                            valeurs_med=[]
                    ligne_f2=f2.readline()
                    if ligne_f2!="":    # Si la fin du fichier f2 n'est pas atteinte
                        num_l2=int(ligne_f2.split(" ")[0])
 
    print "fin bilan"
 
nom_f1="f1.txt"
nom_f2="f2.txt"
cre_files(1,nom_f1,nom_f2) # 1=taille en Mo du fichier d'essai
 
nom_fs="fs.txt"
nom_fm="fm.txt"
cre_bilan(nom_f1,nom_f2,nom_fs,nom_fm)

Bonjour,
merci pour vos reponses,
par contre j'ai une erreur, car je veux pas regrouper les valeurs en fenetre de 100 mais ce sont les positions qui sont dans la premiere colonne:

Par exemple avec deux fichiers:
34 -0.625
80 0.5
86 1
93 1
108 0.666667
115 0.666667
123 0.75
139 -0.333333
150 -0.333333
161 0.6
170 -0.625
176 -0.875
177 0.0769231

Deuxieme fichier
34 -0.354839
80 -0.140351
86 0.25
93 0
94 0
100 0
101 0
102 0.142857
107 0.0769231
108 0.615385

Je voudrais si je pars avec une fenetre de 10, calculer la mediane:
si je prends le premier fichier et le deuxieme il ya deux positions identiques 34 donc je veux faire la mediane que sur 34 car entre 30 et 40 ya que celui la ensuite il ya 80 et 86 donc mediane (0.5,1 ) d'un coté et de l'autre deuxieme fichier mediane (-0.140351,0.25)

Voici mon code j'avais pense a faire des tuples pour garder les positions:

Code:

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
#!/usr/bin/python
# -*- coding: utf-8 -*-
 
###########
# IMPORTS #
###########
import os.path
import sys
from os import getcwd
import getopt
#import config
 
 
'''def cre_files(nmega,nom_f1,nom_f2):
    """ Creation des fichiers d'essai, le parametre est la taille en mega Octet"""
    nlignes=nmega*15
    with open(nom_f1,"w") as fo1:
        fo1.write("")
        i=1
    for n1 in range(nlignes):
        a=""
        for n2 in range(10000):
            if random.randint(0,10)<7:
                a+=str(i)+" "+str(random.randint(0,10)/10.0)+"\n"
            i+=1
        with open(nom_f1,"a") as fo1:
            fo1.write(a)
    print"fin1"
 
    with open(nom_f2,"w") as fo1:
        fo1.write("")
        i=1
    for n1 in range(nlignes):
        a=""
        for n2 in range(10000):
            if random.randint(0,10)<7:
                a+=str(i)+" "+str(random.randint(0,10)/10.0)+"\n"
            i+=1
        with open(nom_f2,"a") as fo1:
            fo1.write(a)
    print"fin2"'''
 
 
def mediane(L):
    L.sort()
    N = len(L)
    n = N/2.0
    p = int(n)
    if n == p:
        return (L[p-1]+L[p])/2.0
    else:
        return L[p]
 
def moyenne(table1):
    return sum(table1, 0.0) / len(table1)
 
 
 
def variance(table):
    m=moyenne(table)
    return moyenne([(x-m)**2 for x in table])
 
 
 
def ecartype(tablea):
    return variance(tablea)**0.5
 
 
 
 
def cre_bilan(nom_f1,nom_f2,nom_fs):
    with open(nom_f1,"r") as f1,open(nom_f2,"r") as f2,open(nom_fs,"w") as fs:
 
        ligne_f2=f2.readline()
        num_l2=int(ligne_f2.split("\t")[0])
        for ligne_f1 in f1: # Parcour du fichier f1.txt
                num_l1=int(ligne_f1.split("\t")[0])
                while num_l1>=num_l2 and ligne_f2!="" :
                    if num_l2==num_l1: # Si egal rajout au fichier de sortie
                        #print str(num_l1)+"\t"+str(float(ligne_f2.split("\t")[1])) +"\t"+str(ligne_f1.split("\t")[2])
                        #tableau_colot=[][]
                        #tableau_jack=[]
                        endPositionGenomic=177
                        startWindows=0
                        endWindows=1
                        lenWindows=20 #lenWindows est la taille de ta fenetre dans notre cas 20
                        ok=()
                        while endWindows <  endPositionGenomic :
                            startWindows=endWindows
                            ok=((ligne_f1.split("\t")[0]),float(ligne_f1.split("\t")[1]),(ligne_f2.split("\t")[1]))
                            endWindows+=lenWindows
                            print str(mediane(ok[1]))
 
 
                    ligne_f2=f2.readline()
 
                    if ligne_f2!="":    # Si la fin du fichier f2 n'est pas atteinte
                        num_l2=int(ligne_f2.split("\t")[0])
 
    #print "fin bilan"
 
nom_f1="test1"
nom_f2="test2"
 
 
nom_fs="fs.txt"
cre_bilan(nom_f1,nom_f2,nom_fs)