Warum ist das DP?
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Code-Selektion mit dynamischer Programmierung
Hallo,
Ich verstehe die Erklaerung auf Folie 09-14, warum das Verfahren DP ist, ueberhaupt nicht.
Geht es nicht einfach darum, dass man sich die “Zwischenergebnisse” der Kinder merkt und merhmals benutzt, ohne sie mehrmals zu berechnen?
Warum sagt die Folie, dass man nicht nur die Kostenvektoren der direkten Nachfolger betrachtet?
Und was genau ist mit identischen Teilbaeumen gemeint?
Die Folie finde ich auch etwas undeutlich formuliert, aber hier mal ein paar Gedanken dazu.
Für jeden Teilbaum müssen ja alle möglichen Befehle durchprobiert werden, mit denen die Operation in der Wurzel durchgeführt werden können. Bei einem naiven rekursiven Verfahren würde man deshalb die Kostenvektoren jedes Kindes mehrfach berechnen, nämlich einmal für jeden Befehl. Das pflanzt sich natürlich rekursiv fort: Für die Berechnung des Vektors im Kind müsste man erneut die Kostenvektoren der eigenen Kinder berechnen usw. Damit man Arbeit nicht mehrfach macht, wendet man DP an. Durch die Bottom-Up-Berechnung im Ausdrucksbaum ist sichergestellt, dass alle Kostenvektoren, die zur Berechnung eines neuen Kostenvektors notwendig sind, bereits berechnet wurden.
Das mit den identischen Teilbäumen ist mir an der Stelle leider auch nicht ganz klar. Was ich mir vorstellen kann: Mittels Compiler-Analysen kann man Teilausdrücke feststellen, die mehrfach berechnet werden. Statt diese Ausdrücke nun tatsächlich mehrfach auszuwerten, kann man diese einmalig berechnen und das Ergebnis sichern (Voraussetzung ist, dass der Teilbaum (und ggf. andere Teilbäume) keine Seiteneffekte hat). Auch hier sorgt die DP dafür, dass man den Kostenvektor für diesen Teilbaum nur einmal berechnen muss. Weil man das Register, in das man das Ergebnis bei der Berechnung ggf. sichert, später für die Auswertung anderer Teilbäume braucht, muss man den Wert in den Speicher schreiben und später wieder laden.
Mit identischen Teilbäumen verliert das Verfahren dann aber seine Optimalität oder? Weil es könnte dann ja sein, dass die beiden identischen Teilbäume in ein Register gespeichert werden, weil es zwar individuell billiger ist, aber es wäre besser den Teilbaum nur einmal in den Speicher zu schreiben und dann zwei mal zu laden?
Im 3. Durchlauf wird dann ja schließlich wirklich Code erzeugt. Auf den Folien steht nur, dass das top-down geschieht (09-16). Das passiert dann aber auch in post-order oder? Also erstmal Code erzeugen für linken Unterbaum, dann für den rechten und schließlich die Operation selber erzeugen.
Ja. Gemeinsame Teilausdrücke machen aus dem Baum einen DAG und die optimale Code-Generierung für DAGs ist NP-vollständig. Man wendet deshalb eine Vereinfachung an, indem jeder Teilbaum des DAGs „herausgeschnitten“ und einzeln behandelt wird (vgl. 08-57).
Post-order, aber nicht notwendigerweise in dieser Reihenfolge. Wenn es die Sprache erlaubt, bei kommutativen Operationen die Reihenfolge der Teilausdrücke zu tauschen, dann werden bei der Bestimmung der Kostenvektoren ja beide Reihenfolgen durchprobiert. In diesem Fall merkt man sich zusätzlich zu den Kosten und der gewählten Instruktion auch noch die Reihenfolge (also ob zuerst das linke oder zuerst das rechte Kind besucht werden muss) und generiert dann eben Code in dieser Reihenfolge.