Cosa sta succedendo esattamente nelle liste annidate infinite?

Question

È possibile creare un elenco nidificato infinito in Python. Questo è chiaro e, sebbene non sia popolare e sicuramente non utile, è un fatto noto.

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

La mia domanda è, che cosa sta succedendo qui:

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

cui ogni modo più profondo, quando sto cercando di capirlo, mi sento molto più come il mio cervello sta per esplodere. Vedo, che contiene b, che contiene un e così via ...

Ora le mie domande su questo. Abbiamo davvero due liste qui, o solo una? Come viene memorizzata una cosa come questa? Quale potrebbe essere uno scopo per consentire ai programmatori di implementare qualcosa di così strano come questo?

Per favore, non trattare questa domanda super-seria. E non dimenticare, che la programmazione può essere divertente a volte.

Answer 1

Disclaimer: Non faccio uso di Python, per cui alcune cose che dico può essere sbagliato. Esperti di Python, sentiti libero di correggermi.

Ottima domanda. Credo che l'idea sbagliata centrale (se non posso nemmeno chiamare così: è perfettamente ragionevole come sei arrivato al processo di pensiero si è utilizzato) hai che richiede di porre la domanda è questa:

Quando scrivo b[0] = a, non significa che a è inb. Significa che b include un riferimento che punta alla cosa a cui punta a.

Le variabili a e b stessi non sono ancora "cose" se stessi, e loro si sono anche solo puntatori ai altrimenti anonimi "cose" in memoria.

Il concetto di riferimenti è un grande salto dal mondo non-programmazione, quindi cerchiamo di passare in rassegna il programma con questo in mente:

>>> a = [0] 

Si crea un elenco che succede ad avere qualcosa in esso (ignorare quello per ora). Ciò che conta è che è una lista. Tale elenco viene memorizzato in memoria. Diciamo che è memorizzato nella posizione di memoria 1001. Quindi, l'assegnazione = crea una variabile a che il linguaggio di programmazione consente di utilizzare in un secondo momento. A questo punto, c'è un elenco di oggetti in memoria e un riferimento ad esso che è possibile accedere con il nome a.

>>> b = [0] 

Questo fa la stessa cosa per b. C'è un nuovo elenco che viene memorizzato nella posizione di memoria 1002. Il linguaggio di programmazione crea un riferimento b che è possibile utilizzare per fare riferimento alla posizione di memoria ea sua volta l'oggetto elenco.

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

Questo fa due cose che sono identici, quindi concentriamoci su un: a[0] = b. Ciò che fa è piuttosto elaborato. Prima valuta il lato destro dell'uguaglianza, vede la variabile b e recupera l'oggetto corrispondente nella memoria (oggetto memoria # 1002) poiché b è un riferimento ad esso. Quello che succede a sinistra è ugualmente elegante. a è una variabile che punta a un elenco (oggetto di memoria # 1001), ma l'oggetto di memoria # 1001 stesso ha un numero di riferimenti proprio. Invece di quei riferimenti che hanno nomi come a e b, che si utilizzano, questi riferimenti hanno indici numerici come 0. Quindi, ora, ciò che fa è a richiama l'oggetto di memoria # 1001, che è una pila di riferimenti indicizzati, e va al riferimento con indice 0 (in precedenza, questo riferimento indicava il numero effettivo 0, che è qualcosa che hai fatto nella riga 1) e quindi reimposta tale riferimento (ovvero, il primo e unico riferimento nell'oggetto di memoria # 1001) a ciò che la cosa sul lato destro dell'equazione valuta. Così ora, l'0 ° punto dell'oggetto 1001 fa riferimento all'oggetto # 1002.

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

Questo è solo fanciness fatto dal linguaggio di programmazione. Quando lo chiedi per valutare a, estrae l'oggetto di memoria (l'elenco nella posizione # 1001), rileva utilizzando la propria magia che è infinito e si presenta come tale.

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

Il fallimento di questa affermazione ha a che fare con il modo in Python fa paragoni. Quando si confronta un oggetto con se stesso, esso viene valutato immediatamente come true. Quando confronti e ti opponi a un altro oggetto, usa "magia" per determinare se l'uguaglianza debba essere vera o falsa. Nel caso di elenchi in Python, esamina ogni elemento in ogni elenco e verifica se sono uguali (a sua volta utilizzando i metodi di verifica dell'uguaglianza degli oggetti stessi). Quindi, quando provi il a == b. Quello che fa è prima scavare b (oggetto # 1002) e un (oggetto # 1001) e poi si rende conto che sono cose diverse in memoria, quindi va al suo check list ricorsivo. Lo fa iterando attraverso le due liste. L'oggetto # 1001 ha un elemento con indice 0 che punta all'oggetto # 1002. L'oggetto # 1002 ha un elemento con indice 0 che punta all'oggetto # 1001. Pertanto, il programma conclude che l'oggetto # 1001 e # 1002 sono uguali se tutti i loro riferimenti puntano alla stessa cosa, ergo se # 1002 (quali sono solo i punti di riferimento di # 1001 a) e # 1001 (quali sono gli unici punti di riferimento di # 1002) la stessa cosa. Questo controllo di uguaglianza non può mai fermarsi. La stessa cosa accadrebbe in qualsiasi elenco che non si fermasse. Si potrebbe fare c = [0]; d = [0]; c[0] = d; d[0] = c e a == c avrebbe generato lo stesso errore.

>>> a[0] == b 
True 

Come ho accennato nel paragrafo precedente, questo risolve immediatamente vero perché Python prende una scorciatoia. Non è necessario confrontare il contenuto dell'elenco perché a[0] punti all'oggetto # 1002 e b punti all'oggetto # 1002. Python rileva che sono identici in senso letterale (sono la stessa "cosa") e non si preoccupano nemmeno di controllare i contenuti.

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

Questo torna ad essere un errore perché a[0][0] finisce indicando obiettare # 1001. Il controllo dell'identità fallisce e ricade sul controllo del contenuto ricorsivo, che non finisce mai.

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

Ancora una volta, a[0][0][0] punti per oggetto # 1002, come fa b. Il controllo ricorsivo viene saltato e il confronto ritorna immediatamente vero.

---

superiore jibber livello jabber non direttamente correlata alla snippet di codice specifico:

• Poiché tutto quello che c'è è riferimenti che si riferiscono ad altri oggetti, anche se non c'è quello che sembra essere di nidificazione "infinito", l'oggetto indicato da a (come ho chiamato l'oggetto # 1001) e l'oggetto denominato b (n. 1002) hanno entrambe la stessa dimensione in memoria. E quella dimensione è in realtà incredibilmente piccola dal momento che tutte sono liste che puntano alle rispettive posizioni di memoria.
• Vale anche la pena notare che in lingue meno "generosi", mettendo a confronto due riferimenti con == rendimenti truesolo se gli oggetti di memoria a cui puntano sono gli stessi, nel senso che entrambi i riferimenti puntano allo stesso punto in memoria. Java è un esempio di questo. La convenzione stilistica che è emersa in questi linguaggi è quella di definire un metodo/funzione sugli oggetti stessi (per Java, è convenzionalmente chiamato equals()) per eseguire test di uguaglianza personalizzati. Python lo fa per gli elenchi. Non so in particolare su Python, ma almeno in Ruby, == è sovraccarico nel senso che quando si esegue someobject == otherobject, in realtà si chiama un metodo chiamato == su someobject (che è possibile sovrascrivere). In teoria, non vi sarebbe nulla che ti impedisca di rendere someobject == otherobject restituire qualcosa di diverso da un valore booleano.

Answer 2

ho sospetto accade quanto segue:

a[0]==b: Python guarda in alto il valore a[0] e trova un qualche tipo di riferimento a b, così si dice True.

a[0][0]==b: Python guarda a[0], trova b e ora guarda in alto a[0][0], che è, (dal momento che a[0] vale b) b[0]. Ora vede, che b[0] contiene una sorta di riferimento a a, che non è esattamente la stessa di b. Quindi python deve confrontare gli elementi, il che significa che deve confrontare a[0] contro b[0]. Ora inizia la ricorsione infinita ...

Si noti che questo funziona solo perché Python non copia effettivamente l'elenco quando si assegna a[0]=b. Python crea piuttosto un riferimento a b che viene memorizzato in a[0].

Answer 3

Questi sono due elenchi. In primo luogo, si crea loro:

a = [0] 
b = [0] 

E poi, si assegna ciascuno al primo elemento dell'altro:

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

Così si può dire

a[0] is b 

e

b[0] is a 

che è la stessa situazione come primo esempio, ma livello più profondo.

Inoltre, non si confronta per l'identità (is), ma per l'uguaglianza (==). Questo porta a provare a confrontarli - profondamente dentro, ciò che porta a una ricorsione.

Answer 4

vedo, che una contiene b, che contiene un

Essi non contengono l'un l'altro come tale - A è un riferimento ad una lista, la prima cosa in questo elenco è un punto di riferimento a B e 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 

Il numero di [0] 's qui non importa, come si può fare il maggior numero di ricerche della lista che vuoi - ciò che conta è che nell'esempio # 1 e # 3 (e tutti i numeri dispari di ricerche) stai dicendo "è B uguale a B", a quel punto python confronta gli indirizzi di memoria a e vede che sono la stessa cosa, quindi dice di sì. Con l'esempio # 2 (e tutte le ricerche pari) che stai dicendo "è uguale a B", python vede che sono diversi indirizzi di memoria, e quindi prova a caricare l'intera struttura (infinita) dei dati in memoria per fare un confronto di profondità.

Answer 5

a[0] riferisce a b e b[0] riferisce a a. Questo è un riferimento circolare. Come menzionato da glglgl, quando provi l'operatore == prova il confronto dei valori.

Prova questo, che potrebbe rendere le cose più chiare -

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