5

Доброго времени суток!

Столкнулся с такой задачей: есть n уравнений, записанных в символьном виде, необходимо оптимизировать количество операций для их вычисления (пока для простоты подразумевается только сложение). Вот пример:

Исходная система уравнений:

x1 = a + b + c
x2 = a + d + c
x3 = a + e + c

В результате должно получиться следующее:

r1 = a + c
x1 = r1 + b
x2 = r1 + d
x3 = r1 + e

Здесь r1 - это замена повторяющейся операции a + b. Легко видеть, что количество сложений уменьшилось с 6 до 4. Все это хорошо, но с маленькими уравнениями, а вот когда количество переменных переваливает за несколько сотен - надо писать программу. Реализовывать алгоритм мне необходимо на C/C++.

После длительного гугления, я выяснил что это называется common subexpression elimination (или удаление общих подвыражений). Однако, как написать программу или каким именно методом такое можно реализовать я так и не понял. И поэтому придумал свой велоспед. Суть велосипеда в следующем: Входными данными является набор строк. Каждая строка представляет собой одно уравнение, например: abc - это x1 = a + b + c Алгоритм действий следующий:

1) упорядочиваем все переменные всех уравнений (ибо он могут быть записаны не по порядку)

2) создаем для каждого уравнения битовый вектор

3) Используя побитовый AND складываем все уравнения и ищем вектор с максимальным количеством установленных бит

4) Добавляем новое уравнение составленное из бит полученных на предыдущем шаге

5) Повторяем все шаги пока не получим нулевой вектор

Я сильно сомневаюсь, что иду правильным путем. Подскажите, пожалуйста, может кто-то сталкивался с подобными алгоритмами, или натолкнете на идею/книгу/библиотеку?

P.S. Сорри если сумбурно, я уже совсем замучался((

1 ответ 1

6

Смотрите, это делается, например, так.

  1. Для начала, для преобразований кода вам нужно распарсить его в syntax tree, или в ещё более удобное представление (например, semantic tree). (Это самая лёгкая часть, вам всё равно это понадобится.)
  2. Суммы переведите из бинарных в n-арные операции. Если одно из слагаемых — сумма, уберите его и добавьте его подслагаемые. То же с разностями. Установите канонический порядок на слагаемых, чтобы не различать x + 3 и 3 + x.
  3. Составляете список всех подвыражений в дереве путём его рекурсивного обхода.
  4. Далее вам нужно ввести порядок на выражениях. Например, вы можете написать хэш-функцию такую, чтобы одинаковые подвыражения обязательно получали одинаковое значение. (Если вы определите хэш-функцию рекурсивно, будет как раз то, что надо.)
  5. Вычислите значения хэша на каждом подвыражении (опять-таки рекурсивно). Отсортируйте список по хэшу.
  6. Рассматривайте (относительно маленькие) группы с одинаковым хэшем. Определите рекурсивно равенство выражений:
    • высоты деревьев не равны => подвыражения не равны
    • типы корней не совпадают => подвыражения не равны
    • поддеревья не совпадают => подвыражения не равны
    • иначе равны
  7. Таким образом, получите список одинаковых подвыражений.
  8. Поскольку суммы можно разделить на части по-разному, вычисляйте хэши также для частичных сумм. Достаточно отсортировать слагаемые, и вычислить 2^n вариантов (включая/не включая каждое из слагаемых). Эти частичные суммы тоже добавляйте в список подвыражений (со ссылкой на оригинальное выражение). При разумном числе слагаемых получится не так уж и много вариантов.

Дерзайте, у вас прекрасное задание!

6
  • @VladD - Вам мое огромное спасибо! Первоначально, у меня тоже были идеи по поводу syntax tree или дерева/списка суффиксов, но я его не стал рассматривать как не очень понятное и неочевидное для меня) В целом я идею понял и постараюсь реализовать в соответствии с Вашими советами. Однако пара вопросов все же есть: конкретно сейчас меня очень интересуют только сложения, кроме того по условиям переменные не могут повторяться в рамках одного уравнения, может все-таки имеет смысл как-то развить мои идеи? И еще, алгоритм, описанный Вами, всегда приводит к глобальному оптимуму или есть исключения? 23 мая 2014 в 20:45
  • @progzdeveloper: На самом деле ваши идеи правильны, просто в моём оформлении должно быть несколько удобнее. Упорядочивание переменных — это как раз и есть приведение слагаемых к каноническому порядку. Затем, в вашем задании имеют ли право быть ещё коэффициенты при слагаемых? Скажем, не просто a + b + c, а a + 2b + 3c? От этого зависит, пройдёт ли идея с битовыми векторами.
    – VladD
    23 мая 2014 в 21:49
  • @progzdeveloper: Насчёт оптимальности не уверен. Смотрите: пусть у нас есть система x1 = a2 + a3 + a4 + a5 x2 = a1 + a3 + a4 + a5 x3 = a1 + a2 + a4 + a5 x4 = a1 + a2 + a3 + a5 x5 = a1 + a2 + a3 + a4 Тогда оптимальным было бы, возможно, не нахождение общих подвыражений, а такое решение: s = a1 + a2 + a3 + a4 + a5 xi = s - ai (i = 1..5)
    – VladD
    23 мая 2014 в 21:53
  • @VladD > в вашем задании имеют ли право > быть ещё коэффициенты при слагаемых? В том то и дело, что коэффициентов при слагаемых быть не может - тоже по условию) Просто сама задача в ее оригинальной постановке более простая чем общие подвыражения, поэтому я и занялся битовыми векторами и проч. Просто хотелось бы также знать как быть в наиболее общем случае - и тут Ваш ответ прям в точку!)) Так что еще раз спасибо!) 24 мая 2014 в 5:07
  • 1
    @progzdeveloper: обязательно сделайте исследование по результатам разработки! Тема сложная и интересная, думаю, она будет полезна многим.
    – VladD
    24 мая 2014 в 10:19

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.