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

Question

Можно создать бесконечный вложенный список в Python. Это ясно, и хотя это не популярно и определенно бесполезно, это известный факт.

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

У меня вопрос, что здесь происходит:

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

Что каждый путь глубже, когда я пытаюсь понять это, я чувствую гораздо больше, как будто мой мозг взорвется. Я вижу, что a содержит b, содержит a и так далее...

Теперь мои вопросы об этом. У нас действительно есть два списка здесь или только один? Как такая вещь сохраняется в памяти? Что может быть целью позволить программистам реализовать что-то такое странное, как это?

Пожалуйста, не относитесь к этому вопросу очень серьезно. И не забывайте, что программирование иногда может быть веселым.

Answer 1

Отказ от ответственности: я не использую 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) на то, что оценивает вещь в правой части уравнения. Итак, теперь нулевая ссылка объекта # 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

Как я намекал в предыдущем абзаце, это сразу же становится истинным, потому что 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.

---

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

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

Answer 2

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

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

Answer 3

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

Попробуйте это, что может сделать вещи более ясными -

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

Answer 4

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

Они не содержат друг друга как таковые - 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 (и всех нечетных числах поисков) вы говорите: " это B равно B", в этот момент python сравнивает адреса памяти и видит, что это одно и то же, поэтому говорит да. В примере №2 (и во всех четных поисках) вы говорите "равно A равно B", python видит, что это разные адреса памяти, а затем пытается загрузить всю (бесконечную) структуру данных в память, чтобы сделать более сравнение глубины

Answer 5

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

a = [0]
b = [0]

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

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

Так что можете сказать

a[0] is b

а также

b[0] is a

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

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