Осуществлять Скала-как батут, чтобы получить хвост вызова оптимизации в Русте


По теме хвост вызов оптимизации, я нашел два РЛК: 271 и 1888.

Пока это воплощается в жизнь, я хотел сделать что-то навеяло из скалы Trampoline функциональность.

Фактическая реализация далека от полноценного оптимизация хвостовой вызов в том, что он заменяет рекурсивные вызовы функций с итеративные, однако его используют для сохранения глубины стека минимум. Мое фактическое состояние работы заключается в следующем:

enum Trampoline<A, R> {
    Continue(A, R),
    End(R),
}

impl<A, R> Trampoline<A, R> {
    fn start(function: &Fn(A, R) -> Trampoline<A, R>, mut arg: A, mut sum: R) -> R
    {
        loop {
            match function(arg, sum) {
                Trampoline::Continue(r_arg, r_sum) => {
                    arg = r_arg;
                    sum = r_sum;
                },
                Trampoline::End(result) => return result,
            }
        }
    }
}

fn recurse_trampolin(arg: i32, sum: i32) -> Trampoline<i32, i32> {
    if arg == 0 {
        Trampoline::End(sum)
    } else {
        Trampoline::Continue(arg - 1, sum + arg)
    }
}

fn recurse_normal(arg: i32, sum: i32) -> i32 {
    if arg == 0 {
        sum
    } else {
        recurse_normal(arg - 1, sum + arg)
    }
}

fn main() {
    println!("{}", recurse_normal(5, 0));
    println!("{}", Trampoline::start(&recurse_trampolin, 5, 0));
}

Помимо использования ссылок для совместимости с не-Copy типа, может эта конструкция быть дополнительно оптимизирована или код упрощенный/приукрашена?



162
5
задан 13 марта 2018 в 10:03 Источник Поделиться
Комментарии
1 ответ


  1. Запустить Rustfmt. Он будет автоматически фиксировать такие вещи, как


    • Открывающие фигурные скобки на той же строке в качестве сигнатуры функции (за исключением функции подписи уже несколько строк).

    • Нет запятой в конце match рука, которая использует фигурные скобки.


  2. Ваша функция имени есть опечатка: recurse_trampolin

  3. Вместо того, чтобы трейт ссылку на объект (&Fn(...) -> ...), взять универсальный. Это позволяет для более лучшей оптимизации и позволяет избежать лишней косвенности.

enum Trampoline<A, R> {
Continue(A, R),
End(R),
}

impl<A, R> Trampoline<A, R> {
fn start<F>(function: F, mut arg: A, mut sum: R) -> R
where
F: Fn(A, R) -> Trampoline<A, R>,
{
loop {
match function(arg, sum) {
Trampoline::Continue(r_arg, r_sum) => {
arg = r_arg;
sum = r_sum;
}
Trampoline::End(result) => return result,
}
}
}
}

fn recurse_trampoline(arg: i32, sum: i32) -> Trampoline<i32, i32> {
if arg == 0 {
Trampoline::End(sum)
} else {
Trampoline::Continue(arg - 1, sum + arg)
}
}

fn recurse_normal(arg: i32, sum: i32) -> i32 {
if arg == 0 {
sum
} else {
recurse_normal(arg - 1, sum + arg)
}
}

fn main() {
println!("{}", recurse_normal(5, 0));
println!("{}", Trampoline::start(recurse_trampoline, 5, 0));
}

2
ответ дан 17 марта 2018 в 05:03 Источник Поделиться