optimiser une recherche dans des dictionnaires

Version imprimable

Bonjour,

Je dispose d'un (grand) tableau de valeur dont voici un exemple simple :
#test
1 A id1 6 20
2 A id2 7 0
3 B id3 89 76
4 B id4 9 9

Dans un autre fichier, j'ai les informations suivantes
tr1 A 8 12
tr2 A 5 2
tr3 B 78 85

Mon but est d'associer les informations d'associer les identifiants 'tr' du second fichier aux 'id' du premier fichier si les bornes des tr sont comprises dans celles des id. Par exemple : tr1 id1 A 1
(8 et 12 compris entre 6 et 20)
J'ai écris ce script qui fonctionne et me donne le résultat attendu:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import sys f1 = open(sys.argv[1], 'r') df1 = {} for line in f1: if line.startswith("#"): continue tmp = line.replace('\n', '').split('\t') df1[tmp[2]] = [tmp[0], tmp[1], int(tmp[3]), int(tmp[4])] f2 = open(sys.argv[2], 'r') for line in f2: tmp = line.split('\t') for i in df1: if df1[i][1]==tmp[1] and int(tmp[2]) in range(df1[i][2],df1[i][3]) and int(tmp[3]) in range(df1[i][2],df1[i][3]): print tmp[0],'\t',i,'\t',df1[i][0],’\t’,df1[i][2]
Le problème est que les fichiers d'entrée contiennent des centaines de milliers de lignes et l'exécution prends des jours.
L'idée pour aller plus vite était de créer plusieurs dictionnaires en lieu et place de df1 et de tester la présence du A ou du B :
df1_1{id1:[1,A,6,20];id2:[2,A,7,0]}
df1_2{id3:[3,B,89,76];id4:[4,B,9,9]}

Mon problème est que je n'arrive pas à créer 'automatiquement' ces petits dictionnaires, pourriez-vous m'aider ?

J'espère que j'ai été assez clair, si ce n'est pas le cas, j'essaierais de clarifier au mieux la situation,

Merci d'avance

Salut,

Ce que j'en comprends c'est que vous devriez avoir un dictionnaire avec les clefs 'A', 'B',... et une liste d'intervalles comme valeurs.
Cela éviterait déjà de balayer toutes les entrées du premier dictionnaire pour y filtrer les "lignes".

Ensuite, il faudrait "optimiser" un peu(*)
Lorsque vous écrivez:
Code:

1 2 3 for i in df1: if df1[i][1]==tmp[1] and int(tmp[2]) in range(df1[i][2],df1[i][3]) and int(tmp[3]) in range(df1[i][2],df1[i][3]): print tmp[0],'\t',i,'\t',df1[i][0],’\t’,df1[i][2]
à chaque itération vous fabriquez int(tmp[2]) et int(tmp[3]): écrire
Code:

1 2 a = int(tmp[2]) b = int(tmp[3])
une seule fois avant d'entrer dans la boucle c'est quand même moins lourd...

Enfin lorsque vous écrivez un truc comme "a in range(10)", Python2 va fabriquer la liste des nombre de 0 à 9 et faire une boucle pour comparer a à 0 puis à 1, ....
Ecrire "0 <= a < 10" ne fera que deux comparaisons.

(*) Il y a probablement des bibliothèque numérique qui savent vectoriser cela.

- W

Citation:
Envoyé par wiztricks
Salut,
Bonsoir et merci de votre réponse

Ce que j'en comprends c'est que vous devriez avoir un dictionnaire avec les clefs 'A', 'B',... et une liste d'intervalles comme valeurs.
Cela éviterait déjà de balayer toutes les entrées du premier dictionnaire pour y filtrer les "lignes".

Effectivement un dictionnaire avec A et B comme clefs irait plus vite, si je comprends bien on aurait : df {A: [1, id1, 6, 20],[2, id2, 7, 0]; B: [3, id3, 89, 76], [4, id4,9,9]} ?

Ensuite, il faudrait "optimiser" un peu(*)
Lorsque vous écrivez:
Code:

1 2 3 for i in df1: if df1[i][1]==tmp[1] and int(tmp[2]) in range(df1[i][2],df1[i][3]) and int(tmp[3]) in range(df1[i][2],df1[i][3]): print tmp[0],'\t',i,'\t',df1[i][0],’\t’,df1[i][2]
à chaque itération vous fabriquez int(tmp[2]) et int(tmp[3]): écrire
Code:

1 2 a = int(tmp[2]) b = int(tmp[3])
une seule fois avant d'entrer dans la boucle c'est quand même moins lourd...

Enfin lorsque vous écrivez un truc comme "a in range(10)", Python2 va fabriquer la liste des nombre de 0 à 9 et faire une boucle pour comparer a à 0 puis à 1, ....
Ecrire "0 <= a < 10" ne fera que deux comparaisons.

Merci pour l'information, par contre, cela va impliquer de rajouter 2 conditions car a > b ou a < b et réciproquement pour la référence
Code:

1 2 if a > df1[i][2] and b < df1[i][3] elif a<df1[i][3] and b > df1[i][2]
cela reste t'il meilleur que le range ?

(*) Il y a probablement des bibliothèque numérique qui savent vectoriser cela.

Encore merci

- W

Peut-être qqch comme ça:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 df1 = {} for line in f1: if line.startswith("#"): continue num, cat, id_, a, b = line.split('\t') foo = a a = int(a) b = int(b) if a > b: a,b = b,a df1.setdefault(cat,[]).append((num, id_, a, b, foo)) for line in f2: tr, cat, c, d = line.split('\t') c = int(c) d = int(d) if c > d: c,d = d,c for num, id_, a, b, foo in df1.get(cat,()): if a <= c and d <= b: print '\t'.join((tr,id_,num,foo))
Les noms de variables c'est n'importe quoi car je ne connais pas la sémantique de tes colonnes, mais tu renommeras...
J'ai pris la liberté de réordonner les bornes, et de considérer la borne supérieur comme inclusive, donc le résultat n'est pas identique à ton code, mais tu adapteras si nécessaire...

Il y a moyen d'améliorer encore, mais ça devrait déjà sérieusement accélérer le traitement.

02/09/2016, 22h27
BufferBob

salut,

Citation:

Envoyé par lup17

Le problème est que les fichiers d'entrée contiennent des centaines de milliers de lignes et l'exécution prends des jours.

si l'exécution prend plusieurs jours, m'est avis qu'il va falloir penser différemment, envisager de distribuer les opérations sur plusieurs thread éventuellement, et avant tout ça identifier ce qui crée la lenteur, savoir si c'est le processeur qui est sous-utilisé, le disque qui ne sert pas les données assez vite ou autre, ça m'étonnerait que 2/3 astuces de grand-mère suffisent à ramener le traitement dans des temps raisonnables malheureusement

disposer d'un échantillon des données de quelques dizaines/centaines de milliers de lignes, avec un timing de référence par exemple, nous permettrait sans doute de tester différentes approches

nb: je n'ai rien contre les grand-mères ou leurs astuces ! ^^'
04/09/2016, 02h56
JacekB

range vs xrange

Pour commencer, le plus simple serait déjà de remplacer tous les range par des xrange, beaucoup moins gourmands en ressource.
05/09/2016, 09h40
lup17

Bonjour,

Merci pour vos réponses, elle m'ont permis d'accélérer l'exécution du script. Malheureusement, il est toujours très long, le goulot d'étranglement est encore l'iteration dans le dictionnaire, je pense que le recours au multithreading pourrait être une solution. Est-ce facile à mettre en place ?

Merci
05/09/2016, 09h53
wiztricks

Citation:

Envoyé par lup17

Merci pour vos réponses, elle m'ont permis d'accélérer l'exécution du script. Malheureusement, il est toujours très long, le goulot d'étranglement est encore l'iteration dans le dictionnaire, je pense que le recours au multithreading pourrait être une solution. Est-ce facile à mettre en place ?

Le multithreading ne vous apportera pas grand chose car il ne permettra pas de faire travailler plus de CPU. Il vous faut passer par plusieurs process et jeter un œil à concurrent.futures (qui est par défaut dans Python3 mais qui s'installe sur Python2.7) pour que ce soit plus facile.
Mais vous pouvez découper le fichier "f2" en plusieurs morceaux et lancer plusieurs process en parallèle pour traiter chaque fichier (avec subprocess): techniquement c'est la même chose mais c'est peut être plus à votre portée.
note: vous pouvez aussi éviter de recréer le dictionnaire f1 à chaque fois en récupérant une copie construite par pickle.

- W
05/09/2016, 17h45
dividee

Citation:

Envoyé par lup17

Bonjour,

Merci pour vos réponses, elle m'ont permis d'accélérer l'exécution du script. Malheureusement, il est toujours très long, le goulot d'étranglement est encore l'iteration dans le dictionnaire, je pense que le recours au multithreading pourrait être une solution. Est-ce facile à mettre en place ?

Merci

Dans le bout de code que j'ai posté plus haut, il n'y a pas d'itération sur un dictionnaire.

C'était d'ailleurs le principal problème de ton code initial et de le façon dont tu voulais organiser le dictionnaire: si tu utilises un dictionnaire pour accélérer les traitements, il faut l'organiser de façon à pouvoir faire une recherche dans celui-ci, pas itérer dessus. Itérer sur un dictionnaire n'est pas plus efficace que d'itérer sur une liste.

Peux-tu poster ton code actuel, qu'on voie à quoi ça ressemble ? Ce qui aiderait aussi, c'est des informations sur tes données. On sait qu'il y a des centaines de milliers de lignes dans chaque fichier, mais est-ce que les bornes de tes intervalles sont toujours aussi petites ? Combien y a-t-il de valeurs distinctes possibles pour chaque colonne ?

Le code que j'avais posté sera par exemple très efficace si le nombre de valeurs possibles dans la seconde colonne de chaque fichier est élevé, mais nettement moins si ce nombre est faible.

2 pièce(s) jointe(s)

Bonjour,

En effet, j'avais fait une erreur dans la boucle en intégrant votre suggestion. Une fois celle-ci, corrigée, le script va beaucoup plus vite.

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
import sys
 
f1 = open(sys.argv[1], 'r')
 
fannot = open('annot2.txt', 'w')
df1 = {}
for line in f1:
    if line.startswith('#'): continue
    tmp = line.replace('\n', '').split('\t')
    # print tmp[8].split(';')
    ch, feat, a, b = tmp[0], tmp[2], int(tmp[3]), int(tmp[4])
    id = ''
    pacid = ''
    name = ''
    parent = ''
    for i in tmp[8].split(';'):
        if 'ID' in i:
            id = i[3:]
        if 'pacid' in i:
            pacid = i[6:]
        if 'Name' in i:
            name = i[5:]
        if 'Parent' in i:
            parent = i[7:]
    df1.setdefault(ch,[]).append((id, feat, a, b, pacid, name, parent))
 
 
f2=open(sys.argv[2],'r')
for line in f2:
    tmp = line.split('\t')
    tr, ch, c, d = tmp[0], tmp[1], int(tmp[8]), int(tmp[9])
    for id, feat, a, b, pacid, name, parent in df1.get(ch,()):
        if a >= c and b <= d or a <= d and b >= d:
            print '\t'.join((tr,id,feat,pacid,name,parent))
            fannot.write('\t'.join((tr,id,feat,pacid,name,parent)))

En PJ, des exemples des fichiers d'entrée.

Merci encore de votre aide !

06/09/2016, 08h12
BufferBob

salut,

Citation:

Envoyé par lup17

(...) le script va beaucoup plus vite.

c'est un gain de quel ordre "beaucoup" ? ^^

Citation:

En PJ, des exemples des fichiers d'entrée.

c'est pas avec ces quelques lignes qu'on peut bench

par ailleurs l'exécution du dernier script que tu donnes à l'encontre des fichiers de test ne sort aucune donnée, le fichier annot2.txt est vide.
06/09/2016, 08h19
lup17

Citation:

Envoyé par BufferBob

salut,

c'est un gain de quel ordre "beaucoup" ? ^^

Citation:

on passe de plusieurs jours à moins d'1h

c'est pas avec ces quelques lignes qu'on peut bench

par ailleurs l'exécution du dernier script que tu donnes à l'encontre des fichiers de test ne sort aucune donnée, le fichier annot2.txt est vide.

Citation:

je sais, le but était juste de montrer la structure du fichier pour répondre aux questions de Dividee