Effiziente Baumstruktur (CModul?)

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
Benutzeravatar
Defnull
User
Beiträge: 778
Registriert: Donnerstag 18. Juni 2009, 22:09
Wohnort: Göttingen
Kontaktdaten:

Donnerstag 7. Januar 2010, 22:58

Ich bin auf der Suche nach einer effizienten Implementierung für Operationen auf sehr großen Baumstrukturen in Python, kann aber keine anständige Bibliothek dafür finden. Ideal wäre ein C-Modul, das es aber erlaubt, die Baum-Knoten mit zusätzlichen Attributen zu erweitern und schnelle import/export Möglichkeiten bietet. XML vielleicht?

Ich möchte:
* Binäre und tertiäre geordnete Bäume mit bis zu 50000 Blättern im Speicher halten
* alle Knoten eines Unterbaums finden (möglichst per iterator)
* alle Blätter eines Unterbaums finden (möglichst per iterator)
* alle Knoten vom Aktuellen bis zur Wurzel finden (Wurzel-Pfad)
* Blätter nummerieren (bei geordneten Bäumen) und sortieren (nach Tiefe und/oder Nummer)
* Unterbäume ein-, aus- und umhängen
* Knoten mit zusätzlichen Informationen versehen (Farbe, Gewicht, Position) oder wenigstens eine ID mit führen, damit ich die Infos separat vorhalten kann.

Meine Python-Implementierung funktioniert zwar, bedient sich aber hässlicher caching-Tricks, um die Rekursionen in Grenzen zu halten und bremst das Skript ziemlich aus.

Ziel ist es, diese Web Applikation etwas zu Beschleunigen.

Hat jemand ne Idee? Ram ist übrigens kein Problem, 64GB sollten reichen.
Bottle: Micro Web Framework + Development Blog
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Donnerstag 7. Januar 2010, 23:51

Ich kann zwar deine Frage nicht beantworten, aber wie groß ist denn dein Baum absolut? 50000 Blätter wären bei einem vollständigen Binärbaum ist ja nicht so viel. Das kriegt man eigentlich auch mit Python noch gut gehandelt __slots__ spart bei sowas auch massiv Speicher.
Benutzeravatar
Defnull
User
Beiträge: 778
Registriert: Donnerstag 18. Juni 2009, 22:09
Wohnort: Göttingen
Kontaktdaten:

Freitag 8. Januar 2010, 09:56

Es funktioniert ja auch mit Python (__slots__ verwende ich schon) allerdings nicht besonders schnell. Ich rendere den Baum in Echtzeit mit cairo, da bremsen die rekursiven Aufrufe ziemlich aus (zumindest sagt mir das hotshot). Selbst so simple Aufrufe wie dieser hier:

Code: Alles auswählen

class Tree(object):
    ...
    def allchilds(self):
        if not self._allchilds:
            for c in self.childs:
                self._allchilds += c.allchilds() + [c]
        return self._allchilds 
Mein aktueller Workaround ist folgender:
Ich berechne das Layout des Baumes ein einziges mal und speichere es in Listen von horizontalen und vertikalen Linien sowie Text-Elementen mit zugehöriger BoundingBox. Dann durchlaufe ich nur noch diese Listen statt den Baum, um cairo damit zu füttern. Bei jeder Änderung des Baumes muss ich das allerdings nochmal neu berechnen. Der Layout-Routine greift viel auf diese rekursiven Baum-Operationen zu und dauert mit über 1200ms schlicht zu lange für eine interaktive Applikation.
Bottle: Micro Web Framework + Development Blog
BlackJack

Freitag 8. Januar 2010, 11:02

@Defnull: Was mir jetzt speziell an dem Schnippsel auffällt ist das ``liste + [c]`` -- Dir ist klar, dass das ``+`` bei Listen eine *neue* Liste erstellt und die beiden alten dort hinein kopiert!?

Wie sieht's mit der Geschwindigkeit mit Psyco oder Cython aus?

Ach ja: Mehrzahl von "child" ist "children". :-)
lunar

Freitag 8. Januar 2010, 11:17

Musst Du den Baum denn zwingend selbst verwalten? Wenn ich mich richtig erinnere, gibt es Python-Anbindungen für Graphviz. Vielleicht ist es ja möglich, den Baum über Graphviz aufzubauen, in eine Grafik zu rendern und diese dann anzuzeigen.
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Freitag 8. Januar 2010, 21:49

Defnull hat geschrieben:Es funktioniert ja auch mit Python (__slots__ verwende ich schon) allerdings nicht besonders schnell. Ich rendere den Baum in Echtzeit mit cairo, da bremsen die rekursiven Aufrufe ziemlich aus (zumindest sagt mir das hotshot). Selbst so simple Aufrufe wie dieser hier:

Code: Alles auswählen

class Tree(object):
    ...
    def allchilds(self):
        if not self._allchilds:
            for c in self.childs:
                self._allchilds += c.allchilds() + [c]
        return self._allchilds 
Schneller und ohne Rekursion wäre so etwas(allerdings in „pre-ordner“):

Code: Alles auswählen


    def pre_order(self):
        stack = deque([self])
        while stack:
            top = stack.pop()
            yield top
            for child in top.children:
                stack.append(child)
Benutzeravatar
noisefloor
User
Beiträge: 2763
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: Görgeshausen
Kontaktdaten:

Freitag 8. Januar 2010, 21:56

Hallo,
Wenn ich mich richtig erinnere, gibt es Python-Anbindungen für Graphviz.
Richtig, sogar mehrere. Siehe z.B. http://code.google.com/p/pydot/ und http://www.graphviz.org/Resources.php.

Unter Debian / Ubuntu gibt's die Pakete python-pydot, python-pygraph, python-pygraphviz und python-yapgvb.

Die Idee ist BTW gar nicht schlecht - schließlich ist Graphviz auf sowas spezialisiert.

Gruß, noisefloor
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Samstag 9. Januar 2010, 00:24

Darii hat geschrieben:

Code: Alles auswählen

            for child in top.children:
                stack.append(child)
``stack.extend(top.children)``?
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Samstag 9. Januar 2010, 09:09

birkenfeld hat geschrieben:``stack.extend(top.children)``?
Das wär zu einfach. ;)
Antworten