Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: pehache Newsgroups: fr.comp.lang.python Subject: =?UTF-8?Q?Re=3a_Comment_sont_r=c3=a9ellement_impl=c3=a9ment=c3=a9es?= =?UTF-8?Q?_les_listes_=3f?= Date: Tue, 8 Dec 2020 14:20:59 +0100 Lines: 39 Message-ID: References: <875z5dh0os.fsf@izac.org> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: individual.net NIP+y42LIaVJiOJmSEIiagIILVvHVqJ5Bh8CGmOHISvVPigufK Cancel-Lock: sha1:LCumB7qls0SqaUC1KWzP7wl651o= User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:78.0) Gecko/20100101 Thunderbird/78.5.1 In-Reply-To: <875z5dh0os.fsf@izac.org> Content-Language: fr Xref: csiph.com fr.comp.lang.python:3408 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 ?