Discussion :

[mister2502]

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 :

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
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.

[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 ?

[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 :

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

for k in tab:

et

Code :

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

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 :

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

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

[mister2502]

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 :

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

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

[eyquem]

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 :

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

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 :

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

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 :

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
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

[Tyrus]

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

Code :

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

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')