Sur l'impl=c3=a9mentation et la complexit=c3=a9 de del

Le
Dan Wissme
Hello, je pensais que del L[i] provoquait un décalage à gauche de
L[i+1:], mais ça ne semble pas le cas :

>>> L
[0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
>>> id(L)
4321967496
>>> id(L[5]) # adresse de 50 ?
4297625504
>>> del L[2]
>>> L
[0, 10, 30, 40, 50, 60, 70, 80, 90, 100]
>>> id(L[4]) # il n'a pas bougé ???
4297625504
>>> id(L)
4321967496

Qu'en pensez-vous ? Fonctionnement et complexité de del L[i] ?
Merci,

dan
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Nicolas
Le #26437526
Bonjour,
Le 06/07/2017 à 09:14, Dan Wissme a écrit :
Hello, je pensais que del L[i] provoquait un décalage à gauche de
L[i+1:], mais ça ne semble pas le cas :
L





[0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
id(L)





4321967496
id(L[5]) # adresse de 50 ?





4297625504
del L[2]
L





[0, 10, 30, 40, 50, 60, 70, 80, 90, 100]
id(L[4]) # il n'a pas bougé ???





4297625504
id(L)





4321967496
Qu'en pensez-vous ? Fonctionnement et complexité de del L[i] ?
Merci,
dan

Je ne vois rien d'anormal dans tout ça.
Quel est le problème ?
mca
Le #26437783
Le 06/07/2017 à 09:14, Dan Wissme a écrit :
Hello, je pensais que del L[i] provoquait un décalage à gauche de
L[i+1:], mais ça ne semble pas le cas :
L



[0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
id(L)



4321967496
id(L[5]) # adresse de 50 ?



4297625504
del L[2]
L



[0, 10, 30, 40, 50, 60, 70, 80, 90, 100]
id(L[4]) # il n'a pas bougé ???



4297625504
id(L)



4321967496
Qu'en pensez-vous ? Fonctionnement et complexité de del L[i] ?

On manipule une listes de pointeurs vers les éléments de la liste, pas
les éléments de la liste directement (heureusement!)
Un article clair sur l'implémentation des listes en CPython
http://www.laurentluce.com/posts/python-list-implementation/
Dan Wissme
Le #26437917
Le 09/07/2017 à 01:47, mca a écrit :
Le 06/07/2017 à 09:14, Dan Wissme a écrit :
Hello, je pensais que del L[i] provoquait un décalage à gauche de
L[i+1:], mais ça ne semble pas le cas :
L



[0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
id(L)



4321967496
id(L[5]) # adresse de 50 ?



4297625504
del L[2]
L



[0, 10, 30, 40, 50, 60, 70, 80, 90, 100]
id(L[4]) # il n'a pas bougé ???



4297625504
id(L)



4321967496
Qu'en pensez-vous ? Fonctionnement et complexité de del L[i] ?

On manipule une listes de pointeurs vers les éléments de la liste, pas
les éléments de la liste directement (heureusement!)

Ah oui ok, il faut que je me repose un peu :-)
Merci,
dan
ast
Le #26439273
"mca"
Le 06/07/2017 à 09:14, Dan Wissme a écrit :
Hello, je pensais que del L[i] provoquait un décalage à gauche de
L[i+1:], mais ça ne semble pas le cas :
L



[0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
id(L)



4321967496
id(L[5]) # adresse de 50 ?



4297625504
del L[2]
L



[0, 10, 30, 40, 50, 60, 70, 80, 90, 100]
id(L[4]) # il n'a pas bougé ???



4297625504
id(L)



4321967496
Qu'en pensez-vous ? Fonctionnement et complexité de del L[i] ?

On manipule une listes de pointeurs vers les éléments de la liste, pas les éléments de la liste
directement (heureusement!)


Quand on supprime l'un de ces pointeurs avec del L[2], les pointeurs
suivants sont-ils déplacés pour combler le trou ?
Je pense que oui.
from timeit import Timer
L = [n for n in range(1000)]
t1 = Timer("del L[0]; L.insert(0, 0)", "from __main__ import L")
t2 = Timer("del L[999]; L.insert(999, 999)", "from __main__ import L")
t1.repeat(1, 100000)
[0.4349975346028714]
t2.repeat(1, 100000)
[0.10269768923146216]
Travailler en début de liste est plus lent que de travailler en fin de liste
Il y a la structure deque qui évite cet inconvéniant
from collections import deque
L = deque([n for n in range(1000)])
t1 = Timer("L.popleft(); L.appendleft(0)", "from __main__ import L")
t2 = Timer("L.pop(); L.append(999)", "from __main__ import L")
t1.repeat(1, 1000)
[0.0007008572318909501]
t2.repeat(1, 1000)
[0.0007085397725177245]
Publicité
Poster une réponse
Anonyme