Comment sont réellement implémentées les listes ?

Le
pehache
Bonjour,

Comme dit dans le titre, comment sont implémentées les listes python ?
Au début je pensais que c'était des listes chaÍ®nées, mais ensuite j'ai
lu que c'était des tableaux dynamiques.

Mais pour moi qui dit tableau dit taille égale de toutes les cases pour
pouvoir calculer rapidement l'adresse d'un élément donné. Donc comment
ça se passe pour les listes qui ne contiennent pas des objets de même
taille ?

- c'est le plus gros objet de la liste qui détermine la taille des
cases, donc avec potentiellement beaucoup de mémoire perdue, et surtout
un gros boulot pour réarranger le tableau quand un objet plus gros que
les autres est inséré.

- le tableau est en fait un tableau de pointeurs (donc avec deux fois la
taille nécessaire quand on a que des nombres dedans).

Je suppose que c'est la deuxième réponse qui est la bonne ?
  • Partager ce contenu :
Vos réponses
Trier par : date / pertinence
Benoit Izac
Le #26562187
Bonjour,
Le 07/12/2020 Í  09:42, pehache a écrit dans le message
Comme dit dans le titre, comment sont implémentées les listes python ?
Au début je pensais que c'était des listes chaÍ®nées, mais ensuite j'ai
lu que c'était des tableaux dynamiques.
Mais pour moi qui dit tableau dit taille égale de toutes les cases
pour pouvoir calculer rapidement l'adresse d'un élément donné. Donc
comment ça se passe pour les listes qui ne contiennent pas des objets
de même taille ?
- c'est le plus gros objet de la liste qui détermine la taille des
cases, donc avec potentiellement beaucoup de mémoire perdue, et
surtout un gros boulot pour réarranger le tableau quand un objet plus
gros que les autres est inséré.
- le tableau est en fait un tableau de pointeurs (donc avec deux fois
la taille nécessaire quand on a que des nombres dedans).
Je suppose que c'est la deuxième réponse qui est la bonne ?

Oui, au moins pour Cpython, c'est bien un tableau de pointeur vers des
objets Python.
Une liste chaÍ®née n'est pas adressable, l[42] demanderait 41 next()
avant d'arriver Í  l'objet souhaité (O(n) contre O(1) pour un tableau).
Ce qui se rapproche le plus d'une liste chaÍ®né est queue.Queue ou
collection.deque (qui est adressable).
Sinon, un nombre reste un objet :
dir(42)



['__abs__', …, 'to_bytes']
Enfin, une liste, contrairement Í  un tableau, peut stocker n'importe
quel type d'objet :
l = ['a', 1, {}]
l[0] = set()
l



[set(), 1, {}]
C'est aussi pour cela qu'on parle de shallow (adresse) ou deep (objet)
copy.
--
Benoit Izac
pehache
Le #26562216
Le 07/12/2020 Í  20:32, Benoit Izac a écrit :
Bonjour,
Le 07/12/2020 Í  09:42, pehache a écrit dans le message
Comme dit dans le titre, comment sont implémentées les listes python ?
Au début je pensais que c'était des listes chaÍ®nées, mais ensuite j'ai
lu que c'était des tableaux dynamiques.
Mais pour moi qui dit tableau dit taille égale de toutes les cases
pour pouvoir calculer rapidement l'adresse d'un élément donné. Donc
comment ça se passe pour les listes qui ne contiennent pas des objets
de même taille ?
- c'est le plus gros objet de la liste qui détermine la taille des
cases, donc avec potentiellement beaucoup de mémoire perdue, et
surtout un gros boulot pour réarranger le tableau quand un objet plus
gros que les autres est inséré.
- le tableau est en fait un tableau de pointeurs (donc avec deux fois
la taille nécessaire quand on a que des nombres dedans).
Je suppose que c'est la deuxième réponse qui est la bonne ?

Oui, au moins pour Cpython, c'est bien un tableau de pointeur vers des
objets Python.


OK, ça parait logique...
pehache
Le #26562227
Le 07/12/2020 Í  20:32, Benoit Izac a écrit :
Bonjour,
Le 07/12/2020 Í  09:42, pehache a écrit dans le message
Comme dit dans le titre, comment sont implémentées les listes python ?
Au début je pensais que c'était des listes chaÍ®nées, mais ensuite j'ai
lu que c'était des tableaux dynamiques.
Mais pour moi qui dit tableau dit taille égale de toutes les cases
pour pouvoir calculer rapidement l'adresse d'un élément donné. Donc
comment ça se passe pour les listes qui ne contiennent pas des objets
de même taille ?
- c'est le plus gros objet de la liste qui détermine la taille des
cases, donc avec potentiellement beaucoup de mémoire perdue, et
surtout un gros boulot pour réarranger le tableau quand un objet plus
gros que les autres est inséré.
- le tableau est en fait un tableau de pointeurs (donc avec deux fois
la taille nécessaire quand on a que des nombres dedans).
Je suppose que c'est la deuxième réponse qui est la bonne ?

Oui, au moins pour Cpython, c'est bien un tableau de pointeur vers des
objets Python.
Une liste chaÍ®née n'est pas adressable, l[42] demanderait 41 next()
avant d'arriver Í  l'objet souhaité (O(n) contre O(1) pour un tableau).
Ce qui se rapproche le plus d'une liste chaÍ®né est queue.Queue ou
collection.deque (qui est adressable).


Pour ce que je comprends des tableaux numpy, ce sont par contre les
objets qui sont stockés directement dedans, pas des pointeurs, on est
d'accord ?
Julien Palard
Le #26562256
Le 2020-12-08 Í  14:20, pehache a écrit :
Pour ce que je comprends des tableaux numpy, ce sont par contre les
objets qui sont stockés directement dedans, pas des pointeurs, on est
d'accord ?

Exact, c'est d'ailleurs pour ça qu'ils annoncent le type de ce qu'ils
contiennent, dans l'attribut `dtype`, par exemple `float64` indique que
le tableau stocke des nombres Í  virgule flottante sur 64 bits [1] chacun.
(Donc on peut dire au revoir a une bonne partie de la magie de Python :
pas de limite ni de perte de précision sur les valeur entières, et
bonjour aux performances, Í  condition de très bien utiliser la
bibliothèque [3]).
Pour ce qui est de l'agencement utilisé par numpy pour représenter les
différentes dimensions, c'est l'attribut `order` qui t'indique comment
c'est organisé [2].
[1]: https://fr.wikipedia.org/wiki/IEEE_754
[2]: https://numpy.org/doc/stable/reference/generated/numpy.array.html
[3]: https://invidious.fdn.fr/watch?v=pMbjk2kZ538
--
mdk
Poster une réponse
Anonyme