29 votes

Comment se fait-élément de la liste de recherche est O(1) en Python?

Aujourd'hui, en classe, nous avons appris que la récupération d'un élément d'une liste est - O(1) en Python. Pourquoi est-ce le cas? Supposons que j'ai une liste de quatre éléments, par exemple:

li = ["perry", 1, 23.5, "s"]

Ces éléments ont des tailles différentes dans la mémoire. Et donc, il n'est pas possible de prendre à l'emplacement de li[0] et ajouter trois fois la taille de chaque élément pour obtenir l'emplacement de la mémoire de l' li[3]. Alors, comment fonctionne l'interprète de savoir où li[3] sans avoir à parcourir la liste pour récupérer l'élément?

55voto

dg123 Points 2283

Une liste en Python est mis en œuvre comme un tableau de pointeurs1. Donc, ce qui se passe réellement lorsque vous créez la liste:

["perry", 1, 23.5, "s"]

c'est que vous êtes en fait la création d'un tableau de pointeurs comme suit:

[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]

Chaque pointeur de "points" pour les objets en mémoire, de sorte que la chaîne de caractères "perry" sera stockée à l'adresse 0xa3d25342 et le nombre 1 seront stockés dans 0x635423fa, etc.

Depuis tous les pointeurs sont de la même taille, l'interprète peut en effet ajouter en 3 fois la taille d'un élément à l'adresse de l' li[0] pour obtenir le pointeur stocké dans li[3].


1 Obtenir plus de détails à partir: de la bouche des chevaux (Disponible le code source sur GitHub).

17voto

Draconis Points 1109

Quand vous dites a = [...], a est en fait un pointeur vers un PyObject contenant un tableau de pointeurs PyObjects.

Lorsque vous demandez a[2], l'interprète de la première suit le pointeur de liste, PyObject, puis ajoute 2 à l'adresse du tableau à l'intérieur d'elle, puis retourne le pointeur. La même chose se produit si vous demandez a[0] ou a[9999].

Fondamentalement, tous les objets Python sont accessibles par référence et non par valeur, même les littéraux entiers comme 2. Il y a juste quelques trucs dans le pointeur de système pour garder tout cela efficace. Et les pointeurs ont une taille connue, de sorte qu'ils peuvent être stockés idéalement dans le style C tableaux.

6voto

hkBst Points 420

Réponse courte: Python, les listes sont des tableaux.

Réponse longue: L'ordinateur de la science terme de la liste signifie généralement une liste liée individuellement (comme utilisé dans la programmation fonctionnelle) ou une liste à double liaison (utilisé en programmation procédurale). Ces structures de données de soutien O(1) insertion à la tête de la liste (fonctionnellement) ou à n'importe quelle position qui n'a pas besoin d'être recherché (procédural). Un Python `liste" ne présente aucune de ces caractéristiques. Au lieu de cela il prend en charge (amorti) O(1) en ajoutant à la fin de la liste (comme en C++ std::vector ou Java ArrayList). Python, les listes sont vraiment de redimensionner les tableaux dans CS termes.

Le commentaire suivant de la documentation Python explique certaines des caractéristiques de performances de Python `listes":

Il est également possible d'utiliser une liste comme une file d'attente, où le premier élément ajouté est le premier élément extrait ("first-in, first-out"); cependant, les listes ne sont pas efficaces à cette fin. Tout en ajoute et pop de la fin de la liste sont rapides, faire des insertions ou des pop depuis le début de la liste est lent (parce que de tous les autres éléments doivent être décalés d'un).

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X