Điều gì xảy ra chính xác trong danh sách lồng nhau vô hạn?

Question

Có thể tạo danh sách lồng nhau vô hạn bằng Python. Điều đó rõ ràng và, mặc dù không phổ biến và chắc chắn không hữu ích là một thực tế đã biết.

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

Câu hỏi của tôi là, những gì đang xảy ra ở đây:

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

Mà mỗi chiều sâu hơn, khi tôi đang cố gắng để hiểu nó, tôi cảm thấy nhiều hơn nữa như bộ não của tôi đang sắp nổ tung. Tôi thấy, có chứa b, có chứa một và cứ thế ...

Bây giờ, tôi có câu hỏi về vấn đề này. Chúng ta thực sự có hai danh sách ở đây hay chỉ có một danh sách? Làm thế nào một thứ như thế này được lưu trữ trong bộ nhớ? Điều gì có thể là một mục đích để cho phép các lập trình viên thực hiện một cái gì đó kỳ lạ như thế này?

Vui lòng không xử lý câu hỏi này siêu nghiêm trọng. Và đừng quên, đôi khi chương trình đó có thể vui vẻ.

Answer 1

Disclaimer: Tôi không sử dụng Python, vì vậy một số điều tôi nói có thể sai. Các chuyên gia Python, cảm thấy tự do để sửa tôi.

Câu hỏi hay. Tôi nghĩ rằng quan niệm sai lầm trung tâm (nếu tôi thậm chí không thể gọi nó rằng, nó hoàn toàn hợp lý như thế nào bạn đến quá trình suy nghĩ bạn sử dụng) bạn gặp nhắc bạn đặt câu hỏi là điều này:

Khi tôi viết b[0] = a, điều đó không có nghĩa là a là trongb. Điều này có nghĩa là b bao gồm tham chiếu trỏ đến điều mà a trỏ tới.

Biến số a và b bản thân họ thậm chí không phải là "những thứ", và bản thân chúng cũng chỉ là con trỏ tới các "thứ" ẩn danh khác trong bộ nhớ.

Khái niệm về tài liệu tham khảo là một bước nhảy vọt lớn từ thế giới phi lập trình, vì vậy chúng ta hãy bước qua chương trình của bạn với điều này trong tâm trí:

>>> a = [0] 

Bạn tạo một danh sách điều đó xảy ra để có một cái gì đó trong nó (bỏ qua cho đến bây giờ). Điều quan trọng là nó là một danh sách. Danh sách đó được lưu trữ trong bộ nhớ. Giả sử nó được lưu trữ ở vị trí bộ nhớ 1001. Sau đó, việc gán = tạo một biến a rằng ngôn ngữ lập trình cho phép bạn sử dụng sau này. Tại thời điểm này, có một số đối tượng danh sách trong bộ nhớ và tham chiếu đến nó mà bạn có thể truy cập với tên a.

>>> b = [0] 

Điều này cũng tương tự đối với b. Có một danh sách mới được lưu trữ ở vị trí bộ nhớ 1002. Ngôn ngữ lập trình tạo tham chiếu b mà bạn có thể sử dụng để tham khảo vị trí bộ nhớ và lần lượt là đối tượng danh sách.

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

Điều này có hai điểm giống hệt nhau, vì vậy hãy tập trung vào một: a[0] = b. Điều này thực sự là khá lạ mắt. Nó đầu tiên đánh giá bên phải của sự bình đẳng, thấy biến b và tìm nạp đối tượng tương ứng trong bộ nhớ (đối tượng bộ nhớ # 1002) kể từ b là một tham chiếu đến nó. Điều gì xảy ra ở phía bên trái là không kém phần ưa thích. a là một biến trỏ đến một danh sách (đối tượng bộ nhớ # 1001), nhưng đối tượng bộ nhớ # 1001 chính nó có một số tham chiếu của riêng nó. Thay vì những tài liệu tham khảo có tên như a và b, mà bạn sử dụng, các tham chiếu đó có chỉ số như 0. Vì vậy, bây giờ, điều này làm là a kéo lên đối tượng bộ nhớ # 1001, là một đống tham chiếu được lập chỉ mục và tham chiếu đến chỉ mục 0 (trước đây, tham chiếu này chỉ đến số thực tế 0, đó là điều bạn đã làm trong dòng 1) và sau đó repoints tham chiếu đó (ví dụ, tham chiếu đầu tiên và duy nhất trong đối tượng bộ nhớ # 1001) đến điều mà bên phải của phương trình đánh giá. Vì vậy, bây giờ, các điểm tham chiếu 0 của đối tượng # 1001 đến đối tượng # 1002.

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

Đây chỉ là sự khéo léo được thực hiện bởi ngôn ngữ lập trình. Khi bạn chỉ cần yêu cầu đánh giá a, nó sẽ kéo đối tượng bộ nhớ (danh sách ở vị trí # 1001), phát hiện bằng cách sử dụng phép thuật riêng của nó là nó vô hạn và tự hiển thị như vậy.

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

Sự thất bại của tuyên bố này liên quan đến cách so sánh Python. Khi bạn so sánh một đối tượng với chính nó, nó ngay lập tức đánh giá đúng. Khi bạn so sánh và đối tượng với một đối tượng khác, nó sử dụng "ma thuật" để xác định liệu sự bình đẳng phải đúng hay sai. Trong trường hợp các danh sách trong Python, nó xem xét mọi mục trong mỗi danh sách và kiểm tra xem chúng có bằng nhau hay không (lần lượt sử dụng các phương thức kiểm tra bình đẳng riêng của các mục). Vì vậy, khi bạn thử a == b. Những gì nó làm là lần đầu tiên đào b (đối tượng # 1002) và một (đối tượng # 1001) và sau đó nhận ra rằng họ là những thứ khác nhau trong bộ nhớ để đi đến kiểm tra danh sách đệ quy của nó. Nó thực hiện điều này bằng cách lặp qua hai danh sách. Đối tượng # 1001 có một phần tử có chỉ mục 0 trỏ đến đối tượng # 1002. Đối tượng # 1002 có một phần tử có chỉ mục 0 trỏ đến đối tượng # 1001. Do đó, chương trình kết luận rằng đối tượng # 1001 và # 1002 bằng nhau nếu tất cả tham chiếu của chúng trỏ đến cùng một thứ, nếu # 1002 (tham chiếu duy nhất của # 1001 trỏ tới) và # 1001 (điểm tham chiếu duy nhất của # 1002) là giống nhau cả thôi. Kiểm tra bình đẳng này không bao giờ có thể dừng lại. Điều tương tự sẽ xảy ra trong bất kỳ danh sách nào không dừng lại. Bạn có thể làm c = [0]; d = [0]; c[0] = d; d[0] = c và a == c sẽ tăng cùng một lỗi.

>>> a[0] == b 
True 

Như tôi đã đề cập trong đoạn trước, điều này ngay lập tức giải quyết thành sự thật vì Python lấy phím tắt. Không cần so sánh nội dung danh sách vì a[0] trỏ đến đối tượng # 1002 và b trỏ tới đối tượng # 1002. Python phát hiện rằng chúng giống hệt nhau theo nghĩa đen (chúng giống nhau) và thậm chí không bận tâm kiểm tra nội dung.

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

Điều này trở lại là lỗi vì a[0][0] kết thúc trỏ đến đối tượng # 1001. Việc kiểm tra danh tính không thành công và rơi trở lại vào kiểm tra nội dung đệ quy, mà không bao giờ kết thúc.

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

Một lần nữa, a[0][0][0] điểm phản đối # 1002, cũng như b. Việc kiểm tra đệ quy được bỏ qua và so sánh ngay lập tức trả về true.ngựa bất kham mức

---

cao jabber không liên quan trực tiếp đến đoạn mã cụ thể của bạn:

• Vì tất cả có là tài liệu tham khảo đề cập đến đối tượng khác, mặc dù có là những gì dường như là "vô hạn" làm tổ, đối tượng được đề cập bởi a (như tôi đã gọi đối tượng # 1001) và đối tượng được gọi là b (# 1002) đều có cùng kích thước trong bộ nhớ. Và kích thước đó thực sự cực kỳ nhỏ vì tất cả chúng là những danh sách trỏ đến các vị trí bộ nhớ khác tương ứng.
• Cũng cần lưu ý rằng bằng ít ngôn ngữ "hào phóng", so sánh hai tham chiếu với == trả về truechỉ nếu các đối tượng bộ nhớ trỏ đến giống nhau. Java là một ví dụ về điều này. Các quy ước phong cách đã nổi lên trong các ngôn ngữ như vậy là để xác định một phương pháp/chức năng trên các đối tượng mình (đối với Java, nó được gọi là equals()) để thực hiện kiểm tra bình đẳng tùy chỉnh. Python thực hiện điều này trong hộp cho danh sách. Tôi không biết cụ thể về Python, nhưng ít nhất trong Ruby, == bị quá tải theo nghĩa là khi bạn thực hiện someobject == otherobject, nó thực sự gọi một phương thức có tên là == trên someobject (bạn có thể ghi đè). Về lý thuyết, sẽ không có gì ngăn cản bạn thực hiện someobject == otherobject trả lại cái gì đó khác với boolean.

Answer 2

tôi nghi ngờ sau xảy ra:

a[0]==b: Python nhìn lên giá trị a[0] và tìm thấy một số loại tài liệu tham khảo để b, vì vậy nó nói True.

a[0][0]==b: Python nhìn lên a[0], thấy b và bây giờ nhìn lên a[0][0], đó là, (kể từ a[0] giữ b) b[0]. Bây giờ nó thấy, rằng b[0] giữ một số loại tài liệu tham khảo để a, mà không phải là chính xác giống như b. Vì vậy, python phải so sánh các yếu tố, có nghĩa là, nó phải so sánh a[0] với b[0]. Bây giờ, đệ quy vô hạn bắt đầu ...

Lưu ý rằng điều này chỉ hoạt động vì Python không thực sự sao chép danh sách khi gán a[0]=b. Python thay vì tạo một tham chiếu đến b được lưu trữ trong a[0].

Answer 3

Đây là hai danh sách. Trước tiên, bạn tạo ra chúng:

a = [0] 
b = [0] 

Và sau đó, bạn chỉ định mỗi một đến phần tử đầu tiên của một trong những khác:

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

Vì vậy, bạn có thể nói

a[0] is b 

và

b[0] is a 

cùng một vị trí ion là ví dụ đầu tiên, nhưng mức độ obe sâu hơn.

Ngoài ra, bạn không so sánh với danh tính (is), nhưng đối với sự bình đẳng (==). Điều này dẫn đến việc thử so sánh chúng - sâu bên trong, điều dẫn đến một đệ quy.

Answer 4

Tôi thấy, rằng một chứa b, có chứa một

Họ không chứa lẫn nhau như vậy - A là một tham chiếu đến một danh sách, điều đầu tiên trong danh sách này là một tài liệu tham khảo đến B, và ngược lại

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

số lượng [0] 's ở đây không quan trọng, như bạn có thể làm như nhiều tra cứu danh sách theo ý muốn - điều quan trọng là trong ví dụ # 1 và # 3 (và tất cả số lượng tra cứu lẻ) bạn đang nói "bằng B bằng B", tại điểm python so sánh địa chỉ bộ nhớ nd thấy rằng họ là những điều tương tự, do đó, nói có. Với ví dụ # 2 (và tất cả tra cứu) bạn đang nói "là A bằng B", python thấy rằng chúng là các địa chỉ bộ nhớ khác nhau, và sau đó cố gắng tải toàn bộ cấu trúc dữ liệu (vô hạn) vào bộ nhớ để thực hiện thêm so sánh chiều sâu.

Answer 5

a[0] đề cập đến b và b[0] là a. Đây là một tham chiếu vòng tròn. Như glglgl đã đề cập, khi bạn thử toán tử ==, nó sẽ so sánh các giá trị.

Hãy thử điều này, mà có thể làm cho mọi việc rõ ràng hơn -

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