Расширение алгоритма оценки дерева выражений - PullRequest
Новая
       64

Расширение алгоритма оценки дерева выражений

0 голосов
/ 10 апреля 2020

Это рекурсивный алгоритм, который я придумал. Я видел примеры алгоритмов, которые похожи на это в книгах. 

f(n)
  if n is an integer
    return n
  else
    l = left child of n
    r = right child of n
    return f(l) n f(r)

1]

Он может использоваться для оценки деревьев выражений, как показано на рисунке слева в выше изображение в течение Θ (n) времени. Пока это все правильно, я хочу расширить его для оценки деревьев выражений, таких как дерево справа, где общие подвыражения дедуплицированы. Я думаю, что алгоритм может правильно оценить эти типы деревьев, но я не уверен, сколько времени это займет. Возможно, какой-то метод хранения поддеревьев следует использовать? Например: 

f(n, A)
  if n is an integer
    return node
  else
    if n has more than 1 parent AND n is in A (A is a list of stored subtrees)
       return n from A
    else
      l = left child of n
      r = right child of n
      s = f(l, A) n f(r, A)
      add s to list A
      return s

Это расширение правильно? Это кажется действительно грязным. Кроме того, у меня есть ощущение, что он будет работать за O (n 2 ), потому что функция будет вызываться на n узлах, и во время каждого вызова ей придется выполнять итерацию по списку сохраненных узлов с верхней границей. из п. Можно ли сделать это лучше, чем в квадрати c раз?

1 Ответ

1 голос
/ 11 апреля 2020

Обработка группы доступности базы данных должна работать нормально, если вы сохраните результат оценки подграфа на узле оператора при первом посещении. Любое последующее посещение этого узла не вызовет рекурсивный вызов для оценки подвыражения, а просто вернет сохраненное значение. Техника называется «запоминание». Время выполнения - это, в основном, число ребер в графе, при условии, что все операторные оценки равны O(1).

Псевдокод: 

f(n)
  if n is an integer
    return n
  else
    if property evalResult of n is defined
       return property evalResult of n
    else
      l = left successor of n
      r = right successor of n
      s = f(l) n f(r)
      set property evalResult of n to s
      return s
...