Хвост-рекурсивный алгоритм pow () с запоминанием - PullRequest
Новая
       45

Хвост-рекурсивный алгоритм pow () с запоминанием

2 голосов
/ 04 апреля 2010

Я ищу алгоритм для вычисления pow(), который является хвостово-рекурсивным и использует запоминание для ускорения повторных вычислений.

Производительность не проблема; это в основном интеллектуальное упражнение - я провел поездку на поезде, придумывая все различные варианты реализации pow(), которые мог, но не смог придумать ту, которой я был доволен, и обладал этими двумя свойствами.

Мой лучший выстрел был следующим: 

def calc_tailrec_mem(base, exp, cache_line={}, acc=1, ctr=0):
    if exp == 0:
        return 1
    elif exp == 1:
        return acc * base
    elif exp in cache_line:
        val = acc * cache_line[exp]
        cache_line[exp + ctr] = val
        return val
    else:
        cache_line[ctr] = acc        
    return calc_tailrec_mem(base, exp-1, cache_line, acc * base, ctr + 1)

Работает, но не запоминает результаты всех вычислений - только те, которые имеют показатели 1..exp/2 и exp.

Ответы [ 3 ]

2 голосов
/ 04 апреля 2010

Вы получите лучшую производительность, если будете использовать метод последовательного возведения в квадрат, описанный в SICP раздел 1.2.4 Экспонирование . Он не использует запоминание, но общий подход - O (log n) вместо O (n), поэтому вы все равно должны увидеть улучшение.

Я говорю о решении итерационного процесса из упражнения 1.16 здесь .

0 голосов
/ 25 мая 2017

Это слишком поздно, но кто-нибудь там ищет ответ, вот он: 

int powMem(int base,int exp){
    //initializes once and for all
    static map<int,int> memo;

    //base case to stop the recursion
    if(exp <= 1) return base;

    //check if the value is already calculated before. If yes just return it.
    if(memo.find(exp) != memo.end())
        return memo[exp];

    //else just find it and then store it in memo for further use.
    int x = powMem(base,exp/2);
    memo[exp] = x*x;

    //return the answer
    return memo[exp];
}

Используется массив memo - точнее, карта - для хранения уже рассчитанных значений.

0 голосов
/ 04 апреля 2010

Я не думаю, что вы записываете правильную вещь в свой кеш, отображение изменилось, когда вы вызываете его с другими аргументами.

Я думаю, вам нужен кеш (base, exp) -> pow (base, exp).

Я понимаю, для чего ctr, и почему записывается только половина того, что вы ожидаете.

Рассмотрим calc_tailrec_mem(2,4): Первый уровень, pow (2,1) записывается как 2, следующий уровень = calc_tailrec_mem(2,3,...), и pow (2,2) записывается. Следующий уровень - calc_tailrec_mem(2,2,...), но он уже сохранен в кэше, поэтому рекурсия останавливается.

Функция очень запутанная, потому что она кэширует что-то совершенно отличное от того, что она должна вычислять, из-за накопителя и ctr.

...