cerhu > comp.lang.* > comp.lang.python

Dan Wissme (06/07/2017, 09h14)
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
Nicolas (06/07/2017, 13h14)
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 :
> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
> 4321967496
> 4297625504
> [0, 10, 30, 40, 50, 60, 70, 80, 90, 100]
> 4297625504
> 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 (09/07/2017, 01h47)
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 :
> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
> 4321967496
> 4297625504
> [0, 10, 30, 40, 50, 60, 70, 80, 90, 100]
> 4297625504
> 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
[..]
Dan Wissme (10/07/2017, 12h18)
Le 09/07/2017 à 01:47, mca a écrit :
> Le 06/07/2017 à 09:14, Dan Wissme a écrit :
> 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 (20/07/2017, 13h56)
"mca" <nospam> a écrit dans le message de news:34cc
> Le 06/07/2017 à 09:14, Dan Wissme a écrit :
> 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]
Discussions similaires
compléxité

complexite de l'ACP

Complexité C++

Complexité


Fuseau horaire GMT +2. Il est actuellement 09h31. | Privacy Policy