¿Qué está pasando exactamente en las listas anidadas infinitas?

Question

Es posible crear una lista anidada infinita en Python. Eso es claro y, aunque no es popular y definitivamente no es útil, es un hecho conocido.

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

Mi pregunta es, ¿qué está sucediendo aquí:

>>> 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 
>>> 

la que cada modo más profundo, cuando estoy tratando de entenderlo, me siento mucho más como si mi cerebro va a explotar. Veo, que a contiene b, que contiene un y así sucesivamente ...

Ahora mis preguntas acerca de esto. ¿Realmente tenemos dos listas aquí, o solo una? ¿Cómo se almacena una cosa como esta en la memoria? ¿Cuál podría ser el propósito de permitir a los programadores implementar algo tan extraño como este?

Por favor, no trate esta pregunta súper seria. Y no olvides que la programación puede ser divertida a veces.

Answer 1

responsabilidad: yo no uso de Python, por lo que algunas cosas que digo estar equivocado. Expertos de Python, siéntete libre de corregirme.

Una gran pregunta. Creo que el error central de (si ni siquiera puedo llamar así, es perfectamente razonable cómo llegó al proceso de pensamiento que utilizó) que está teniendo que le pide hacer la pregunta es la siguiente:

Cuando escribo b[0] = a, no significa que a es enb. Significa que b incluye una referencia que apunta a lo que apunta a a.

Las variables a y b mismos no son aún "cosas" a sí mismos, y ellos mismos también son meramente punteros a lo contrario "cosas" anónimos en la memoria.

El concepto de referencias es un gran salto desde el mundo no-programación, así que vamos a dar un paso a través de su programa con esto en mente:

>>> a = [0] 

Se crea una lista que pasa a tener algo en él (ignorar eso por ahora). Lo que importa es una lista. Esa lista se almacena en la memoria. Digamos que está almacenado en la ubicación de la memoria 1001. Luego, la asignación = crea una variable a que el lenguaje de programación le permite usar más adelante. En este punto, hay un objeto de lista en la memoria y una referencia a la que puede acceder con el nombre a.

>>> b = [0] 

Esto hace lo mismo para b. Hay una nueva lista que se almacena en la ubicación de la memoria 1002. El lenguaje de programación crea una referencia b que puede usar para referirse a la ubicación de la memoria y, a su vez, al objeto de la lista.

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

Esto hace dos cosas que son idénticas, por lo que vamos a centrarnos en uno: a[0] = b. Lo que hace esto es bastante elegante. Primero evalúa el lado derecho de la igualdad, ve la variable b y busca el objeto correspondiente en la memoria (objeto de memoria n. ° 1002) ya que b es una referencia a la misma. Lo que sucede en el lado izquierdo es igualmente elegante. a es una variable que apunta a una lista (objeto de memoria n. ° 1001), pero el objeto de memoria n. ° 1001 tiene un número de referencias propio. En lugar de aquellas referencias que tienen nombres como a y b, que utiliza, esas referencias tienen índices numéricos como 0. Entonces, ahora, lo que hace es a saca el objeto de memoria # 1001, que es un montón de referencias indexadas, y va a la referencia con el índice 0 (anteriormente, esta referencia apuntaba al número real 0, que es algo que hiciste en la línea 1) y luego remarca esa referencia (es decir, la primera y única referencia en el objeto de memoria n. ° 1001) a lo que evalúa la cosa en el lado derecho de la ecuación. Entonces, la 0ª referencia del objeto # 1001 apunta al objeto # 1002.

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

Esto es solo fanatismo hecho por el lenguaje de programación. Cuando solo le pides que evalúe a, tira del objeto de memoria (la lista en la ubicación n. ° 1001), detecta usando su propia magia que es infinito y se presenta como tal.

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

El error de esta afirmación tiene que ver con la forma en que Python hace las comparaciones. Cuando compara un objeto consigo mismo, inmediatamente lo evalúa como verdadero. Cuando compara y objeta a otro objeto, usa "magia" para determinar si la igualdad debe ser verdadera o falsa. En el caso de las listas en Python, examina cada elemento de cada lista y comprueba si son iguales (a su vez utilizando los propios métodos de comprobación de igualdad de los elementos). Entonces, cuando pruebas a == b. Lo que hace es desenterrar primero b (objeto n. ° 1002) y a (objeto n. ° 1001) y luego se da cuenta de que son cosas diferentes en la memoria, por lo que pasa a su comprobador recursivo de listas. Lo hace iterando a través de las dos listas. El objeto n. ° 1001 tiene un elemento con índice 0 que apunta al objeto n. ° 1002. El objeto n. ° 1002 tiene un elemento con índice 0 que apunta al objeto n. ° 1001. Por lo tanto, el programa concluye que los objetos # 1001 y # 1002 son iguales si todas sus referencias apuntan a lo mismo, ergo si # 1002 (a que referencia la única referencia del # 1001) y # 1001 (a cuál referencia el único 1002 puntos) la misma cosa. Este control de igualdad nunca se puede detener. Lo mismo sucedería en cualquier lista que no se detenga. Usted podría hacer c = [0]; d = [0]; c[0] = d; d[0] = c y a == c levantaría el mismo error.

>>> a[0] == b 
True 

Como insinué en el párrafo anterior, esto inmediatamente se resuelve como verdadero porque Python toma un atajo. No es necesario comparar los contenidos de la lista porque a[0] apunta al objeto # 1002 y b apunta al objeto # 1002. Python detecta que son idénticos en el sentido literal (son la misma "cosa") y ni siquiera se molesta en verificar los contenidos.

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

Este vuelve a ser un error porque a[0][0] termina señalando al objeto # 1001. La verificación de identidad falla y vuelve a la verificación de contenido recursivo, que nunca termina.

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

Una vez más, a[0][0][0] puntos al objeto # 1002, al igual que b. El control recursivo se omite y la comparación se devuelve inmediatamente verdadera.jibber nivel

---

Superior Jabber no directamente relacionado con el fragmento de código específica:

• Dado que todo lo que hay es referencias que se refieren a otros objetos, aunque no es lo que parece ser anidación "infinita", el objeto al que hace referencia a (como he llamado objeto n. ° 1001) y el objeto al que se hace referencia es b (n. ° 1002) tienen el mismo tamaño en la memoria. Y ese tamaño es realmente increíblemente pequeño, ya que todos ellos son listas que apuntan a las respectivas otras ubicaciones de memoria.
• También vale la pena notar que en las lenguas menos "generoso", comparando dos referencias con == vuelve trueúnica si los objetos de memoria que apuntan son los mismos en el sentido de que ambas referencias apuntan al mismo lugar en la memoria. Java es un ejemplo de esto. La convención estilística que ha surgido en dichos lenguajes es definir un método/función en los propios objetos (para Java, se llama convencionalmente equals()) para realizar pruebas de igualdad personalizadas. Python hace esto fuera de la caja para las listas. No sé sobre Python en particular, pero al menos en Ruby, == está sobrecargado en el sentido de que cuando lo haces someobject == otherobject, en realidad llama a un método llamado == en someobject (que puedes sobrescribir). En teoría, no hay nada que te impida hacer someobject == otherobject devolver algo que no sea booleano.

Answer 2

I sospechoso ocurre lo siguiente:

a[0]==b: Python busca el valor a[0] y se encuentra algún tipo de referencia a b, por lo que dice True.

a[0][0]==b: Pitón mira hacia arriba a[0], encuentra b y ahora mira hacia arriba a[0][0], que es, (ya que a[0] sostiene b) b[0]. Ahora se ve que b[0] tiene algún tipo de referencia a a, que no es exactamente lo mismo que b. Entonces python tiene que comparar elementos, lo que significa que tiene que comparar a[0] contra b[0]. Ahora, la recursión infinita comienza ...

Tenga en cuenta que esto funciona solo porque Python no copia realmente la lista al asignar a[0]=b. Python más bien crea una referencia a b que se almacena en a[0].

Answer 3

Estas son dos listas. En primer lugar, se crea ellas:

a = [0] 
b = [0] 

Y entonces, se asigna a cada uno al primer elemento de la otra:

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

Así que se puede decir

a[0] is b 

y

b[0] is a 

que es la misma situación Ion como el primer ejemplo, pero obedezca al nivel más profundo.

Además, no se compara con la identidad (is), sino con la igualdad (==). Esto nos lleva a tratar de compararlos, profundamente en el interior, lo que conduce a una recursión.

Answer 4

veo, que contiene b, que contiene una

No contienen uno al otro como tal - A es una referencia a una lista, la primera cosa en esta lista es una referencia a B, y viceversa

>>> 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 

El número de [0] está aquí, no importa, como se puede hacer tantas búsquedas en la lista como desee - lo que importa es que en el ejemplo # 1 y # 3 (y todos los números impares de búsquedas) está diciendo "es B igual a B", momento en el que python compara las direcciones de memoria a y ve que son la misma cosa, entonces dice sí. Con el ejemplo n. ° 2 (y todas las búsquedas pares), usted dice "es A igual a B", python ve que son direcciones de memoria diferentes, y luego intenta cargar toda la estructura de datos (infinita) en la memoria para hacer una comparación de profundidad.

Answer 5

a[0] se refiere a b y b[0] se refiere a a. Esta es una referencia circular. Como glglgl ha mencionado, cuando intente con el operador ==, intentará la comparación de valores.

Prueba de esto, lo que podría hacer las cosas más claras -

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