Есть произвольное лямбда-выражение. Про это лямбда-выражение известно, что в нем могут встречаться вызовы функции F(x). Причем вызовы могут встречаться несколько раз, и могут встречаться вызовы с одними и теми же аргументами. Про функцию F(x) известно, что она работает “достаточно медленно”, если вызывать ее с одними и теми же аргументами, то всегда будет возвращать одинаковый результат.
Задача: сделать оптимизацию исходного лямбда-выражения, то есть избавиться от одинаковых вызовов функции F(x).
Пример.
На входе выражение:
(int x, int y) => F(x) > F(y) ? F(x) : (F(x) < F(2*y) ? F(2*y) : F(y))
На выходе:
Лямбда-выражения, которые делают предварительное вычисление параметров:
var p1 = (int x) => F(x);
var p2 = (int y) => F(y);
var p3 = (int y) => F(2*y);
и оптимизированное выражение:
(p1, p2, p3) => p1 > p2 ? p1 : (p1 < p3 ? p3 : p2)
Требуется создать функцию оптимизированного вычисления выражения вида:
OptimizedCalculation(lambda, lambdaParams, functionF) { var optimized = OptimizeLambda(lambda, functionF); var result = CalculateLambda(optimized, lambdaParams); return result; }
То есть сначала выполняется оптимизация, потом вычисление. Прошу учесть, что исходное лямбда-выражение может иметь совершенно произвольную форму. Так же функция F может иметь совершенно произвольный вид и набор параметров.
Здравствуйте, Kaifa, Вы писали:
K>Есть произвольное лямбда-выражение. Про это лямбда-выражение известно, что в нем могут встречаться вызовы функции F(x). Причем вызовы могут встречаться несколько раз, и могут встречаться вызовы с одними и теми же аргументами. Про функцию F(x) известно, что она работает “достаточно медленно”, если вызывать ее с одними и теми же аргументами, то всегда будет возвращать одинаковый результат.
K>Задача: сделать оптимизацию исходного лямбда-выражения, то есть избавиться от одинаковых вызовов функции F(x).
K>Пример.
K>На входе выражение:
K>(int x, int y) => F(x) > F(y) ? F(x) : (F(x) < F(2*y) ? F(2*y) : F(y))
(x, y) => (
(y, fx, fy) => (
fx > fy ? fx : (fx, fy, f2y) => ( -- обойдёмся без замыканий, пробросим нужные значения как аргументы
fx < f2y ? f2y : fy
)(fx, fy, F(2*y))
)(y, F(x), F(y))
)
K>На выходе:
K>Лямбда-выражения, которые делают предварительное вычисление параметров:
K>var p1 = (int x) => F(x);
K>var p2 = (int y) => F(y);
K>var p3 = (int y) => F(2*y);
Неправильно ты, дядя Фёдор, тернарный оператор делаешь. Вычислять p3 нужно только после проверки !(p1>p2).
K>То есть сначала выполняется оптимизация, потом вычисление. Прошу учесть, что исходное лямбда-выражение может иметь совершенно произвольную форму. Так же функция F может иметь совершенно произвольный вид и набор параметров.
Задача на потрахаться с абстрактным синтаксическим деревом? Или со строкой лямбда-выражения?
Здравствуйте, Kaifa, Вы писали:
K>То есть сначала выполняется оптимизация, потом вычисление. Прошу учесть, что исходное лямбда-выражение может иметь совершенно произвольную форму. Так же функция F может иметь совершенно произвольный вид и набор параметров.
Да, кстати, мы как должны различать аргументы? По внешнему виду, по формальным правилам эквивалентности (например, для арифметики справедливо (x+0) == x, (x-x) == 0, (x+x) == x*2 и т.п.) или по фактическим значениям?
Сделать мемоизацию на чистой лямбде — мучительно, но возможно.
Пусть мы знаем, что всегда сперва вычисляется F(x), а затем иногда F(y).
Тогда делаем следующую замену
-- префиксная запись лямбда-выражения с немедленной подстановкой
let a=A in (...) === (\a -> (...))(A)
\x,y -> (..... F(x) ..... F(y) .....)
\x,y -> let fx = F(x),
fy = F(y) in
(..... fx ..... fy .....)
\x,y -> let fx = F(x),
lfy = \() -> F(y) in
(..... fx ..... fy() .....)
\x,y -> let fx = F(x) in
let lfy = \() -> if y==x then fx else F(y) in
(..... fx ..... fy() .....)
Если же мы не знаем, то придётся подниматься в какую-то монаду состояний, и тащить в качестве состояния кэш.
Да, кстати! Если мы вообще забьём на оптимизаии, — то просто возьмём и прикрутим кэш, и просунем через состояния.
(забыл, как эта разновидность называется в хаскелле — State это более общий случай)
(int x, int y) => F(x) > F(y) ? F(x) : (F(x) < F(2*y) ? F(2*y) : F(y))
// лифт функции F в мемоизатор
SF = (state, arg) =>
arg in state ?
state, state[arg]
:
let result = F(arg),
(state + {arg:result}), result
(int x, int y) => (
let s0 = {}, // затравочное состояние
let sn, result = ( // лифт исходного выражения в мемоизатор
let s1,fx = SF(s0,x),
let s2,fy = SF(s1,y),
fx > fy ?
SF(s2,x) // тупо? да, тупо, мы не думаем о том, что SF(s2,x) == SF(s0,x)
:
let s3,fx = SF(s2,x),
let s4,f2y = SF(s3,2*y),
fx < f2y ?
SF(s4,2*y)
:
SF(s4,y)
),
result // вышли из монады
)
Перекуём баги на фичи!
