Verschachtelungs-Tiefe bei list / dict ?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
10111
User
Beiträge: 22
Registriert: Samstag 21. Februar 2009, 01:34

Dienstag 31. März 2009, 15:11

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]}}}}
Benutzeravatar
b.esser-wisser
User
Beiträge: 272
Registriert: Freitag 20. Februar 2009, 14:21
Wohnort: Bundeshauptstadt B.

Dienstag 31. März 2009, 15:46

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
Wir haben schon 10% vom 21. Jahrhundert hinter uns!
Benutzeravatar
Trundle
User
Beiträge: 591
Registriert: Dienstag 3. Juli 2007, 16:45

Dienstag 31. März 2009, 15:56

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.
"Der Dumme erwartet viel. Der Denkende sagt wenig." ("Herr Keuner" -- Bertolt Brecht)
10111
User
Beiträge: 22
Registriert: Samstag 21. Februar 2009, 01:34

Dienstag 31. März 2009, 22:42

Danke für eure Antworten.

Habe so an eine Tiefe von 16 - 20 gedacht. Sollte also wohl möglich sein. :)
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 1. April 2009, 08:59

10111 hat geschrieben:Habe so an eine Tiefe von 16 - 20 gedacht.
Das wird aber ein kurzes Lisp-Programm. 8)
My god, it's full of CARs! | Leonidasvoice vs Modvoice
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Mittwoch 1. April 2009, 09:34

Trundle hat geschrieben: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
User
Beiträge: 22
Registriert: Samstag 21. Februar 2009, 01:34

Mittwoch 1. April 2009, 11:40

@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?
Benutzeravatar
Hyperion
Moderator
Beiträge: 7472
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Mittwoch 1. April 2009, 12:10

10111 hat geschrieben:@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 :-D

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
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 1. April 2009, 18:25

10111 hat geschrieben: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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
10111
User
Beiträge: 22
Registriert: Samstag 21. Februar 2009, 01:34

Donnerstag 2. April 2009, 04:47

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. :?
Benutzeravatar
cofi
Moderator
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Donnerstag 2. April 2009, 13:19

10111 hat geschrieben: 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 :twisted:
Benutzeravatar
b.esser-wisser
User
Beiträge: 272
Registriert: Freitag 20. Februar 2009, 14:21
Wohnort: Bundeshauptstadt B.

Donnerstag 2. April 2009, 13:57

...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
Wir haben schon 10% vom 21. Jahrhundert hinter uns!
Antworten