Que se passe-t-il exactement dans les listes imbriquées infinies ?

Question

Il est possible de créer une liste imbriquée infinie en Python. C'est clair et, même si ce n'est pas populaire et certainement pas utile, c'est un fait connu.

>>> a = [0]
>>> a[0] = a
>>> a
[[...]]
>>> a[0] == a
True

Ma question est la suivante : que se passe-t-il ici ?

>>> a = [0]
>>> b = [0]
>>> a[0], b[0] = b, a
>>> a
[[[...]]]
>>> b
[[[...]]]
>>> a == b
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: maximum recursion depth exceeded in cmp
>>> a[0] == b
True
>>> a[0][0] == b
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: maximum recursion depth exceeded in cmp
>>> a[0][0][0] == b
True
>>> 

Ce qui fait que chaque fois que j'essaie de comprendre, j'ai beaucoup plus l'impression que mon cerveau va exploser. Je vois que a contient b, que b contient a et ainsi de suite...

Maintenant, mes questions sur celui-ci. Avons-nous vraiment deux listes ou une seule ? Comment une telle chose est-elle stockée dans la mémoire ? Dans quel but les programmeurs pourraient-ils mettre en œuvre une chose aussi étrange que celle-ci ?

S'il vous plaît, ne prenez pas cette question très au sérieux. Et n'oubliez pas que la programmation peut parfois être amusante.

Answer 1

Avertissement : Je n'utilise pas Python, donc certaines choses que je dis peuvent être erronées. Les experts de Python peuvent me corriger.

Excellente question. Je pense que l'idée fausse la plus répandue (si je ne peux même pas l'appeler ainsi, il est parfaitement raisonnable de savoir comment vous êtes arrivé au processus de pensée que vous avez utilisé) que vous avez et qui vous incite à poser la question est la suivante :

Lorsque j'écris b[0] = a cela ne signifie pas que a es en b . Cela signifie que b comprend une référence qui renvoie à la chose qui a pointe vers.

Les variables a y b ne sont même pas des "choses" elles-mêmes, et elles ne sont elles-mêmes que des pointeurs vers des "choses" autrement anonymes dans la mémoire.

Le concept de références est un saut important par rapport au monde de la non-programmation, nous allons donc parcourir votre programme en gardant cela à l'esprit :

>>> a = [0]

Vous créez une liste qui contient quelque chose (ignorez cela pour l'instant). Ce qui compte, c'est qu'il s'agit d'une liste. Cette liste est stockée en mémoire. Disons qu'elle est stockée à l'emplacement 1001. Ensuite, l'affectation = crée une variable a que le langage de programmation permet d'utiliser ultérieurement. À ce stade, il y a un objet liste en mémoire et une référence à cet objet à laquelle vous pouvez accéder avec le nom a .

>>> b = [0]

Il en va de même pour b . Une nouvelle liste est stockée dans l'emplacement de mémoire 1002. Le langage de programmation crée une référence b que vous pouvez utiliser pour faire référence à l'emplacement de la mémoire et à l'objet de la liste.

>>> a[0], b[0] = b, a

Il s'agit de deux actions identiques, nous allons donc nous concentrer sur l'une d'entre elles : a[0] = b . Ce qu'il fait est assez sophistiqué. Il évalue d'abord le côté droit de l'égalité, voit la variable b et récupère l'objet correspondant dans la mémoire (objet mémoire #1002) puisque b est une référence à celui-ci. Ce qui se passe du côté gauche est tout aussi fantaisiste. a est une variable qui pointe vers une liste (objet mémoire #1001), mais l'objet mémoire #1001 a lui-même un certain nombre de références. Au lieu que ces références aient des noms comme a y b que vous utilisez, ces références ont des indices numériques tels que 0 . Donc, ce que cela fait, c'est a extrait l'objet mémoire #1001, qui est une pile de références indexées, et va à la référence avec l'index 0 (précédemment, cette référence pointait vers le nombre réel 0 (ce que vous avez fait à la ligne 1) et reporte cette référence (c'est-à-dire la première et unique référence de l'objet mémoire 1001) sur ce que l'on évalue du côté droit de l'équation. Ainsi, la 0e référence de l'objet #1001 pointe maintenant vers l'objet #1002.

>>> a
[[[...]]]
>>> b
[[[...]]]

Il s'agit d'une simple fantaisie du langage de programmation. Lorsque vous lui demandez simplement d'évaluer a Il extrait l'objet mémoire (la liste à l'emplacement 1001), détecte par sa propre magie qu'il est infini et s'affiche en tant que tel.

>>> a == b
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: maximum recursion depth exceeded in cmp

L'échec de cette affirmation est lié à la façon dont Python effectue les comparaisons. Lorsque vous comparez un objet à lui-même, il est immédiatement évalué à true. Lorsque vous comparez un objet à un autre objet, il utilise la "magie" pour déterminer si l'égalité doit être vraie ou fausse. Dans le cas des listes en Python, il examine chaque élément de chaque liste et vérifie s'ils sont égaux (en utilisant à leur tour les méthodes de vérification d'égalité des éléments). Ainsi, lorsque vous essayez a == b . Il commence par rechercher b (objet n° 1002) et a (objet n° 1001), puis se rend compte qu'il s'agit de choses différentes en mémoire et passe donc à son vérificateur de liste récursive. Il le fait en itérant à travers les deux listes. L'objet 1001 a un élément d'indice 0 qui pointe vers l'objet 1002. L'objet 1002 a un élément d'indice 0 qui pointe vers l'objet 1001. Par conséquent, le programme conclut que les objets #1001 et #1002 sont égaux si toutes leurs références pointent vers la même chose, donc si #1002 (ce vers quoi pointe la seule référence de #1001) et #1001 (ce vers quoi pointe la seule référence de #1002) sont la même chose. Ce contrôle d'égalité ne peut jamais s'arrêter. La même chose se produirait dans toute liste qui ne s'arrête pas. Vous pourriez faire c = [0]; d = [0]; c[0] = d; d[0] = c y a == c provoquerait la même erreur.

>>> a[0] == b
True

Comme je l'ai laissé entendre dans le paragraphe précédent, cela se résout immédiatement en vrai parce que Python prend un raccourci. Il n'a pas besoin de comparer le contenu des listes parce que a[0] pointe vers l'objet #1002 et b pointe vers l'objet #1002. Python détecte qu'ils sont identiques au sens littéral (ils sont la même "chose") et ne prend même pas la peine de vérifier le contenu.

>>> a[0][0] == b
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: maximum recursion depth exceeded in cmp

Il s'agit à nouveau d'une erreur car a[0][0] finit par pointer vers l'objet #1001. Le contrôle d'identité échoue et se rabat sur le contrôle récursif du contenu, qui ne se termine jamais.

>>> a[0][0][0] == b
True

Une fois de plus, a[0][0][0] pointe vers l'objet #1002, tout comme b . La vérification récursive est ignorée et la comparaison renvoie immédiatement un résultat positif.

---

Jibber jabber de niveau supérieur qui n'est pas directement lié à votre extrait de code spécifique :

• Puisqu'il n'y a que des références à d'autres objets, même si l'imbrication semble "infinie", l'objet auquel se réfère le mot a (c'est ainsi que j'ai appelé l'objet #1001) et l'objet auquel il est fait référence est b (#1002) ont la même taille en mémoire. Et cette taille est en fait incroyablement petite puisqu'il ne s'agit que de listes qui pointent vers les autres emplacements de mémoire respectifs.
• Il convient également de noter que dans les langues moins "généreuses", la comparaison de deux références avec == retours true sólo si les objets de mémoire vers lesquels ils pointent sont les mêmes, en ce sens que les deux références pointent vers le même endroit de la mémoire. Java en est un exemple. La convention stylistique qui a émergé dans de tels langages consiste à définir une méthode/fonction sur les objets eux-mêmes (pour Java, elle est conventionnellement appelée equals() ) pour effectuer des tests d'égalité personnalisés. Python le fait d'office pour les listes. Je ne connais pas Python en particulier, mais au moins Ruby, == est surchargé dans le sens où lorsque vous faites someobject == otherobject il appelle en fait une méthode appelée == sur someobject (que vous pouvez écraser). En théorie, rien ne vous empêche de faire de la someobject == otherobject renvoie autre chose qu'un booléen.

Answer 2

I suspect il se produit ce qui suit :

a[0]==b : Python recherche la valeur a[0] et trouve une sorte de référence à b Il est donc écrit True .

a[0][0]==b : Python consulte a[0] , trouve b et regarde maintenant vers le haut a[0][0] ce qui est, (puisque a[0] cale b ) b[0] . Il voit maintenant que b[0] contient une sorte de référence à a ce qui n'est pas exactement la même chose que b . Python doit donc comparer des éléments, ce qui signifie qu'il doit comparer a[0] contre b[0] . Maintenant, la récursion infinie commence...

Notez que cela fonctionne uniquement parce que Python ne copie pas réellement la liste lors de l'assignation de a[0]=b . Python crée plutôt une référence à b qui est stockée dans a[0] .

Answer 3

a[0] se réfère à b y b[0] se réfère à a . Il s'agit d'une référence circulaire. Comme l'a mentionné glglgl, lorsque vous utilisez == il effectue la comparaison des valeurs.

Essayez ceci, qui pourrait rendre les choses plus claires -

>>> id(a)
4299818696
>>> id(b)
4299818768
>>> id(a[0])
4299818768
>>> 
>>> id(b[0])
4299818696

Answer 4

Je vois que a contient b, qui contient a

Ils ne se contiennent pas l'un l'autre en tant que tels - A est une référence à une liste, la première chose dans cette liste est une référence à B, et vice versa.

>>> a[0] == b
True
>>> a[0][0] == b
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: maximum recursion depth exceeded in cmp
>>> a[0][0][0] == b
True

Le nombre de [0] n'a pas d'importance, car vous pouvez faire autant de recherches dans les listes que vous le souhaitez - ce qui compte, c'est que dans les exemples 1 et 3 (et tous les nombres impairs de recherches), vous dites "est-ce que B est égal à B", et à ce moment-là, Python compare les adresses mémoire et voit qu'il s'agit de la même chose, et dit donc oui. Dans l'exemple n°2 (et tous les nombres pairs de recherches), vous dites "A est-il égal à B", Python voit qu'il s'agit d'adresses mémoire différentes, et essaie alors de charger toute la structure de données (infinie) en mémoire pour effectuer une comparaison plus approfondie.

Answer 5

Il s'agit de deux listes. Tout d'abord, vous les créez :

a = [0]
b = [0]

Ensuite, vous affectez chacun d'eux au premier élément de l'autre :

a[0], b[0] = b, a

Vous pouvez donc dire

a[0] is b

et

b[0] is a

ce qui correspond à la même situation que le premier exemple, mais à un niveau plus profond.

En outre, vous ne comparez pas pour l'identité ( is ), mais pour l'égalité ( == ). Cela conduit à essayer de les comparer - profondément à l'intérieur, ce qui conduit à une récursion.