Что именно происходит в бесконечных вложенных списках?

Отказ от ответственности: я не использую Python, поэтому некоторые вещи, которые я говорю, могут быть неверными. Знатоки Python, не стесняйтесь меня поправлять.

Отличный вопрос. Я думаю, что центральное заблуждение (если я даже не могу его так назвать; вполне разумно, как вы пришли к используемому вами мыслительному процессу), которое побуждает вас задать вопрос, заключается в следующем:

Когда я пишу b[0] = a, это не означает, что a в b. Это означает, что b включает ссылку, указывающую на объект, на который указывает a.

Переменные a и b сами по себе даже не являются "вещами", и сами они также являются просто указателями на анонимные "вещи" в памяти.

Концепция ссылок — это большой скачок из мира программирования, поэтому давайте пройдемся по вашей программе с учетом этого:

>>> a = [0]

Вы создаете список, в котором что-то есть (пока не обращайте на это внимания). Важно то, что это список. Этот список сохраняется в памяти. Допустим, он хранится в ячейке памяти 1001. Затем присваивание = создает переменную a, которую язык программирования позволяет вам использовать позже. На данный момент в памяти есть некоторый объект списка и ссылка на него, к которой вы можете получить доступ с именем a.

>>> b = [0]

Это делает то же самое для b. Существует новый список, который сохраняется в ячейке памяти 1002. Язык программирования создает ссылку b, которую вы можете использовать для ссылки на ячейку памяти и, в свою очередь, на объект списка.

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

Это делает две идентичные вещи, поэтому давайте сосредоточимся на одной: a[0] = b. То, что это делает, довольно причудливо. Сначала он оценивает правую часть равенства, видит переменную b и выбирает соответствующий объект в памяти (объект памяти #1002), так как b является ссылкой на него. То, что происходит на левой стороне, столь же причудливо. a — это переменная, указывающая на список (объект памяти № 1001), но сам объект памяти № 1001 имеет несколько собственных ссылок. Вместо тех ссылок, которые имеют такие имена, как a и b, которые вы используете, эти ссылки имеют числовые индексы, такие как 0. Итак, теперь это делает то, что a извлекает объект памяти # 1001, который представляет собой кучу индексированных ссылок, и переходит к ссылке с индексом 0 (ранее эта ссылка указывала на фактическое число 0, что вы и сделали в строке 1), а затем повторно указывает эту ссылку (т. е. первую и единственную ссылку в объекте памяти № 1001) на то, что оценивает вещь в правой части уравнения. Итак, теперь 0-я ссылка объекта №1001 указывает на объект №1002.

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

Это просто фантазия, сделанная языком программирования. Когда вы просто просите его оценить a, он извлекает объект памяти (список в ячейке #1001), определяет с помощью своей собственной магии, что он бесконечен, и отображает себя как таковой.

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

Ошибка этого утверждения связана с тем, как Python выполняет сравнения. Когда вы сравниваете объект с самим собой, он немедленно оценивается как истина. Когда вы сравниваете и возражаете против другого объекта, он использует «магию», чтобы определить, должно ли равенство быть истинным или ложным. В случае списков в Python он просматривает каждый элемент в каждом списке и проверяет, равны ли они (в свою очередь, используя собственные методы проверки элементов на равенство). Итак, когда вы попробуете a == b. Сначала он выкапывает b (объект № 1002) и a (объект № 1001), а затем понимает, что это разные вещи в памяти, поэтому переходит к своей рекурсивной проверке списка. Он делает это путем перебора двух списков. Объект №1001 имеет один элемент с индексом 0, который указывает на объект №1002. Объект №1002 имеет один элемент с индексом 0, который указывает на объект №1001. Следовательно, программа заключает, что объекты #1001 и #1002 равны, если все их ссылки указывают на одно и то же, следовательно, если #1002 (на что указывает единственная ссылка #1001) и #1001 (на что указывает единственная ссылка #1002) тоже самое. Эта проверка на равенство никогда не остановится. То же самое произойдет в любом списке, который не останавливается. Вы можете сделать c = [0]; d = [0]; c[0] = d; d[0] = c, а a == c вызовет ту же ошибку.

>>> a[0] == b
True

Как я намекнул в предыдущем абзаце, это немедленно принимает значение true, потому что Python использует более короткий путь. Нет необходимости сравнивать содержимое списка, поскольку a[0] указывает на объект №1002, а b указывает на объект №1002. Python определяет, что они идентичны в буквальном смысле (это одна и та же «вещь»), и даже не утруждает себя проверкой содержимого.

>>> 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] в конечном итоге указывает на объект № 1001. Проверка личности дает сбой и возвращается к рекурсивной проверке содержимого, которая никогда не заканчивается.

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

И снова a[0][0][0] указывает на объект №1002, как и b. Рекурсивная проверка пропускается, и сравнение немедленно возвращает значение true.

Джаббер более высокого уровня, не связанный напрямую с вашим конкретным фрагментом кода:

• Поскольку все, что есть, это ссылки, ссылающиеся на другие объекты, хотя существует то, что кажется «бесконечной» вложенностью, объект, на который ссылается a (как я назвал объект № 1001), и объект, на который ссылается b (# 1002). ) имеют одинаковый размер в памяти. И этот размер на самом деле невероятно мал, поскольку все они представляют собой списки, указывающие на соответствующие другие области памяти.
• Также стоит отметить, что в менее «щедрых» языках сравнение двух ссылок с == возвращает true только, если объекты памяти, на которые они указывают, одинаковы в том смысле, что обе ссылки указывают на одно и то же место в памяти. . Java является примером этого. Стилистическое соглашение, появившееся в таких языках, заключается в определении метода/функции на самих объектах (для Java это обычно называется equals()) для выполнения пользовательской проверки на равенство. Python делает это из коробки для списков. Я не знаю конкретно о Python, но, по крайней мере, в Ruby == перегружен в том смысле, что когда вы выполняете someobject == otherobject, он фактически вызывает метод с именем == для someobject (который вы можете перезаписать). Теоретически ничто не мешает вам заставить someobject == otherobject возвращать что-то, кроме логического значения.

Я подозреваю, что происходит следующее:

a[0]==b: Python ищет значение a[0] и находит какую-то ссылку на b, поэтому он говорит True.

a[0][0]==b: Python ищет a[0], находит b и теперь ищет a[0][0], то есть (поскольку a[0] содержит b) b[0]. Теперь он видит, что b[0] содержит какую-то ссылку на a, которая не совсем совпадает с b. Таким образом, python должен сравнивать элементы, что означает, что он должен сравнивать a[0] с b[0]. Теперь начинается бесконечная рекурсия...

Обратите внимание, что это работает только потому, что Python фактически не копирует список при назначении a[0]=b. Python скорее создает ссылку на b, которая хранится в a[0].

a[0] относится к b, а b[0] относится к a. Это циклическая ссылка. Как уже упоминалось в glglgl, когда вы используете оператор ==, он выполняет сравнение значений.

Попробуйте это, что может прояснить ситуацию -

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

Я вижу, что a содержит b, который содержит a

Они не содержат друг друга как таковые - A является ссылкой на список, первое в этом списке является ссылкой на B, и наоборот

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

Количество [0] здесь не имеет значения, так как вы можете выполнять столько поисковых запросов по списку, сколько захотите - важно то, что в примерах № 1 и № 3 (и во всех нечетных числах поисковых запросов) вы говорите " is B равно B", и в этот момент python сравнивает адреса памяти и видит, что это одно и то же, поэтому говорит "да". В примере № 2 (и во всех даже поисковых запросах) вы говорите «равно ли A равному B», python видит, что это разные адреса памяти, а затем пытается загрузить всю (бесконечную) структуру данных в память, чтобы сделать более точные действия. сравнение глубины.

Это два списка. Сначала вы создаете их:

a = [0]
b = [0]

И затем вы назначаете каждый из них первому элементу другого:

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

Итак, вы можете сказать

a[0] is b

и

b[0] is a

это та же ситуация, что и в первом примере, но на более глубоком уровне.

Кроме того, вы сравниваете не на идентичность (is), а на равенство (==). Это приводит к попытке сравнить их - глубоко внутри, что приводит к рекурсии.