Я интересуюсь ранней историей опубликованных результатов о пространственно-временных компромиссах общего назначения. В частности, я хочу знать, кто первым описал следующий тип алгоритма для вычисления вычисления, имеющего произвольный граф потока данных с степенью O (1), используя пространство, пропорциональное глубине (не ширине) графа потока данных (плюс размер ввода), выполняя прямую оценку глубины в первую очередь графика. Подробнее:
Пусть граф потока данных имеет вид G = (V, E), где V - это множество вычислительных вершин (значения данных размера O (1)), а E - это множество ребер (v_p, v_s), так что значение преемника вершина v_s \ in V напрямую зависит от значения предшествующей вершины v_p \ in V. Пусть v_f будет вершина без преемников, представляющих конечный результат вычисления. Пусть я - канонически упорядоченный набор входных вершин (без предшественников), для i \ in I задано его значение x (i). Для других вершин v \ in S их значения определяются как x (v) = F_v (x (P (v))), где P (v) - канонически упорядоченный список предшественников v, x (P (v)) - соответствующий список их значений, а F_v - это функция вершины, которая определяет ее значение как функцию списка значений ее предшественников.
Учитывая эту настройку, рассматриваемый алгоритм довольно очевиден и тривиален:
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)
Это требует O (d) уровней рекурсии, где d - глубина графа потока данных, а пространство стека на каждом уровне является постоянным из-за допущений, что степень степени графа потока данных постоянна, и что размер значения данных постоянны. (Для простоты здесь я также рассматриваю размер ссылок на вершины как постоянный, даже если они действительно логарифмичны в | V |.) Таким образом, общее использование пространства равно O (d + | I |). Максимальная ширина графа потока данных может быть экспоненциально больше, чем этот, поэтому в лучшем случае этот метод может обеспечить довольно большую экономию пространства по сравнению, скажем, с жадной прямой оценкой графа (который может быть на каждом шаг, оцените все вершины, которые напрямую зависят только от вершин, значения которых уже известны,
Во всяком случае, это довольно очевидная техника, по крайней мере, в ретроспективе, и она, конечно, давно известна, но мне было интересно, как обстоят дела с литературой о ней. Кто-нибудь знает раннюю историю результатов такого рода (описанных в этих терминах или других аналогичных), и что было бы хорошим ориентиром для изучения этого вопроса?
Большое спасибо, Майк Фрэнк