Удаление общих подвыражений

Доброго времени суток! Столкнулся с такой задачей: есть 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. Сорри если сумбурно, я уже совсем замучался((

Ответ

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