Position dans une liste hétérogène

Version imprimable

Bonjour,
sous python 2.5, je dois créer une fonction qui, à partir d'une liste de listes, doit renvoyer l'indice de la sous-liste contenant un certain élément.

Ex.:
dans
tab=[[4229.0], [4099.0, 4100.0], [7861.0], [9896.0], [4505.0, 9948.0, 9956.0], [3729.0, 8473.0]]
(tab, non triée, peut contenir + d'1 million de sous-listes triées de longueurs diverses)
pour l'élément
nb=9948.0
ma fonction doit renvoyer
position=4

Ma première idée est:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def position(tab,nb): position=[] for k in tab: i=0 end=False while not end and i<len(tab[k]): end=nb in tab[k][i] i+=1 if end: position.append(i-1) else: position.append('') return position
Mais c'est très très lent, et ça semble saturer pour un grand nombre de listes.

Avez-vous d'autres idées?
J'essaie de trouver une solution avec bisect qui est rapide, mais nécessite un tri préalable.
http://mail.python.org/pipermail/pyt...ne/266184.html
Merci.

23/04/2009, 12h57
kango

bonjour,

travailler avec des listes aussi longues, surtout lorsque l'on a besoin d'aller rechercher un indice ça peut être extrêmement lent.

es tu contraint d'utiliser des listes de listes comme structure de données ou est ce que tu as la latitude d'organiser tes données comme tu le souhaites ?
23/04/2009, 13h08
eyquem
Ce n'est pas très très lent: ça ne tourne pas.
Si tu écris for k in tab: , k est une sous-liste de tab et écrire plus loin tab[k] ne veut rien dire.
La longueur de tab, c'est simplement len(tab)

Ton code est impossible à corriger car il y a un vice algorithmique:
il y a deux boucles en réalité:

Code:

for k in tab:

et
Code:

1 2 3 while not end and i<len(tab): .... i += 1
Or il n'en faut qu'une.

Je te laisse réfléchir, mais l'instruction break te facilitera grandement la vie.
Code:

1 2 3 4 5 6 7 8 i = 0 while i<200: if i==55: print i break i += 1 # Ce code est bête comme chou, il ne sert à rien d'autre # qu'à faire sentir à quoi sert break

En effet eyquem, comme je n'ai pas été clair, on peut penser à une erreur.
Mais tab est un dictionnaire, donc k in tab appelle une à une ses clés.
Pour reprendre l'ex.:

dans:
tab[k]=[[4229.0], [4099.0, 4100.0], [7861.0], [9896.0], [4505.0, 9948.0, 9956.0], [3729.0, 8473.0]]
(tab[k], liste non triée à la clé k du dictionnaire tab, peut contenir + d'1 million de sous-listes triées tab[k][i] de longueurs diverses)
pour l'élément
nb=9948.0
ma fonction doit renvoyer
position=4

Pensez-vous qu'un break optimise le code ici ?

Kango, à quelle autre structure penses-tu ? array, liste de tuples , ...?

J'ai réécrit ma fonction, mais c'est le même principe, tjs lent :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 def position(id_tab,pur_nb): position=[] for k in id_tab: i=0 while i<len(id_tab[k]) and not pur_nb in id_tab[k][i]: i+=1 if i==len(id_tab[k]): position.append('') else: position.append(i) return position

Ah ! j'aurais dû y penser ! L'idée que c'était bizarre que tu fasses une erreur pareille et présente un code qui ne tourne pas m'a bien effleuré un instant, mais je ne m'y suis pas arrèté. Désolé.

En y pensant après coup, je me suis dit que le conseil de break n'était pas très bon.
J'ai parlé de break avec l'idée que ça allait te permettre de simplifier ton premier code en évitant l'usage de ce end qui me paraissait gripper un peu le code. mais c'était t'indiquer un moyen de simplifier un code mal conçu, donc un mauvais conseil.

Mais tu as vu qu'il fallait éliminer cet emploi de end. Ton deuxième code est donc mieux.
- Mais à mon avis la condition dans le while a des défauts.
Par exemple, à chaque fois que le programm va devoir évaluer

Code:

not pur_nb in id_tab[k][i]

, il va devoir re-chercher la liste k dans id_tab pour en examiner la sous-liste i. Cette re-recherche de id_tab[k] pour chaque i à examiner, c'est du boulot !
Il vaut mieux procéder avec un alias:
lik = id_tab[k]
De même pour len(id-tab[k]) ,tu obliges ton programme à recalculer cette valeur à chaque fois. Il vaut mieux créer un alias lenk = len(id-tab[k])

Code:

while i<lenk and not pur_nb in lik:

J'ai lu je ne sais où que l'utilisation d'alias accélère les programmes.
J'aimerais avoir confirmation de la part de quelqu'un de plus calé que moi, mais je crois que c'est bien comme ça. J'ai la flemme de faire une étude comparative de vitesses.

Mais ce n'est pas tout.
- Il y a un problème d'algorithme à mon avis. Avec ton code , tu places une valeur '' dans la variable position pour chaque sous-liste de id_tab[k] qui ne contient pas ce qu'on cherche. Je ne crois pas que ce soit ce que tu veux vraiment.

- De plus, id_tab étant un dictionnaire,
for k in id_tab: fait venir les éléments de id_tab dans un ordre quelconque: un dictionnaire n'est pas ordonné. Les valeurs que tu vas lire dans position seront donc dans un ordre hasardeux et tu ne sauras pas établir la correspondance avec les listes id_tab[k] ou les sous-listes de id_tab[k].
Personnellement je ferais de position un dictionnaire et j'utiliserais l'instruction # position[k] = rec

- Enfin tu utilises un indice i que tu incrémentes spécialement avec une instruction et la nécessité de tester sa valeur dans la condition du while. Les instructions for sont là pour éviter cela, j'ai donc cherché une solution avec un i qui stoppe tout seul au bout de l'intervalle dans lequel on l'autorise à courir.

J'ai eu un peu de mal à trouverla solution suivante. C'est la première fois que j'utilise la propriété de typage dynamique:
rec est soit une chaine vide soit un indice numérique.
Remarque aussi que j'utilise un alias lik
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 li1 = [['4229.0'], ['4099.0', '4100.0'], ['7861.0'], ['9896.0'], ['4505.0', '9948.0', '9956.0'], ['3729.0', '8473.0'], ['1673.09','5678.098','345.84','98.4476'],['233,56.789','8912.3','897.90'],['8796.78','0.876'],['874553.90'], ['3452.8754','98342.86451','98.8306'],['647.98'',0.785','987.102'],['784.9'], ['76453.9084','895364','98333.90554','98331.23','46653.7766','5.66788','66.7744','3344.5544','54'], ['784555','3833.94','344.23','4556.980','123.42'],['87533.871','8273654.809','6666.77','9344.89']] li2 = [['987.902','2665.12','234.876'],['78663.8234','12.308','4436.902','0.763'], ['647.902','988363.90'],['8643']] li3 = [['7200.80','23.4'],['632.9011'],['6534.98','23.0664','6666.77'],['72.34','120.2','34','18772.32']] tab = {'k1':li1,'k2':li2,'k3':li3} def position(id_tab,pur_nb): position=[] for k in id_tab: lik = id_tab[k] rec = '' for i in xrange(len(id_tab[k])): if pur_nb in lik[i]: rec = i break position.append(rec) # position[k] = rec return position print position(tab,'6666.77')
Il faudrait faire une comparaison de vitesse de ton dernier code avec celui-ci, pour vérifier mes assertions.

EDIT:
changé la place de rec = '', je l'ai sortie de la boucle for i in xrange(len(id_tab[k])):
pour éviter de l'exécuter pour chaque i

j'ai un peu modifié ton code pour utiliser enumerate qui est plus conseillé

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def position(id_tab,pur_nb):
    position=[]
    for value in id_tab.values():   
 
        for (i,item) in enumerate(value):
            if pur_nb in item:
                position.append(i)
                break
 
 
    return position
 
 
print position(tab,'6666.77')

Ah bien vu le enumerate().
Il faudrait comparer les vitesses.
Mais ton code oublie d'enregistrer '' quand il le faut.

Sinon j'ai pensé à une autre solution qui t'intéressera peut être, mister, car elle donne tous les index dans une sous-liste et pas seulement le premier rencontré.
On doit pouvoir faire la même chose en adaptant les codes précédents, mais là encore il faudrait comparer les vitesses, les list comprehension étant favorites sur la ligne de départ. Mais faut voir.

J'ai modifié la valeur de li1 pour qu'on perçoive la différence.

Au fait , j'ai pris des nombres en chaines parce que sous forme numérique, il y avait des problèmes de chiffres à 8 ou 9 rangs après la virgule qui rendaient fausses les if n_pur in liste
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 li1 = [['4229.0'], ['4099.0','6666.77','4100.0'], ['7861.0'], ['9896.0'], ['4505.0', '9948.0', '9956.0'], ['3729.0', '8473.0'], ['1673.09','5678.098','345.84','98.4476'],['233,56.789','8912.3','897.90'],['8796.78','0.876'],['874553.90'], ['3452.8754','98342.86451','98.8306'],['647.98','0.785','987.102'],['784.9'], ['76453.9084','895364','6666.77','98333.90554','98331.23','46653.7766','5.66788','66.7744','3344.5544','54'], ['784555','3833.94','344.23','4556.980','123.42'],['87533.871','8273654.809','6666.77','9344.89']] li2 = [['987.902','2665.12','234.876'],['78663.8234','12.308','4436.902','0.763'], ['647.902','988363.90'],['8643']] li3 = [['7200.80','23.4'],['632.9011'],['6534.98','23.0664','6666.77'],['72.34','120.2','34','18772.32']] tab = {'k1':li1,'k2':li2,'k3':li3} def position(id_tab,pur_nb): position=[] for k in id_tab: lik = id_tab[k] rec = '' lu = [sli for sli in lik if pur_nb in sli] if lu: position.append([ lik.index(sli)+1 for sli in lu ]) else: position.append('') return position print position(tab,'6666.77')

Je vient de faire un essai de bourrin
le résultat assez aléatoire question temps

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
li1 = [['4229.0'], ['4099.0', '4100.0'], ['7861.0'], ['9896.0'], ['4505.0', '9948.0', '9956.0'], ['3729.0', '8473.0'],
       ['1673.09','5678.098','345.84','98.4476'],['233,56.789','8912.3','897.90'],['8796.78','0.876'],['874553.90'],
       ['3452.8754','98342.86451','98.8306'],['647.98'',0.785','987.102'],['784.9'],
       ['76453.9084','895364','98333.90554','98331.23','46653.7766','5.66788','66.7744','3344.5544','54'],
       ['784555','3833.94','344.23','4556.980','123.42'],['87533.871','8273654.809','6666.77','9344.89']]
 
li2 = [['987.902','2665.12','234.876'],['78663.8234','12.308','4436.902','0.763'],
       ['647.902','988363.90'],['8643']]
 
li3 = [['7200.80','23.4'],['632.9011'],['6534.98','23.0664','6666.77'],['72.34','120.2','34','18772.32']]
 
tab = {'k1':li1,'k2':li2,'k3':li3}
for i in range(10000000):
    tab["k%s" %i] = li1
 
import time
 
def position1(id_tab,pur_nb):
    start_time = time.time()
    position=[]
    for value in id_tab.values():   
 
        for (i,item) in enumerate(value):
            if pur_nb in item:
                position.append(i)
                break
    total = (time.time()- start_time)
    print "total : %s" % total      
    return position
 
def position2(id_tab,pur_nb):
    start_time = time.time()
    position=[]
    for value in id_tab.values():   
 
        for (i,item) in enumerate(value):
            if pur_nb in item:
                position.append(i)
                break
    total = (time.time()- start_time)
    print "total : %s" % total
    return position
 
 
print "position 1"
 
position1(tab,'6666.77')
print "position 2"
 
position2(tab,'6666.77')

1essai
position 1
total : 43.3920001984
position 2
total : 43.0

2éme essai
position 1
total : 42.7509999275
position 2
total : 42.9230000973

Citation:

Mais ton code oublie d'enregistrer '' quand il le faut.

je ne vois pas ?

edit d'accord je viens de comprendre avec le code du début mais il y a petit prb le résultat peut étre différent pour le même dictionnaire car les element ne sont pas dans un ordre fixe :?

J'ai fait mes petites mesures de temps aussi:

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
li1 = [['4229.0'], ['4099.0', '4100.0'], ['7861.0'], ['9896.0'], ['4505.0', '9948.0', '9956.0'], ['3729.0', '8473.0'],
       ['1673.09','5678.098','345.84','6666.77','98.4476'],['233,56.789','8912.3','897.90'],['8796.78','0.876'],['874553.90'],
       ['3452.8754','98342.86451','98.8306'],['647.98'',0.785','987.102'],['784.9'],
       ['76453.9084','895364','6666.77','98333.90554','98331.23','46653.7766','5.66788','66.7744','3344.5544','54'],
       ['784555','3833.94','344.23','4556.980','123.42'],['87533.871','8273654.809','6666.77','9344.89']]
 
li2 = [['987.902','2665.12','234.876'],['78663.8234','12.308','4436.902','0.763'],
       ['647.902','988363.90'],['8643']]
 
li3 = [['7200.80','23.4'],['632.9011'],['6534.98','23.0664','6666.77'],['72.34','120.2','34','18772.32']]
 
tab = {'k1':li1,'k2':li2,'k3':li3}
 
 
from timeit import Timer
 
def enum(id_tab,pur_nb):
    position=[]
    for value in id_tab.values():
        rec = ''
        for (i,item) in enumerate(value):
            if pur_nb in item:
                rec = i+1
                break
        position.append(rec)      
    return position
 
 
def xrang(id_tab,pur_nb):
    position=[]
    for k in id_tab:
        rec = ''
        for i in xrange(len(id_tab[k])):
            if pur_nb in id_tab[k][i]:
                rec = i+1
                break
        position.append(rec)
    return position
 
 
def xralia(id_tab,pur_nb):
    position=[]
    for k in id_tab:
        lik = id_tab[k]
        rec = ''
        for i in xrange(len(id_tab[k])):
            if pur_nb in lik[i]:
                rec = i+1
                break
        position.append(rec)
    return position
 
 
def licomp(id_tab,pur_nb):
    position=[]
    for k in id_tab:
        lik = id_tab[k]
        rec = ''
        lu = [sli for sli in lik if pur_nb in sli]
        if lu:
            position.append([ lik.index(sli)+1 for sli in lu ])
        else:
            position.append('')
    return position
 
 
def aff(tu):
    print str(min(tu))[0:5],'    ',str(sum(tu)/len(tu))[0:5],'    ',str(max(tu))[0:5],'       ',round(100*(sum(tu)/len(tu)-min(tu))/min(tu),1),'%',
 
 
print enum(tab,'6666.77')
print xrang(tab,'6666.77')
print xralia(tab,'6666.77')
print licomp(tab,'6666.77')
 
 
 
repet = 7
iterat = 10000
 
tenum = Timer("enum(tab,'6666.77')","from __main__ import enum,tab").repeat(repet,iterat)
txrang = Timer("xrang(tab,'6666.77')","from __main__ import xrang,tab").repeat(repet,iterat)
txralia = Timer("xralia(tab,'6666.77')","from __main__ import xralia,tab").repeat(repet,iterat)
tlicomp =  Timer("licomp(tab,'6666.77')","from __main__ import licomp,tab").repeat(repet,iterat)
 
 
 
print 'minimum    moyenne    maximum     (moy-min)/min '
aff(tenum)
print '    methode avec enumerate'
aff(txrang)
print '    methode  avec xrange'
aff(txralia)
print '    methode  avec xrange et alias'
aff(tlicomp)
print '    methode avec list comprehension'

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
[3, '', 7]
[3, '', 7]
[3, '', 7]
[[3], '', [7, 14, 16]]
minimum    moyenne    maximum     (moy-min)/min 
0.541      0.591      0.742         9.3 %     methode avec enumerate
0.619      0.663      0.802         7.1 %     methode  avec xrange
0.568      0.608      0.676         7.0 %     methode  avec xrange et alias
0.909      1.002      1.184         10.2 %     methode avec list comprehension
 
0.557      0.599      0.741         7.4 %     methode avec enumerate
0.621      0.676      0.829         8.9 %     methode  avec xrange
0.573      0.635      0.733         10.9 %     methode  avec xrange et alias
0.919      1.001      1.132         8.9 %    methode avec list comprehension
 
0.558      0.596      0.733         6.8 %     methode avec enumerate
0.637      0.693      0.787         8.8 %     methode  avec xrange
0.573      0.621      0.765         8.3 %     methode  avec xrange et alias
0.920      0.968      1.065         5.2 %     methode avec list comprehension
 
0.561      0.605      0.714         8.0 %     methode avec enumerate
0.613      0.638      0.666         4.2 %     methode  avec xrange
0.569      0.620      0.726         8.8 %     methode  avec xrange et alias
0.933      0.979      1.068         4.9 %     methode avec list comprehension
 
0.542      0.581      0.616         7.1 %     methode avec enumerate
0.621      0.685      0.794         10.4 %     methode  avec xrange
0.571      0.611      0.746         7.0 %     methode  avec xrange et alias
0.920      0.970      1.161         5.5 %     methode avec list comprehension

On vérifie que l'itroduction d'un alias dans le code accélère effectivement l'exécution

enumerate() doit être une fonction optimisée parce qu'elle est légèrement plus rapide, ce n'est pas la première fois que je le remarque. C'est une chose à retenir.

Avec list comprehension , c'est plus long mais c'est normal car ce code travaille plus.

24/04/2009, 09h59
mister2502

Merci pour ces recherches.
enumerate permet d'indexer efficacement ma liste de listes.
Comme je veux trouver l'indice de la première liste contenant pur_nb (présent une seule fois dans les sous-listes, s'il est présent), c'est pratique.
En temps d'exécution, les fonctions se valent (sauf avec list comprehension).
Pour ces 3 fonctions, c'est le test pur_nb in list qui prend du temps.
Mais comment s'en passer ?
Je vais chercher des optimisations avec set ou les propriétés de bisect (on y a droit comme les sous-listes sont triées).
24/04/2009, 11h27
mister2502

Lors de la construction du dictionnaire tab, si on convertit les listes li1(,2,3) de listes en listes de sets, on divise le temps d'exécution par 6 environ !
24/04/2009, 11h37
Tyrus

Peut être que tu gagne en performance mais est ce que tu ne perds pas l'information que tu rechercher car si je me trompe pas les set met les élément dans l'ordre croissant donc tu perd la position de l'élément :? (et il n'est pas possible d'avoir deux éléments identique )
Ou j'ai peut étre pas compris le but de ton programme :aie:
24/04/2009, 11h51
mister2502

Je ne devrais pas perdre d'info.

Ex. cherché:

tab={ 1:[set(2,5),set(4)], 2:[set(1,3),set(5,8)], 3:[set(2,6,8,9)] }

position(tab,5)

doit renvoyer:

[0,1,'']
24/04/2009, 11h53
eyquem

- Utiliser des sets, c'est ce à quoi j'avais aussi pensé. J'étais en train de monter un code pour tester.
Quand tu dis «Lors de la construction du dictionnaire tab», c'est avant l'entrée dans la fonction position() n'est ce pas ?

C'est une chose qu'il faut faire à mon avis pour tout code: ne pas rester plongé dans une fonction, il faut penser de façon intégrée, replacer une fonction dans le contexte général du code et créer les structures de données en amont en pensant à la façon dont elles seront traitées plus loin. Mais bon, je dois énoncer une évidence connue de tout développeur un peu avancé.

- Une chose m'intéresserait de savoir: y a-t-il eu gain de temps entre ton deuxième code (message #4) et les codes qu'on ta proposés ? Combien ?
g 1 pe la flèm

- Sinon, comme j'avais commencé à l'écrire avant de lire ton message, il est essentiel de sortir le regard de la fonction position(id_tab,pur_nb) pour se demander à quel usage elle servira:
va-t-elle servir plusieurs fois sur un même dictionnaire avec des n différents ?
Si c'est le cas il y a avantage à adapter le code pour faire trouver tous les index de tous les n à chercher dans un seul passage dans un dictionnaire donné:

au lieu de faire
- parcourir tab1 pour touver l'index de n1
- parcourir tab2 pour touver l'index de n2
- parcourir tab3 pour touver l'index de n3
- parcourir tab4 pour touver l'index de n4
- parcourir tab5 pour touver l'index de n5

il vaut mieux faire
- parcourir tab1 pour trouver n2,n5,n3,n1,n4
24/04/2009, 11h56
eyquem

S'il remplace 'une liste de listes' par 'une liste de sets' et recherche l'index d'un set au sein de la liste de sets, il n'y a pas de problème. Setévident.
24/04/2009, 12h19
Tyrus

Ah ok les list sont toujours en ordre croissante donc oui les set conviennent à la situation
24/04/2009, 12h22
mister2502

Quand je lance mon programme, j'appelle plusieurs fois la fonction position sur un même dictionnaire id_tab pour des valeurs différentes de pur_nb.

Toutes les versions de la fonction position (y compris la mienne) se valent en temps d'exécution (noyée dans le programme). Seule la version list comprehension est vraiment plus lente.

En construisant un dictionnaire de listes de sets, le gain de temps est le plus grand avec la version xralia de position (facteur 6 au lieu de 3 ou 4 pour les autres versions) que j'ai donc retenue.
24/04/2009, 14h10
eyquem

Tyrus,

Le dictionnaire n'est pas trié , par définition.

Chaque liste-élément du dictionnaire n'est pas triée.

Les sous-listes de chaque liste sont triées mais ça n'a pas d'importance pour la recherche visée. On cherche un index dans une liste non triée, c'est tout