2

Recently I found that python list and dictionary can be nested in multiple level like this

a = {'a1':[{'a2':{'a3':[4,5,6]}}]}

So I'd like to ask is there a technical limit for the nested level? If there isn't, is there a conventional limit for nested level, what's it?

Mario
  • 921
  • 2
  • 10
  • 22

3 Answers3

6

The only limit is memory. Given infinite memory you can nest Python objects infinitely.

Demo:

>>> root = lst = []
>>> levels = 0
>>> while True:
...     lst.append([])
...     lst = lst[-1]
...     levels += 1
...     if levels % 1000000 == 0:  # every 1 million
...         print levels
... 
1000000
2000000
3000000
4000000
5000000
6000000
7000000
8000000
9000000
10000000
11000000
# ....
# [ slower and slower as the system starts to swap ]
# ....
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError

For the sake of my sanity I killed it at 30 million objects though.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
  • I tried this in Idle just for kicks now, and got a "maximum recursion depth exceeded while getting the repr of a list" – WeaselFox Mar 06 '14 at 12:18
  • You can't nest them indefintely in literals, and when writing recursive code to create nested data structures you also have to take the maximum recursion depth into account. – Sven Marnach Mar 06 '14 at 12:20
  • 1
    @WeaselFox: Don't confuse recursion limits when *printing* a nested object with how deep you can stack object references. – Martijn Pieters Mar 06 '14 at 12:20
  • yes, the problem came up when trying to print it.. I see. – WeaselFox Mar 06 '14 at 12:22
2

There's no real limit to how deeply nested a data structure you can create (other than the memory it consumes), but there are limits to how how deeply nested a data structure you can write as a literal in your code. For example, here's a quick test:

>>> eval(70*'['+70*']')
[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
>>> eval(80*'['+80*']')
[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]        
>>> eval(90*'['+90*']')
[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
>>> eval(100*'['+100*']')
s_push: parser stack overflow
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError

That didn't actually run out of total memory, but it ran out of stack space while trying to parse the data structure. You can create lists nested that deep, you just can't write them in your source code directly.

Would you want to? Not normally. Perhaps you want to create a linked list manually. That might be a reason to create a structure that's deeply nested.

Weeble
  • 17,058
  • 3
  • 60
  • 75
1

You can even do infinite loop:

>>> l = [1]
>>> l.append(l)
>>> l
[1, [...]]
>>> l[1][1][1][1][1][1][1][1][1][1][1][1][1][1][1]
[1, [...]]
>>>
hivert
  • 10,579
  • 3
  • 31
  • 56
  • 1
    That's a *self reference*, not stacking distinct objects. – Martijn Pieters Mar 06 '14 at 12:22
  • I think it is relevant: I have a list which contains a nested list which contains a nested list which contains a nested list which contains a nested list which contains a nested list which contains a nested list which contains a nested list... – hivert Mar 06 '14 at 12:24
  • 1
    You have a list that contains a reference to itself. *That is not the same thing*. Cute, but irrelevant here. – Martijn Pieters Mar 06 '14 at 12:29
  • This is the only way to interpret "nesting infinitely" that makes it possible in Python. Even given unbounded memory, the Turing-like Python computation model doesn't otherwise admit an infinitely deep structure. What would construct it, a program that has run for an infinite time? There's no such thing. But of course the question body makes it clear that the questioner doesn't really mean "infinitely" as stated in the title :-) – Steve Jessop Mar 06 '14 at 14:06