Das deutsche Python-Forum

Hallo,

ich habe eine Datenstruktur, die ein wenig einem Graphen ähnelt. Für die Darstellung in Python nutze ich der Lesbarkeit halber allerdings Knoten-Objekte und keine adjacency matrix. Der Graph ist ungerichtet, d.h. wenn Knoten A Nachbar von Knoten B ist, dann haben beide eine Referenz des anderen in ihrer Nachbarschaftsliste.
Das Problem tritt nun auf, wenn ich diese Struktur in ein Django-Sessionobjekt speichere. Zum einfacheren Debuggen habe ich versucht die Liste von Knoten zu pickeln (unter der Annahme, dass Django genau das tut). Dies gibt mir einen AssertionError und folgende Fehlermeldung sowie einen sehr tiefen traceback:

Code: Alles auswählen

c:\Python26\lib\pickle.py in memoize, line 244

Kennt jemand zufällig dieses Problem und wie kann ich es lösen? Ich bin nicht unbedingt auf pickle angewiesen, d.h. ich kann auch andere Serialisier benutzen (und dann evtl. mit Django pickeln).

Ein kurzer Test mit yaml brachte leider keine Besserung (dump erstellen hat funktioniert, aber das dekodieren dauerte ewig, sodass ich eine Endlosschleife vermute).

Die Knoten-Struktur ändern möchte ich mir ersparen, wenn irgendwie möglich...

Nehmen wir mal den simplen Graphen A <--> B (A kennt B und B kennt A, da ungerichtet und allwissend)

Du solltest vor dem Pickeln mindestens eine der beiden Verbindungen kappen, damit keine zirkulären Abhängigkeiten entstehen. Nach dem Pickeln kannst du sie wieder her stellen. Das einfachste wäre, wenn deine Knoten eine absolute Ordnung hätten (A<B). Dann könntest du z.B. immer die Verbindung vom Kleineren zum Größeren kappen.

Ungetestetes Beispiel:

Code: Alles auswählen

class Node(object):
  def __init__(self):
    self.friends = []
  def __getstate__(self):
    friends = [f for f in self.friends if f<self]
    return {'friends':friends}
  def __setstate__(self, state):
    self.friends = state['friends']
    for friend in self.friends:
      if friend < self:
        friend.friends.append(self)

@lunas: Grundsätzlich hat `pickle `mit rekursiven Verweisen kein Problem, der Rat von Defnull sollte also überflüssig sein:

Code: Alles auswählen

In [197]: a, b = Node(), Node()

In [198]: a.other = b

In [199]: b.other = a

In [200]: print pickle.dumps([a, b])
(lp0
ccopy_reg
_reconstructor
p1
(c__main__
Node
p2
c__builtin__
object
p3
Ntp4
Rp5
(dp6
S'other'
p7
g1
(g2
g3
Ntp8
Rp9
(dp10
g7
g5
sbsbag9
a.

Da muss also irgend etwas "besonderes" bei Dir vorliegen, was vielleicht einen Fehler in der `pickle`-Implementierung sichtbar macht!?

BlackJack hat geschrieben:Da muss also irgend etwas "besonderes" bei Dir vorliegen, was vielleicht einen Fehler in der `pickle`-Implementierung sichtbar macht!?

Ich tippe mal Blind auf die Rekursionstiefe. A <-> B geht vielleicht, da Pickle sich alle Knoten gut merken kann, aber bei einem Graphen von 1000+ Nodes wird das schon langsam schwierig. Ich vermute stark, das Pickle, genau wie der GC von Python, nur mit Kreisabhängigkeiten bis zu einer bestimmten Größe fertig wird.

Generell wird Pickle sehr langsam, sobald viele verschachtelte Objekte serialisiert werden sollen. Da du mit Django arbeitest und von Sessions redest, vermute ich mal, das ein paar Sekunden deserialisieren pro Seitenaufruf nicht so ideal sind. Vielleicht solltest du dir Gedanken machen, wie du deinen Graphen besser serialisieren* kannst oder unserialisiert im Speicher hältst.

* Bei einem meiner Projekte hat es sich z.B als sehr sinnvoll erwiesen, eine lange Liste mit Strings vor dem Serialisieren mit join() zu einem zusammen zu fügen und später mit split() wieder zu trennen, da dies deutlich schneller ging als das pickeln der Liste.

Ja, das kann schon sein, dass mein Objektmodell nicht so astrein ist. Ich werde es wohl mal zerlegen müssen und die Einzelteile unter die Lupe nehmen (schade, dachte ich könnte es auf pickle schieben und einfach etwas anderes benutzen...).

Vielen Dank euch beiden.

lunas

Das deutsche Python-Forum

Rekursives Objekt serialisieren

Rekursives Objekt serialisieren