Приветствую,
Стала подобная проблема:
Есть некоторая зависимость выражений, например
А и Б — ни от кого не зависят
С зависит от Б
Д зависит от А и С
и т.д.
необходимо вычислить все выражения в таком порядке, что когда начинаю вычислять определенное выражение (напр. Д) то те от которых он зависит( А и С) к этому моменту будут уже вычислены. Иными словами, требуется алгоритм нахождения порядка вычисления.
Думаю, что не первый кто столкнулся с подобной проблемой, но пока ничего действительно хорошего не нашел
Помогите, пожалуйста, кто знает

С уважением
Павел

Здравствуйте, Аноним, Вы писали:

А>Приветствую,
А>Стала подобная проблема:
А>Есть некоторая зависимость выражений, например
А>А и Б — ни от кого не зависят
А>С зависит от Б
А>Д зависит от А и С
А>и т.д.
А>необходимо вычислить все выражения в таком порядке, что когда начинаю вычислять определенное выражение (напр. Д) то те от которых он зависит( А и С) к этому моменту будут уже вычислены. Иными словами, требуется алгоритм нахождения порядка вычисления.
А>Думаю, что не первый кто столкнулся с подобной проблемой, но пока ничего действительно хорошего не нашел
А>Помогите, пожалуйста, кто знает

А>С уважением
А>Павел

Поиск где угодно по ключевому слову "топологическая сортировка". Например, на algolist.manual.ru

Здравствуйте, <Аноним>, Вы писали:

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

Здравствуйте, Аноним, Вы писали:

А почему бы не вычилять по требованию? То есть типа так

int calculate()
 {
  static bool is_caculated = false;
  static int precalulated_result;

  if (!is_calculated)
  {
    precalculated_result = .... /* тут и вычисляем */

    is_calculated = true;
  }

  return precalculated_result;
 }

Тогда

1) всё вычислится в порядке учитывающем зависимости
2) каждый результат будет вычисляться только 1 раз
3) результаты которые в некоторой ситуации не нужны вычислены не будут
4) никаких сортировок не надо, всё делается само.

Здравствуйте, Аноним, Вы писали:

А>Приветствую,
А>Стала подобная проблема:
А>Есть некоторая зависимость выражений, например
А>А и Б — ни от кого не зависят
А>С зависит от Б
А>Д зависит от А и С
А>и т.д.
А>необходимо вычислить все выражения в таком порядке, что когда начинаю вычислять определенное выражение (напр. Д) то те от которых он зависит( А и С) к этому моменту будут уже вычислены. Иными словами, требуется алгоритм нахождения порядка вычисления.
А>Думаю, что не первый кто столкнулся с подобной проблемой, но пока ничего действительно хорошего не нашел
А>Помогите, пожалуйста, кто знает

А>С уважением
А>Павел

топологическая сортировка

Здравствуйте, adontz, Вы писали:

A>Здравствуйте, Аноним, Вы писали:

A>А почему бы не вычилять по требованию? То есть типа так
A>

A>int calculate()
A> {
A>  static bool is_caculated = false;
A>  static int precalulated_result;

A>  if (!is_calculated)
A>  {
A>    precalculated_result = .... /* тут и вычисляем */

A>    is_calculated = true;
A>  }

A>  return precalculated_result;
A> }
A>

A>Тогда

A>1) всё вычислится в порядке учитывающем зависимости
A>2) каждый результат будет вычисляться только 1 раз
A>3) результаты которые в некоторой ситуации не нужны вычислены не будут
A>4) никаких сортировок не надо, всё делается само.

Это здорово, если есть уверенность в правильности исходных данных. А если там цикл?

Здравствуйте, VsevolodC, Вы писали:


VC>Это здорово, если есть уверенность в правильности исходных данных. А если там цикл?

Вначале надо поверить выражение на отсутствие циклов. Потом можно уже вычислять.

Здравствуйте, Аноним, Вы писали:

А>Приветствую,
А>Стала подобная проблема:
А>Есть некоторая зависимость выражений, например
А>А и Б — ни от кого не зависят
А>С зависит от Б
А>Д зависит от А и С
А>и т.д.
А>необходимо вычислить все выражения в таком порядке, что когда начинаю вычислять определенное выражение (напр. Д) то те от которых он зависит( А и С) к этому моменту будут уже вычислены. Иными словами, требуется алгоритм нахождения порядка вычисления.
А>Думаю, что не первый кто столкнулся с подобной проблемой, но пока ничего действительно хорошего не нашел
А>Помогите, пожалуйста, кто знает

А>С уважением
А>Павел

Как это делал я:
1. строим матрицу зависимостей выражений — допустим так

  
  A B C
A 0 1 0
B 0 0 1
C 0 0 0

Согласно этой матрице а зависит от в, в зависит от с.

2. Далее находим вектор у которого все нолики -- т.е. соответствующее выражение не зависит от других.
3. Удаляем строку и столбец, соответствующие этому выражению, а само выражение добавляем в вектор выражений
4. Пункты 2 и 3 повторяем количество раз равное количеству выражений.

Если после данной процедуры в векторе выражений их количество меньше изначального, значит среди них есть циклы.

У этого алгоритма две проблемы
1. Он определяет только присутствие циклов но не находит сами циклы.
2. сложность — О(n^3) — не учитывая время на удаление элементов матрицы.
Элементы можно не удалять, а завести вектор удаленных выражений.

З.Ы. Алгоритм был придуман на скорую руку, так что прошу сильно не критиковать.
З.З.Ы. Предложите оптимизацию, буду очень благодарен.

Здравствуйте, VsevolodC, Вы писали:

VC>Здравствуйте, adontz, Вы писали:

A>>Здравствуйте, Аноним, Вы писали:

A>>А почему бы не вычилять по требованию? То есть типа так
A>>

A>>int calculate()
A>> {
A>>  static bool is_caculated = false;
A>>  static int precalulated_result;

A>>  if (!is_calculated)
A>>  {
A>>    precalculated_result = .... /* тут и вычисляем */

A>>    is_calculated = true;
A>>  }

A>>  return precalculated_result;
A>> }
A>>

A>>Тогда

A>>1) всё вычислится в порядке учитывающем зависимости
A>>2) каждый результат будет вычисляться только 1 раз
A>>3) результаты которые в некоторой ситуации не нужны вычислены не будут
A>>4) никаких сортировок не надо, всё делается само.

VC>Это здорово, если есть уверенность в правильности исходных данных. А если там цикл?

Вот это обнаружит заодно и цикл.

    void calculate(Expression e) {
        if (inProgress[e]) throw "Circular dependency detected";
        if (e.value hasn't been calculated yet) {
            inProgress[e] = true;
            foreach dep in e.dependencies {
                calculate(dep);
            }
            inProgress[e] = false;
            e.value = e.evaluate();
        }
    }