parcourir une liste et supprimer des éléments selon une condition

**jean-pat** · 05/05/2011, 15h58

Bonjour,
Je souhaite parcourir une liste et supprimer au fur et à mesure selon une condition des éléments de cette liste. J'ai un probleme d'index out of range:

Code :

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

1
2
3
4
5
6
7
8
9
if __name__ == "__main__":
    liste=[]
    liste.append(12)
    liste.append(7)
    liste.append(99)
    for i in range(0,len(liste)):
        elem=liste[i]
        if (elem % 3==0):liste.remove(liste[i])
    print liste

ce qui est logique, je modifie le nombre d'éléments à l'intérieur de la boucle...

j'ai bien vu

Code :

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

 liste.__delitem__

, mais je ne vois pas comment introduire ma condition...

merci de vos suggestions

**jean-pat** · 05/05/2011, 16h09

j'ai trouvé cela finallement

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == "__main__":
    liste=[]
    liste.append(12)
    liste.append(7)
    liste.append(99)
    i=len(liste)
    while i!=0:
        print "i,",i,"l",liste[i-1]
        elem=liste[i-1]
        if (elem % 3==0):liste.remove(liste[i-1])
        i=i-1
    print liste

**rambc** · 05/05/2011, 16h19

Bonjour.

Tu peux utiliser ce que l'on appelle une "list comprehension" :

Code :

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

1
2
3
4
5
6
7
 
liste=[]
liste.append(12)
liste.append(7)
liste.append(99)
 
liste = [x for x in liste if x % 3 != 0]

**jean-pat** · 05/05/2011, 16h27

merci,
cela à l'air recursif, "liste" est une liste contenant un code ... qui la fabrique elle même

Je n'ai pas saisi ce qui supprime l'élément.

**kango** · 05/05/2011, 16h36

bonjour,

plutôt que de supprimer les éléments d'une liste qui satisfont à une condition particulière, rambc te propose un algo qui reconstruit une liste à partir des éléments qui ne satisfont pas à cette même condition.

La ligne:

Code :

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

liste = [x for x in liste if x % 3 != 0]

est strictement équivalente à:

Code :

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

1
2
3
4
5
o = [ ]
for x in liste:
    if x % 3 != 0 #qui peut se simplifier en if x % 3:
        o.append(x)
liste = o

**fatbob** · 05/05/2011, 17h37

Juste un petit éclaircissement sur le problème rencontré :
Si l'on parcours une liste en enlevant des éléments au fur et à mesure, le résultat risque fortement de ne pas correspondre à ce que l'on veut car les éléments retirés perturbent la suite des indices :

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
 
l = [0,1,2,3,5,7,8,10,11]
for i in range(len(l)): # soit range(9)
    print i, l[i]
    if l[i] % 2 != 0:
        print "Delete l[%d] = %d" % (i, l[i])
        del l[i]
    print l
 
> 0 0
> [0, 1, 2, 3, 5, 7, 8, 10, 11]
> 1 1
> Delete l[1] = 1
> [0, 2, 3, 5, 7, 8, 10, 11]
> 2 3
> Delete l[2] = 3
> [0, 2, 5, 7, 8, 10, 11]
> 3 7
> Delete l[3] = 7  # Oooh, le 5 passe à l'as
> [0, 2, 5, 8, 10, 11]
> 4 10
> [0, 2, 5, 8, 10, 11]
> 5 11
> Delete l[5] = 11
> [0, 2, 5, 8, 10]
> 6
> 
> Traceback (most recent call last):
>   File "C:\Mesdoc~1\ReNo\PyPgm\PyUtils\tests\test.py", line 781, in ?
>     am()
>   File "C:\Mesdoc~1\ReNo\PyPgm\PyUtils\tests\test.py", line 775, in am
>     print i, l[i]
> IndexError: list index out of range # Normal, vu que la liste a été réduite en cours de route

**mont29** · 05/05/2011, 18h07

rambc, kango, votre solution est bonne… Mais elle implique la création d’une nouvelle liste.

Le code trouvé par jean-pat le fait en place (ce qui peut avoir son importance, si l’on manipule des listes d’objets lourds en mémoire), et en effet, en partant depuis la fin de la liste, il n’y a pas de problèmes – je le réécrirais juste de façon plus “pythonesque” :

Code :

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

1
2
3
4
5
6
7
8
if __name__ == "__main__":
    liste = [12, 7, 99]
    i = len(liste)
    while i: # équivalent à i != 0
        print("i:",i,", l:",liste[i-1]) # autant s’habituer aux parenthèses, elles sont indispensables en 3.x
        if not liste[i-1] % 3: del liste[i-1]
        i -= 1
    print liste

**kango** · 05/05/2011, 19h05

ce n'est pas ma solution, je me suis contenté d'éclaircir l'approche de rambc

si on ne veut pas dupliquer les éléments en mémoire on peut aussi faire comme ceci:

Code :

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

1
2
3
4
5
6
7
o = [ ]
while liste:
    x = liste.pop()
    if x % 3:
        o.append(x)
o.reverse() #necessaire si on veut conserver l'ordre initial des éléments
liste = o

la solution consistant à supprimer des éléments est problématique quand la liste contient un nombre important (les éléments de la liste doivent être translatés).

c'est pour cette raison que je ne fais pas un pop(0) sur la liste qui est plus lourd que le pop()

**rambc** · 05/05/2011, 20h04

Envoyé par mont29

rambc, ta solution est bonne… Mais elle implique la création d’une nouvelle liste.

Les "lists comprehension" sont très efficaces en terme de rapidité.

Envoyé par mont29

... je le réécrirais juste de façon plus “pythonesque”...

Ah bon !

Donnes-moi un langage qui propose un équivalent des "lists comprehension" ?

**dividee** · 05/05/2011, 21h51

Envoyé par rambc

Donnes-moi un langage qui propose un équivalent des "lists comprehension" ?

Euh... Haskell, Scala, F#, Javascript, Ruby, ...
Sans oublier (si on a une acception assez large de "list comprehension")... SQL.

**jean-pat** · 05/05/2011, 22h01

merci à vous tous pour ces différents angles, bien utile pour un débutant.

**mont29** · 05/05/2011, 22h59

Ce n’était pas ton code que je « réécrivais de façon plus pythonesque », rambc, mais celui de jean-pat… Et de toute façon, kango a trouvé encore mieux dans le genre…

Quand aux list comprehensions, elles sont certes très efficaces, mais entraînent quand même une duplication des éléments (évidemment, si l’on n’en a pas 1000000, ce n’est pas vraiment un problème, donc tu pourrais me reprocher de chercher la p’tite bête

).

**dividee** · 05/05/2011, 23h34

Envoyé par mont29

Quand aux list comprehensions, elles sont certes très efficaces, mais entraînent quand même une duplication des éléments (évidemment, si l’on n’en a pas 1000000, ce n’est pas vraiment un problème, donc tu pourrais me reprocher de chercher la p’tite bête

).

Ce sont les références qui sont dupliquées, pas les objets contenus dans la liste. Même avec 1000000 d'éléments, ça ne fait qu'environ 4MB de plus (en fait, moins dans ce cas-ci, vu qu'on en filtre une partie), et ce quelque soit la taille des objets contenus dans la liste.
Et la liste d'origine est libérée juste après, dans le code de rambc. Cette surcharge est donc très temporaire...

De plus, supprimer un élément au milieu d'une liste est une opération assez coûteuse, car python doit décaler tous les éléments qui suivent pour combler le trou. Comparé à cela, la surcharge de mémoire est un défaut bien mineur...

Une façon plus efficace de le faire "en place" serait:

Code :

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

1
2
3
4
5
6
7
l = [12,7,99]
i = 0
for e in l:
	if e % 3:
		l[i] = e
		i += 1
del l[i:]

**Captain'Flam** · 06/05/2011, 11h22

Juste une question à vous tous qui semblez des pointures en python :

toutes ces solutions que vous proposez en en comparant les performances et coûts supposent de connaître la façon dont python implémente sa classe liste :
- est-ce que l'on peut en être sûr ?
- y a-t-il une doc qui impose une implémentation plutôt qu'une autre ?
- si je m'amuse à implémenter mon propre interpréteur python, suis-je tenu de respecter certaines contraintes (en plus de respecter la sémantique du langage bien sûr) ?

Par exemple, la solution consistant à effacer les éléments en partant de la fin peut ne pas marcher suivant l'implémentation des listes.

Ou encore, la remarque de kango

la solution consistant à supprimer des éléments est problématique quand la liste contient un nombre important (les éléments de la liste doivent être translatés).
c'est pour cette raison que je ne fais pas un pop(0) sur la liste qui est plus lourd que le pop()

n'est valable que pour une implémentation à base de tableau. Avec des listes chaînées, ce n'est plus vrai.

Ma question finale : d'où tirez vous vos certitudes quant aux choix d'implémention de python ?

Merci

**kango** · 06/05/2011, 13h45

Envoyé par Captain'Flam

Ou encore, la remarque de kangon'est valable que pour une implémentation à base de tableau. Avec des listes chaînées, ce n'est plus vrai.

Ma question finale : d'où tirez vous vos certitudes quant aux choix d'implémention de python ?

Merci

du livre d'Alex Martelli , core developer de Python, qui précise dans son livre que le coût du pop(0) est plus important que pop().

De même que la doc officielle de python à propos des deque:

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

source: http://docs.python.org/library/colle...#deque-objects

**jean-pat** · 10/05/2011, 10h23

Envoyé par jean-pat

j'ai trouvé cela finallement

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
if __name__ == "__main__":
    liste=[]
    liste.append(12)
    liste.append(7)
    liste.append(99)
    i=len(liste)
    while i!=0:
        print "i,",i,"l",liste[i-1]
        elem=liste[i-1]
        if (elem % 3==0):liste.remove(liste[i-1])
        i=i-1
    print liste