为什么效率低下的阶乘计算is...efficient (和快速)？

Question

我编写了这个简单的程序来测试回忆录技术：

int main() {
    function<double(double)> f = [&f](double i) -> double {
        if (i == 1)
            return 1;
        else
            return i * f(i - 1);
    };
    cout << f(100) << endl;
}

我本来希望在几秒钟内执行这段代码(因为它的递归效率很低)，但实际上它只需要很少的ms...Why？我认为在幕后有一些编译器优化，但我不明白会发生什么。

的额外问题：，你能给我一个简单的程序，它的执行效率很低(编译器优化与否)，这样我就可以测试回忆录的好处了吗？

Answer 1

注解技术用于优化昂贵的函数调用。阶乘函数不是这样的。C++非常快，所以一个阶乘函数调用的计算时间永远不会超过几毫秒。(至少如果没有使用多精度)。阶乘( 100 )是“仅”100个乘法，所以对C++没有任何意义。

如果这只是为了测试或演示目的，我将简单地介绍函数调用中的延迟(睡眠、长虚拟循环或其他什么)。随着记忆的实施，这个延迟不应该发生，所以它在“几乎”没有时间。

这就是我会做的一个例子。阶乘是一种昂贵的函数。memo_factorial是它与回忆录技术的结合。在对函数的第一次调用中，将更新输入和输出字典，在以下具有相同输入的调用中，先前存储的值返回，因此不会再次执行"real“函数。

#define ELAPSE(cmd) { clock_t s = clock();\
    long ret = cmd;\
    cout << "\t" << #cmd\
         << " = " << ret \
         << "\t(" << (clock()-s)/double(CLOCKS_PER_SEC) << " secs)" \
         << endl; }

long factorial(long i) {
    for(clock_t s = clock(); (clock()-s)<CLOCKS_PER_SEC; );
    return i<=1 ? 1 : i*factorial(i-1);
}
long memo_factorial(long i) {
    static map<long,long> saved;
    map<long,long>::const_iterator it = saved.find(i);
    return ( it==saved.end() ) ? (saved[i] = memo_factorial(i)) : it->second;
}

int main() {
    cout << "first execution WITHOUT memoization" << endl;
    for(int i=1; i<5; ++i) {
        ELAPSE( memo_factorial(i) )
    }

    cout << "second execution WITH memoization" << endl;
    for(int i=1; i<5; ++i) {
        ELAPSE( memo_factorial(i) )
    }

    return 0;
}

产出应是：

first execution WITHOUT memoization
    memo_factorial(i) = 1   (1 secs)
    memo_factorial(i) = 2   (1 secs)
    memo_factorial(i) = 6   (1 secs)
    memo_factorial(i) = 24  (1 secs)
second execution WITH memoization
    memo_factorial(i) = 1   (0 secs)
    memo_factorial(i) = 2   (0 secs)
    memo_factorial(i) = 6   (0 secs)
    memo_factorial(i) = 24  (0 secs)

希望你觉得有用。

你好，亚历克斯

注意:阶乘通常是对整数值进行定义的。当然，它只是一个乘法序列，因此它可以应用于其他类型。

Answer 2

记忆主要是一种改进计算的算法复杂度，而不是避免递归的技术。这就是为什么Fibonacci数比阶乘函数要好得多的原因(尽管WikiPedia页面使用阶乘函数)。

看看动态规划wikibook中的数字。在第二个数字中划掉的所有电话都是你从回忆录中得到的节省。有了阶乘函数，任何东西都不会被划掉。