为什么低效的阶乘计算是......高效(且快速)?
Why inefficient factorial computation is...efficient (and fast)?
我写了这个简单的程序来测试 memoization 技术:
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;
}
我期望在几秒钟内执行这段代码(因为它的递归效率低下),但实际上只花了几毫秒...为什么?我认为引擎盖下有一些编译器优化,但我不明白会发生什么。
奖金问题:
你能给我一个执行效率低下(编译器优化与否)的简单程序,以便我测试记忆化的好处吗?
记忆主要是一种改进计算 algorithmic complexity 的技术,而不是避免递归。这就是为什么斐波那契数是比阶乘函数更好用的例子(即使 WikiPedia 页面使用阶乘函数)。
看看wikibook on dynamic programming中的数字。在第二个数字中被划掉的所有电话都是您从记忆中获得的节省。使用阶乘函数,什么都不会被划掉。
记忆技术旨在用于优化昂贵的函数调用。阶乘函数并非如此。 C++ 非常快,因此阶乘函数调用的计算时间永远不会超过几毫秒。 (至少如果不使用多精度)。 factorial(100) 是 "only" 100 次乘法,所以对 C++ 来说没什么。
如果这只是为了测试或演示目的,我会简单地在函数调用中引入延迟(睡眠、长虚拟循环或其他)。
随着记忆的实施,这种延迟不应该发生,所以它在 "almost" 内立即运行。
这是我会做的一个例子。 factorial 是昂贵的功能。 memo_factorial 是实现记忆技术的包装。
在函数的第一次调用中,输入和输出的字典被更新,在接下来的具有相同输入的调用中,先前存储的值是 return 所以 "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)
希望你觉得有用。
此致,
亚历克斯
注意:阶乘通常定义在整数值上。当然,它只是一个乘法序列,因此它可以应用于其他类型。
我写了这个简单的程序来测试 memoization 技术:
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;
}
我期望在几秒钟内执行这段代码(因为它的递归效率低下),但实际上只花了几毫秒...为什么?我认为引擎盖下有一些编译器优化,但我不明白会发生什么。
奖金问题: 你能给我一个执行效率低下(编译器优化与否)的简单程序,以便我测试记忆化的好处吗?
记忆主要是一种改进计算 algorithmic complexity 的技术,而不是避免递归。这就是为什么斐波那契数是比阶乘函数更好用的例子(即使 WikiPedia 页面使用阶乘函数)。
看看wikibook on dynamic programming中的数字。在第二个数字中被划掉的所有电话都是您从记忆中获得的节省。使用阶乘函数,什么都不会被划掉。
记忆技术旨在用于优化昂贵的函数调用。阶乘函数并非如此。 C++ 非常快,因此阶乘函数调用的计算时间永远不会超过几毫秒。 (至少如果不使用多精度)。 factorial(100) 是 "only" 100 次乘法,所以对 C++ 来说没什么。
如果这只是为了测试或演示目的,我会简单地在函数调用中引入延迟(睡眠、长虚拟循环或其他)。 随着记忆的实施,这种延迟不应该发生,所以它在 "almost" 内立即运行。
这是我会做的一个例子。 factorial 是昂贵的功能。 memo_factorial 是实现记忆技术的包装。 在函数的第一次调用中,输入和输出的字典被更新,在接下来的具有相同输入的调用中,先前存储的值是 return 所以 "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)
希望你觉得有用。
此致, 亚历克斯
注意:阶乘通常定义在整数值上。当然,它只是一个乘法序列,因此它可以应用于其他类型。