Существует ли алгоритм извлечения подвыражений из выражения?
Предположим, у меня есть выражение:
v = ((((x * 3) * y) * 5) * z) + 5
И я хочу максимально сократить количество операций в v, перемещая подвыражения в разные переменные, сохраняя при этом, что y должно встречаться только в v, например:
a = x * 3
b = 5 * z
v = ((a * y) * b) + 5
Есть ли алгоритм, который может достичь этого?
Можем ли мы сделать c = x * 15 * z; v = c * y + 5?
@DavidEisenstat да, пока y все еще только в v
Ответы 1
Если программы ограничены прямолинейными программами с положительным, отрицательным временем, то вы можете определить значение v как полином от y и оценить его с помощью метода Хорнера.
Вот пример грубого Python в качестве иллюстрации.
import operator
class Formula:
def __init__(self, s=0):
self.s = str(s)
def __repr__(self):
return "Formula({!r})".format(self.s)
def __str__(self):
return self.s
def __add__(self, other):
if isinstance(other, int):
other = Formula(str(other))
if not isinstance(other, Formula):
return NotImplemented
if other.s == "0":
return self
return Formula("({}) + ({})".format(self, other))
def __radd__(self, other):
return self + other
def __mul__(self, other):
if isinstance(other, int):
other = Formula(str(other))
if not isinstance(other, Formula):
return NotImplemented
if other.s == "0":
return 0
if other.s == "1":
return self
return Formula("({}) * ({})".format(self, other))
def __rmul__(self, other):
return self * other
class Polynomial:
def __init__(self, *coefs):
self.coefs = coefs
def print_program(self):
v = 0
for i, coef in enumerate(reversed(self.coefs)):
c = Formula("c{}".format(i))
print("{} = {}".format(c, coef))
v *= Formula("y")
v += c
print("v = {}".format(v))
def __add__(self, other):
if isinstance(other, int):
other = Formula(other)
if isinstance(other, Formula):
other = Polynomial(other)
if not isinstance(other, Polynomial):
return NotImplemented
coefs = list(map(operator.add, self.coefs, other.coefs))
if len(self.coefs) > len(other.coefs):
coefs.extend(self.coefs[len(other.coefs) :])
if len(other.coefs) > len(self.coefs):
coefs.extend(other.coefs[len(self.coefs) :])
return Polynomial(*coefs)
def __radd__(self, other):
return self + other
def __mul__(self, other):
if isinstance(other, int):
other = Formula(other)
if isinstance(other, Formula):
other = Polynomial(other)
if not isinstance(other, Polynomial):
return NotImplemented
coefs = [0] * (len(self.coefs) + len(other.coefs) - 1)
for i, ci in enumerate(self.coefs):
for j, cj in enumerate(other.coefs):
coefs[i + j] += ci * cj
return Polynomial(*coefs)
def __rmul__(self, other):
return self * other
x = Formula("x")
y = Polynomial(0, 1)
z = Formula("z")
v = ((((x * 3) * y) * 5) * z) + 5
v.print_program()
Выход
c0 = (((x) * (3)) * (5)) * (z)
c1 = 5
v = ((c0) * (y)) + (c1)
Большое спасибо за подробный ответ. Это отлично работает для примера. Два вопроса: могу ли я по-прежнему использовать этот метод, если я 1. хочу ввести оператор деления? и 2. могу ли я также использовать этот метод, если он имеет несколько значений y, например ((((x * 3) * y) * 5) * z) + y) + 5
@Tom Несколько вхождений y в порядке. Деление включает в себя расширение полиномиальной логики на полиномиальные дроби — не слишком сложно, следует логике целых дробей, но я не уверен, что полиномиальная дробь всегда оптимальна. Вы можете захотеть реализовать полиномиальный НОД, чтобы исключить общие факторы.
Спасибо. Есть ли у вас какие-либо советы, как заставить это работать с несколькими специальными значениями, например. y, q? Таким образом, конечным результатом также является выражение, содержащее только y и q
@Tom Затем вам нужно реализовать поддержку многомерных многочленов, которые вы можете рассматривать как одномерные многочлены с одномерными (в другой переменной) полиномиальными коэффициентами. Однако чем больше мощности вы добавляете, тем сложнее ее оптимизировать. Это может быть момент, когда вы захотите попытаться изменить то, что существует, используя стандартные методы оптимизации компилятора, а не разбивать его на мономы и собирать обратно.
В обоих случаях 4 умножения и 1 сложение. Так что сокращения нет.