Ich interessiere mich für die frühe Geschichte der veröffentlichten Ergebnisse zu Allzweck-Raum-Zeit-Kompromissen. Insbesondere möchte ich wissen, wer zuerst die folgende Art von Algorithmus zur Auswertung einer Berechnung mit einem beliebigen Datenflussdiagramm mit Grad O (1) unter Verwendung eines Raums beschrieben hat, der proportional zur Tiefe (nicht Breite) des Datenflussdiagramms (plus der Größe) ist der Eingabe) durch eine einfache Tiefenauswertung des Graphen. Ausführlicher:
Der Datenflussgraph sei G = (V, E), wobei V die Menge der rechnerischen Eckpunkte (O (1) -große Datenwerte) und E die Menge der Kanten (v_p, v_s) ist, so dass der Wert des Nachfolgers Der Scheitelpunkt v_s \ in V hängt unmittelbar vom Wert des Vorgängerscheitelpunkts v_p \ in V ab. Sei v_f der Scheitelpunkt ohne Nachfolger, der das Endergebnis der Berechnung darstellt. Sei ich eine kanonisch geordnete Menge von Eingangsscheitelpunkten (ohne Vorgänger), denn in I ist ihr Wert x (i) gegeben. Für andere Eckpunkte v \ in S werden ihre Werte durch x (v) = F_v (x (P (v))) definiert, wobei P (v) eine kanonisch geordnete Liste der Vorgänger von v ist, x (P (v)) ist die entsprechende Liste ihrer Werte, und F_v ist die Funktion des Scheitelpunkts, die seinen Wert als Funktion der Werteliste seiner Vorgänger bestimmt.
In Anbetracht dieser Konfiguration ist der fragliche Algorithmus ziemlich offensichtlich und trivial:
def eval(v): (v can be any vertex in the graph)
let P := P(v), the list of v's predecessors (has O(1) elements by assumption)
let val[] := uninitialized array of |P| data values
for each predecessor p[i] in P (i.e. for i from 1 to |P|):
if p[i] is in I then
val[i] = x(p) (look up a given input)
else
val[i] = eval(p[i]) (recursive call)
return F_v(val[]) (apply vertex's function to list of predecessor values)
Dies erfordert O (d) Rekursionsebenen, wobei d die Tiefe des Datenflussgraphen ist und der Stapelraum auf jeder Ebene aufgrund der Annahme, dass der Grad des Datenflussgraphen konstant ist und die Größe von konstant ist, konstant ist Die Datenwerte sind konstant. (Der Einfachheit halber behandle ich hier auch die Größe der Vertex-Referenzen als konstant, obwohl sie in | V | wirklich logarithmisch sind.) Daher ist der gesamte Speicherplatzbedarf O (d + | I |). Die maximale Breite des Datenflussgraphen kann exponentiell größer sein, daher kann diese Technik im besten Fall eine ziemlich extreme Platzersparnis im Vergleich zu beispielsweise einer gierigen vorwärts gerichteten Auswertung des Graphen (die an jedem liegen könnte) bieten Schritt, bewerten Sie alle Scheitelpunkte, die direkt nur von Scheitelpunkten abhängen, deren Werte bereits bekannt sind,
Wie auch immer, es ist eine ziemlich offensichtliche Technik, zumindest im Nachhinein, und sie ist sicherlich seit langem bekannt, aber ich habe mich gefragt, wie die Literatur darauf zurückgeht. Jeder kennt die frühe Geschichte solcher Ergebnisse (ob in diesen Begriffen oder in anderen analogen Begriffen beschrieben), und was wäre eine gute Referenz, um sich mit diesem Thema zu befassen?
Vielen Dank, -Mike Frank
quelle