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

From	Benoit Izac <use.reply.to@INVALID.ADDRESS>
Newsgroups	fr.comp.lang.python
Subject	Re: Comment sont réellement implémentées les listes ?
Date	2020-12-07 20:32 +0100
Message-ID	<875z5dh0os.fsf@izac.org> (permalink)
References	<i3686vF1bqcU1@mid.individual.net>

Show all headers | View raw

Bonjour,

Le 07/12/2020 à 09:42, pehache a écrit dans le message
<i3686vF1bqcU1@mid.individual.net> :

> 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.
<https://github.com/python/cpython/blob/master/Include/cpython/listobject.h>

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

Back to fr.comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Comment sont réellement implémentées les listes ? pehache <pehache.7@gmail.com> - 2020-12-07 09:42 +0100
  Re: Comment sont réellement implémentées les listes ? Benoit Izac <use.reply.to@INVALID.ADDRESS> - 2020-12-07 20:32 +0100
    Re: Comment sont réellement implémentées les listes ? pehache <pehache.7@gmail.com> - 2020-12-08 11:39 +0100
    Re: Comment sont réellement implémentées les listes ? pehache <pehache.7@gmail.com> - 2020-12-08 14:20 +0100
      Re: Comment sont réellement implémentées les listes ? Julien Palard <julien@palard.fr> - 2020-12-08 22:09 +0100

csiph-web