Объяснение алгоритма вычисления входных/выходных переменных в реальном времени

На этом слайде показаны алгоритм вычисления in[n] и out[n] для узла графа потока управления. Хотя мне трудно понять, как это работает. Я видел несколько других вариаций и тоже с трудом их понимаю. Я никогда раньше не имел дела с фиксированной точкой.

for each n
  in[n] := {}; out[n] = {}
repeat
  for each n
    in’[n] := in[n]; out’[n] := out[n]
    in[n] := use[n] ∪ (out[n] - def[n])
    out[n] := ∪ {in[s] | s ε succ[n]}
  until in’[n] = in[n] and out’[n] = out[n]
  for all n

Вопрос в том, что делает этот алгоритм / более интуитивное объяснение этого. Я не понимаю, что такое in' и out' и что означает конечное условие (until in'...). Не следуя вложенным циклам. Моя попытка реализовать JavaScript показывает, где мне не хватает частей:

var in = {}
var out = {}
var in2 = {}
var out2 = {}
var use = {}
var out = {}
var def = {}

for (var i = 0, n = nodes.length; i < n; i++) {
  var node = nodes[i]
  in[node] = []
  out[node] = []
  // assume these are already filled out:
  use[node] = []
  out[node] = []
  def[node] = []
}

while (true) {
  for (var i = 0, n = nodes.length; i < n; i++) {
    var node = nodes[i]
    in2[node] = in[node]
    out2[node] = out[node]
    // assume ∪ and - work on arrays
    in[node] = use[node] ∪ (out[node] - def[node])
    // ? not sure the ∪
    out[node] = ∪ {in[s] | s ε succ[n]}
  }

  // until in’[n] = in[n] and out’[n] = out[n]
  // for all n
}

Любая помощь будет принята с благодарностью. Спасибо.


algorithm graph-theory control-flow-graph
person Lance Pollard    schedule 26.05.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Алгоритм наименьшей фиксированной точки применяется к ситуациям, когда у вас есть конечное число наборов, члены которых происходят из конечной вселенной, и где принадлежность каждого набора (возможно) зависит от принадлежности к другим множествам, в частности, путем включения элементов из определенных других наборов. наборы.

Если зависимости образуют направленный ациклический граф (DAG), то проблем нет; наборы можно вычислить, топологически упорядочив наборы по отношению зависимости, а затем вычислив наборы по порядку. (Из-за топологической сортировки ни один набор не зависит от предыдущего набора, поэтому к тому моменту, когда набор необходимо вычислить, все его зависимости уже вычислены.)

Но если в графе зависимостей есть циклы, топологическая сортировка невозможна, поэтому вместо этого мы используем алгоритм наименьшей фиксированной точки. Начнем с того, что установим все множества пустыми, а затем обработаем их все в определенном порядке. Когда мы подходим к зависимости, мы просто добавляем элементы, которые в данный момент находятся в зависимости. Если какой-либо набор был изменен во время этого цикла, мы снова обрабатываем все наборы. (Не обязательно обрабатывать их в одном и том же порядке, но обычно это самый простой способ.) И мы продолжаем делать это снова и снова, пока не пройдем полный цикл без добавления нового элемента в любой набор. На данный момент мы достигли согласованного набора зависимостей членства («фиксированная точка»), в котором нет посторонних членов (так что это «наименее фиксированная точка»).

Теоретически этот алгоритм может выполняться долго, но он должен завершаться, поскольку каждый цикл включает в себя фиксированное число вычислений набора и (кроме последнего цикла) добавляет к некоторому набору хотя бы один элемент. В худшем случае каждый набор включает в себя каждый элемент, поэтому возможно только конечное число циклов (максимум количество наборов, умноженное на количество элементов). На практике для многих проблемных областей алгоритм работает намного быстрее, либо произведение множеств и элементов не слишком велико (или и то, и другое).

Эти проблемы обычно можно решить, вычислив транзитивное замыкание реляционного уравнения. Поскольку алгоритмы транзитивного замыкания обычно быстрее (как с точки зрения теоретической сложности, так и с точки зрения практического времени выполнения внутреннего цикла), они будут предпочтительным решением, если скорость имеет значение. Однако алгоритм с наименьшими фиксированными точками легче понять, а его код несколько менее загадочен.

В конкретном алгоритме определения живучести установленные отношения зависимости перечислены на предыдущем слайде; вы можете видеть, что каждый набор in и out определяется некоторыми фиксированными элементами и объединением одного или нескольких других наборов. Как показано, алгоритм сохраняет копию всех наборов в начале цикла и сравнивает каждую копию с соответствующим набором в конце цикла. Если какой-либо набор был изменен в течение цикла, алгоритм еще не завершен.

На практике чаще всего просто устанавливают логический флаг в false в начале цикла и в true, если операция объединения приводит к добавлению нового элемента в набор (что легко добавить в операцию объединения, но сложно описать формальным алгоритмом). Затем алгоритм завершает работу, если логическое значение все еще ложно в конце цикла.

person rici    schedule 26.05.2018
comment
Ага! Это было ключом, спасибо. Если какой-либо набор был изменен в течение цикла, алгоритм еще не завершен. - person Lance Pollard; 27.05.2018
comment
Это было очень полезное объяснение. - person Lance Pollard; 27.05.2018
comment
Удивительно :) На практике чаще всего просто устанавливают логический флаг в false в начале цикла и в true, если операция объединения приводит к добавлению нового элемента в набор. - person Lance Pollard; 27.05.2018
comment
Это также было ключевым, если граф зависимостей имеет циклы, топологическая сортировка невозможна, поэтому вместо этого мы используем алгоритм наименьшей фиксированной точки. Кажется, не так много вещей о циклах, большинство вещей касается DAG. - person Lance Pollard; 27.05.2018
comment
@lance: граф зависимостей, о котором я говорю, создан уравнениями для in[n] и out[n] (где левая часть зависит от всего, что находится в правой части). Должно быть ясно, что этот граф зависимостей имеет цикл именно тогда, когда поток, который он представляет, имеет цикл (то есть почти всегда). - person rici; 27.05.2018