Оптимизация хвостовых вызовов в C # - PullRequest
Новая
       19

Оптимизация хвостовых вызовов в C #

3 голосов
/ 10 сентября 2010

У меня есть глубоко рекурсивная функция, которая теоретически должна хорошо работать даже при больших входах.Проблема была в момент написания, я забыл, что C # не очень хорошо выполняет оптимизацию хвостового вызова, поэтому я получаю StackOverflowException s для любого достаточно сложного ввода.Базовая структура метода состоит из двух больших методов, каждый из которых вызывает другой. 

public object Simplify(object param) {
    if (IsSimple(param))
        return param;
    else
        return Expand(param);
}

private object Expand(object param) {
    return Simplify(ProcessExpansion(param));
}

Оба IsSimple и ProcessExpansion имеют относительно фиксированную глубину стека - единственная проблема - рекурсия между Simplify иExpand.Как бы вы пошли по поводу уменьшения глубины стека здесь?

Я думал о возвращении делегатов, которые вычислили бы результат, но это похоже на излишество - должен быть более простой способ.Это моя мысль о решении (оно не очень хорошо отработано, потому что я продолжаю думать, что я, должно быть, здесь что-то ужасно неправильно): 

public object Simplify(object param) {
    object result = () => SimplifyInternal(param);
    while (result is Func<object>)
        result = ((Func<object>)result)();
    return result;
}

private object SimplifyInternal(object param) {
    if (IsSimple(param))
        return param;
    else
        return Expand(param);
}

private object Expand(object param) {
    return () => SimplifyInternal(ProcessExpansion(param));
}

Итак, два моих вопроса:

  1. Что такого ужасного в этом решении?
  2. Можете ли вы придумать лучший вариант?

1 Ответ

8 голосов
/ 10 сентября 2010

Разве это не просто 

while(!IsSimple(param))
    param = ProcessExpansion(param);
return param;

...