Резюме:
Используя «открытую» рекурсию:
- Мы можем отделить логику мемоизации от функциональной логики.
- Мы можем мемоизировать функции, не изменяя синтаксис функции.
- Мы можем сделать функции универсальными для нескольких типов мемоизации.
Мемоизация в Rust.
Рассмотрим рекурсивную функцию. Самый простой пример - последовательность Фибоначчи. Вот наивная реализация:
fn fib_naive(arg: u32) -> u32 { match arg { 0 => 0, 1 => 1, n => fib_naive(n - 1) + fib_naive(n - 2), } }fn main() { assert_eq!(fib_naive(40), 102334155); }
Расчет fib_naive(40) на моем компьютере занимает почти секунду. Если мы посмотрим на эту функцию, мы сможем судить о ее производительности. Результатом fib_naive будет 0, 1 или результат двух вызовов fib_naive, сложенных вместе. Если в нашем распоряжении есть только 0, 1 и сложение, то для вычисления fib_naive(n) потребуется не менее fib_naive(n) сложений. Это неприемлемая производительность для чего-либо, кроме наименьших значений n.
Запоминание результатов
Один из способов повысить производительность - запомнить результаты. Это означает, что когда мы вызываем нашу функцию, мы записываем результат в какой-то кеш. Если нам нужно снова вызвать функцию с теми же аргументами, вместо вычисления результата мы ищем результат в кеше.
Алгоритм представляет собой простую модификацию функции выше: всякий раз, когда мы вызываем нашу функцию, мы проверяем, есть ли результат уже в кеше, если он уже там, мы возвращаем его. Если его нет, мы его вычисляем, сохраняем результат в кеш и возвращаем значение:
fn fib_memo (cache: &mut HashMap<u32, u32>, arg: u32) -> u32 { match cache.get(&arg).map(|entry| entry.clone()) { Some(result) => result, None => { let result = match arg { 0 => 0, 1 => 1, n => fib_memo(cache, n - 1) + fib_memo(cache, n - 2), }; cache.insert(arg, result.clone()); result } } }fn main () { assert_eq!(fib_memo(&mut HashMap::new(), 40), 102334155); }
Это все еще достаточно просто, нет ничего слишком сложного, а производительность этой функции значительно улучшена по сравнению с fib_naive. Обратите внимание, что исходное тело функции все еще находится в ветви None оператора match. Мы также должны вызвать функцию с дополнительным аргументом: &mut HashMap::new().
Мы можем лучше. Логика мемоизации не специфична для fib_memo. Мы можем поместить логику мемоизации в отдельную функцию, чтобы потом использовать ее для других функций:
fn memoize<A, R, F> (cache: &mut HashMap<A, R>, func: F, arg: A) -> R where
A: Eq + Hash + Clone,
R: Clone,
F: Fn(&mut HashMap<A, R>, A) -> R
{
match cache.get(&arg).map(|x| x.clone()) {
Some(result) => result,
None => {
let result = func(cache, arg.clone());
cache.insert(arg, result.clone());
result
}
}
}Эта функция позволяет нам переписать нашу fib_memo функцию:
fn fib_memo2 (cache: &mut HashMap<u32, u32>, arg: u32) -> u32 { match arg { 0 => 0, 1 => 1, n => memoize(cache, fib_memo2, n - 1) + memoize(cache, fib_memo2, arg - 2), } }fn main() { assert_eq!(memoize(&mut HashMap::new(), fib_memo2, 40), 102334155); }
Теперь мы можем использовать memoize для любой функции, не записывая ее постоянно. В этом коде все еще есть некоторые проблемы, которые мы попытаемся решить:
Во-первых, мы могли передать неправильный кеш для мемоизации. Это может быть кеш от другой функции, или он мог быть изменен чем-то другим, чтобы содержать неверные значения. Кэш и функция связаны друг с другом и должны быть единым целым.
Во-вторых, неудобно всегда вызывать fib_memo2 через функцию memoize. Пользователи этой функции могут быть разочарованы тем, что мы не можем вызвать ее напрямую.
В-третьих, мы не можем изменить тип мемоизации. Если мы хотим вызвать эту функцию без мемоизации, мы должны ее переписать. Мы поговорим о том, как решить эту проблему позже.
Введение в открытую рекурсию
Отказ от ответственности: следующее в настоящее время работает только на Rust nightly.
Прежде всего, мы объединяем кеш и функцию в единую структуру, чтобы случайно не использовать неправильный кеш с нашей функцией. Мы также создаем конструктор, чтобы мы могли сделать HashCache из функции:
struct HashCache <A, R> {
data: HashMap<A, R>,
func: fn(&mut HashCache<A, R>, A) -> R,
}
impl<A, R> HashCache<A, R> where
A: Eq + Hash
{
fn from_func(func: fn(&mut Self, A) -> R) -> Self {
HashCache {
data: HashMap::new(),
func: func,
}
}
}Подпись func очень похожа на подпись fib_memo, но вместо HashMap в качестве кеша у нас есть собственный HashCache.
Затем давайте реализуем FnMut для HashCache:
impl<A, R> FnMut<(A,)> for HashCache<A, R> where A: Eq + Hash + Clone, R: Clone, { extern "rust-call" fn call_mut(&mut self, args: (A,)) -> Self::Output { let arg = args.0; match self.data.get(&arg).map(|x| x.clone()) { Some(result) => result, None => { let result = (self.func.clone())(self, arg.clone()); self.data.insert(arg, result.clone()); result } } } }// We need to implement `FnOnce` to implement `FnMut`. impl<A, R> FnOnce<(A,)> for HashCache<A, R> where A: Eq + Hash + Clone, R: Clone, { type Output = R; extern "rust-call" fn call_once(mut self, args: (A,)) -> Self::Output { self.call_mut(args) } }
За исключением некоторых незначительных деталей реализации, код для call_mut совпадает с кодом для memoize. Вот некоторые ключевые моменты:
- Мы можем вызывать структуру
HashCacheкак обычную функцию, потому что она реализуетFnMut. - Когда мы вызываем
HashCacheкак функцию, он уже содержит кеш и указатель на функцию, поэтому единственная дополнительная информация, которая нам нужна, - это аргумент дляfib_xxx.
Затем давайте перепишем нашу функцию, чтобы использовать открытую рекурсию:
fn fib_open<F>(recurse: &mut F, arg: u32) -> u32 where
F: FnMut(u32) -> u32
{
match arg {
0 => 0,
1 => 1,
n => recurse(n - 1) + recurse(n - 2),
}
}Это похоже на то, как выглядел наш оригинальный fib_naive. Разница в том, что там, где fib_open вызывает себя по имени, мы вызываем функцию recurse.
fib_open также имеет сходство с fib_memo2, вместо аргумента кеша у нас есть &mut F с именем recurse, и вместо вызова memoize мы вызываем recurse.
HashCache<u32, u32> реализует FnMut(u32) -> u32, поэтому это подходящее значение для recurse. Мы также можем назвать это отдельной функцией:
fn main() {
let mut memoised = HashCache::from_func(fib_open);
assert_eq!(memoised(40), 102334155);
}
Замена рекурсивных методов:
Мы обсудили, что не нужно переписывать функцию, если мы хотим использовать обычную рекурсию. Мы можем создать оболочку newtype вокруг открытой рекурсивной функции:
struct NoCache<A, R>(fn(&mut NoCache<A, R>, A) -> R);В отличие от структуры HashCache, поскольку мы ничего не запоминаем, нам не нужно хранить кеш, только указатель на функцию. Мы можем реализовать FnMut для NoCache:
impl<A, R> FnMut<(A,)> for NoCache<A, R> { extern "rust-call" fn call_mut(&mut self, args: (A,)) -> Self::Output { (self.0.clone())(self, args.0) } }impl<A, R> FnOnce<(A,)> for NoCache<A, R> { type Output = R; extern "rust-call" fn call_once(mut self, args: (A,)) -> Self::Output { self.call_mut(args) } }
Подобно HashCache, NoCache является подходящим значением для recurse, поэтому мы можем передать его в fib_open и вызвать его отдельно:
fn main() {
let mut regular = NoCache(fib_open);
assert_eq!(regular(40), 102334155);
}В заключение нам удалось решить все три исходные задачи:
- Используя
HashCache, мы не можем перепутать функцию и соответствующий кеш. - Мы можем вызвать мемоизированную функцию, используя обычный синтаксис вызова функции.
- Мы можем заменить мемоизацию на обычную рекурсию, не изменяя саму функцию.
