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

From	pehache <pehache.7@gmail.com>
Newsgroups	fr.comp.lang.python
Subject	Re: Comment sont réellement implémentées les listes ?
Date	2020-12-08 14:20 +0100
Message-ID	<i39cttFk6bbU1@mid.individual.net> (permalink)
References	<i3686vF1bqcU1@mid.individual.net> <875z5dh0os.fsf@izac.org>

Show all headers | View raw

Le 07/12/2020 à 20:32, Benoit Izac a écrit :
> 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).
> 

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 ?

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