Verschachtelungs-Tiefe bei list / dict ?

[10111]

Hallo.

Leider konnte ich nichts passendes finden. Deshalb frage ich euch.

Wie tief kann man Listen / Dictionaries verschachteln? Also z.B. :

Code: Alles auswählen

liste = [1, [2, [3, [4, [x, y]]]]]
verz = {1: {2: {3: {4: [x,y]}}}}

[b.esser-wisser]

Es gibt das "recursion limit", das wird wohl verhindern, dass du unbegrenzt tiefe Geschichten verarbeiten kannst - abgesehen davon kannst du schachteln bis dir der Speicher ausgeht.

Code: Alles auswählen

>>> giant =  elem = []
>>>for i in xrange(100000):
>>>   elem.append([])
>>>   elem = elem[0]
>>> print giant

 # Folgendes geht ja auch (ist 'unbegrenzt' tief):
>>> a = []
>>> a.append(a)

hth, Jörg

[Trundle]

Es kommt (bei CPython) auch darauf an, wie die Listen/Dicts erstellt werden. Erstellt man sie dynamisch, etwa über Py-Code oder C-Code, müsste wohl wie b.esser-wisser bereits sagte der Speicher die Begrenzung sein. Werden die Listen hingegen über normalen Quelltext erstellt, der von CPython geparst wird, hat man da eine Begrenzung, da der Parser intern einen Stack benutzt, der eben begrenzt ist.

Folgender Code wirft bei mir (Python 2.5) z.B. einen `MemoryError`:

Code: Alles auswählen

eval('[' * 34 + ']' * 34)

Mit 33 wird der Code noch geparst.

[10111]

Danke für eure Antworten.

Habe so an eine Tiefe von 16 - 20 gedacht. Sollte also wohl möglich sein.

[Leonidas]

Habe so an eine Tiefe von 16 - 20 gedacht.

Das wird aber ein kurzes Lisp-Programm.

[sma]

Folgender Code wirft bei mir (Python 2.5) z.B. einen `MemoryError`:

Code: Alles auswählen

eval('[' * 34 + ']' * 34)

Mit 33 wird der Code noch geparst.

Wie erbärmlich ist denn das? Ein

Code: Alles auswählen

eval("("*33 + "42" + ")" * 33)

geht auch schon nicht mehr.

Python 3.0 kommt immerhin bis 93 bevor "s_push" einen "parser stack overflow" meldet. Hier ist der Code, der das bei Python 2.5 beeinflusst: http://www.google.com/codesearch/p?hl=d ... ser.c&l=42. Man hat hier http://www.google.com/codesearch/p?hl=d ... ser.h&l=10 den Stack willkürlich auf 500 Elemente festgesetzt und offenbar addiert sich das dann irgendwie auf.

Stefan

[10111]

@Leonidas: Sollte eigentlich ein binärer Baum werden. Aber vielleicht gibt es da auch bessere Möglichkeiten. Da ich so etwas leider noch nie programmiert habe, überlege ich erstmal in alle Richtungen.
Vielleicht ist eine Klasse mit einer Liste mit Folge-Elementen geeigneter?

[Hyperion]

@Leonidas: Sollte eigentlich ein binärer Baum werden. Aber vielleicht gibt es da auch bessere Möglichkeiten. Da ich so etwas leider noch nie programmiert habe, überlege ich erstmal in alle Richtungen.
Vielleicht ist eine Klasse mit einer Liste mit Folge-Elementen geeigneter?

Könnte man auch über ein dict lösen:

Code: Alles auswählen

# dict: key = Node, values = children
btree = {1: [2, 3], 2: [4], 3: None, 4: None}

Aber ich denke ne Klasse kann hier schon besser sein, weil der Zugriff / Traversierung dann intern implementiert werden kann und nicht von außerhalb draufgeproft werden muss. Außerdem fehlen dem Baum hier noch die Datencontainer

Mir fällt grad ein, dass die Unterscheidung von links und rechts ja durchaus eine wichtige Rolle spielen kann, das wäre hier irgend wie häßlich, da man für die Unterscheidung ggf. ein [None, x] basteln müßte.

Alternativ ein dict von dicts:

Code: Alles auswählen

# dict: key = Node, values = dict with "r", and "l" keys
btree = {1: {"r": 2, "l": 3}, 2: {"l": 4}, 3: None, 4: None}

Hm ... naja, führt nicht zu wirklich was ...

[Leonidas]

Sollte eigentlich ein binärer Baum werden.

Und diesen willst du einfach so im Quelltext drin stehen haben?

Für Bäume würde ich mir dennoch warscheinlich zumindest eine Node-Klasse schreiben und das über verkettete Nodes lösen. Schon allein weil das semantisch mehr her macht als tief verschachtelte Listen.

[10111]

Danke für eure Tipps.

@Leonidas: Natürlich will ich den Baum erst zur Laufzeit erstellen. Auch scheint es mir einfacher mit einer Node-Klasse zu sein, sich da durchzuhangeln. Bei einer tief geschachtelten Liste (oder Dict) könnte das etwas kompliziert werden.

[cofi]

Bei einer tief geschachtelten Liste (oder Dict) könnte das etwas kompliziert werden.

Ach wieso denn?
`tree[1][0][0][1][0][0][0][1][0][1]' sieht doch toll aus? SCNR

[b.esser-wisser]

...und der default-Wert für das Rekursionslimit liegt bei 1000, für so einen großen Baum hast du gar keinen Platz

Code: Alles auswählen

def list_tree(depth=10, l=None):
    """Erzeigt einen vollen Binaerbaum aus Listen, <depth> Ebenen tief

    bleibt die Frage: wozu?""" 
    if depth >0:
        if l is None: l=[]
        l.append(list_tree(depth-1))
        l.append(list_tree(depth-1))
    else:
        l = [None]
    return l
tree= list_tree(16) # ab ca. 30 wird es erst spannend
print tree[0][0][0][0][0][0][0][0][0][0][0][0][0][0][0]

hth, Jörg