Je m'intéresse à la première histoire des résultats publiés sur les compromis spatio-temporels à usage général. En particulier, je veux savoir qui a décrit en premier le type d'algorithme suivant pour évaluer un calcul ayant un graphique de flux de données arbitraire avec en degré O (1) en utilisant un espace proportionnel à la profondeur (pas la largeur) du graphique de flux de données (plus la taille de l'entrée) en effectuant une évaluation directe en profondeur du graphique. Plus en détail:
Soit le graphique de flux de données G = (V, E) où V est l'ensemble des sommets de calcul (O (1) -taille des données) et E est l'ensemble des arêtes (v_p, v_s), de sorte que la valeur du successeur le sommet v_s \ dans V dépend immédiatement de la valeur du sommet prédécesseur v_p \ dans V. Soit v_f le sommet sans successeurs représentant le résultat final du calcul. Soit I un ensemble de sommets d'entrée canoniquement ordonné (sans prédécesseurs), pour i \ in I sa valeur x (i) est donnée. Pour les autres sommets v \ dans S, leurs valeurs sont définies par x (v) = F_v (x (P (v))) où P (v) est une liste canoniquement ordonnée des prédécesseurs de v, x (P (v)) est la liste correspondante de leurs valeurs, et F_v est la fonction du sommet qui détermine sa valeur en fonction de la liste de valeurs de ses prédécesseurs.
Compte tenu de cette configuration, l'algorithme en question est assez évident et 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)
Cela prend O (d) niveaux de récursivité, où d est la profondeur du graphique de flux de données, et l'espace de pile à chaque niveau est constant en raison de l'hypothèse que le degré du graphique de flux de données est constant et que la taille de les valeurs des données sont constantes. (Par souci de simplicité ici, je traite également la taille des références de sommets, même si elles sont vraiment logarithmiques dans | V |.) Ainsi, l'espace total utilisé est O (d + | I |). La largeur maximale du graphique de flux de données peut être exponentiellement plus grande que cela, donc dans le meilleur des cas, cette technique peut fournir des économies d'espace assez extrêmes, en comparaison, par exemple, à une évaluation avant avide du graphique (qui pourrait être, à chaque étape, évaluer tous les sommets qui ne dépendent directement que des sommets dont les valeurs sont déjà connues,
Quoi qu'il en soit, c'est une technique assez évidente, du moins rétrospectivement, et elle est certainement connue depuis longtemps, mais je me demandais à quoi remontait la littérature à ce sujet. Quelqu'un connaît l'histoire des premiers résultats de ce type (qu'ils soient décrits dans ces termes ou d'autres analogues), et quelle serait une bonne référence pour creuser ce sujet?
Merci beaucoup, -Mike Frank
la source