题目:
Consider the following recursive function:
int recur(int n) {
if (n < 3)
return 1;
return recur(n-1) * recur(n-2) * recur(n-3);
}
if memoisation is applied and recur(n-1) is calculated and stored before calculating recur(n-2) and recur(n-3), for the call recur(6), how many calls will be made to recur()?
我的解法这样的:
int count_x = 0;
unordered_map<int,int> map_x;
int recur(int n) {
count_x++;
if (n < 3)
return 1;
// cout << n << endl;
if (map_x.find(n) != map_x.end()) {
return map_x[n];
}
map_x[n] = recur(n-1) * recur(n-2) * recur(n-3);
return map_x[n];
}
TEST(test, recur) {
cout << recur(6) << endl;
cout << count_x << endl;
}
输出结果是:
1
13
现在明确题目的答案不是 13,我这么验证哪里存在问题吗
1
wutiantong 2021-05-26 16:24:19 +08:00 1
答案是 7 么(包括 recur(6)本身)
|
2
AkideLiu OP @wutiantong 是的!请问为什么呢?
|
3
wutiantong 2021-05-26 16:32:17 +08:00
@AkideLiu 你那个解法的代码里 count_x 的计算没尊重 memoisation 呀
|
4
jorneyr 2021-05-26 16:37:35 +08:00
map_x[0], map_x[1], map_x[2] 先放到 map 里
|
5
hitmanx 2021-05-26 16:50:13 +08:00
“if memoisation is applied and recur(n-1) is calculated and stored before calculating recur(n-2) and recur(n-3)”
没太搞懂,如果答案是 7,是不是 recur(0) - recur(6)各计算一次?这样的话得按照从小到大进行计算与储存,即 recur(n-3) => recur(n-2) => recur(n-1)。 但是题目里写的是先储存 recur(n-1),那岂不是 recur(n-3)和 recur(n-2)的结果会被重复计算?这样答案为何还是 7 ? |
6
AkideLiu OP @wutiantong count_x 在最上面啊,每次 recur function 被 call 都会+1,这个计算方式不适用于 memoisation 吗?
|
7
jorneyr 2021-05-26 16:52:37 +08:00 1
答案是 7 的话,执行前明显先把 3 的解也存储起来了:
6 > 5, 4, 3 5 > 4, 3, 2 4 > 3, 2, 1 3 直接查,为 1 次 4 为 3, 2, 1: 都是直接查,为 3 次 5 为 4, 3, 2: 因为上面 4 已经存储,也是直接查, 为 3 次 当然,程序还可以优化为先找相对小的递归的解,这样大的问题就能从小的问题中直接查询答案: map_x[n] = recur(n-3) * recur(n-1) * recur(n-1); |
8
wutiantong 2021-05-26 16:59:40 +08:00 1
@AkideLiu memoisation 的意义不就是减少原始调用么?所以在你的代码里,当从 map 中返回值时(相当于 memoisation ),就不应该再算作是调用次数了。
|
9
wutiantong 2021-05-26 17:02:39 +08:00
@hitmanx 那句话是在说 recur(n-1) * recur(n-2) * recur(n-3) 这个表达式中 recur(n-1) 被确保先于后两者求值。在 C++中,同个表达式内的求值顺序通常是不确定的。
|
10
AkideLiu OP @wutiantong @jorneyr 太感谢了!恍然大悟!
这样子输出是 7 !!! ```c++ int count_x = 0; unordered_map<int,int> map_x; int recur(int n) { // cout << n << endl; if (map_x.find(n) != map_x.end()) { return map_x[n]; } count_x++; if (n < 3){ map_x[n] = 1; return 1; } map_x[n] = recur(n-1) * recur(n-2) * recur(n-3); return map_x[n]; } TEST(test, recur) { cout << recur(6) << endl; cout << count_x << endl; } ``` |
11
monkeyNik 2021-05-26 17:10:27 +08:00
对本次调用你查表,但你没在内部递归调用前对每个子调用查表,导致你多了一些函数调用。
至于次数,6 、5 、4 、3 、2 、1 、0,每一个都算一遍并缓存,闭着眼睛也是 7 次。 |
12
lesismal 2021-05-26 17:25:52 +08:00
简单直接的判断方法:
3 为临界值,n=3 时最多向下 n-1/n-2/n-3,即 recur 最小的参数 n 为 0 ; 每个 n 对应的值都进行记忆的前提下,每个 n 只需要调用一次 recur ; 首次调用 recur(6),则整个过程需要对 0-6 挨个计算、记忆,所以是 7 次(不管小于 3 的参数是否记忆,当 n=3/4/5 时 n 也被缓存过、不会被重复调用,所以小于 3 的也不会被重复调用)。 可以类推首次调用大于等于 3 和小于 3 的次数 |
13
jorneyr 2021-05-26 17:45:44 +08:00
只要进入 recur 就算一次递归调用吧,不管是查表还是继续递归计算。
也就是 recur 被调用的次数。 |
14
AkideLiu OP @jorneyr 不得不承认,题目确实不严谨。如果结果是 7 的话问题可以问题成 how many times of recur function actually computed 。我的理解是 return memo 就不算是 computed, 而是 cache,但是依然会有 function be called 。
|
15
FACEB00K 2021-05-26 18:34:37 +08:00 1
换种写法
```cpp int count_x = 0; unordered_map<int,int> map_x; int recur(int n) { count_x++; if (map_x.find(n) != map_x.end()) { return map_x[n]; } if (n < 3) { map_x[n] = 1; return map_x[n]; } int next_1 = (map_x.find(n-1) == map_x.end()) ? recur(n-1) : map_x[n-1]; int next_2 = (map_x.find(n-2) == map_x.end()) ? recur(n-2) : map_x[n-2]; int next_3 = (map_x.find(n-3) == map_x.end()) ? recur(n-3) : map_x[n-3]; map_x[n] = next_1 * next_2 * next_3; return map_x[n]; } ``` |
16
LigeLaige 2021-05-26 20:02:37 +08:00
顺着 lz 思路,修改如下
```cpp int recur(int n) { if (map_x.find(n) != map_x.end()) { return map_x[n]; } count_x++; if (n < 3) { map_x[n] = 1; } else { map_x[n] = recur(n-1) * recur(n-2) * recur(n-3); } return map_x[n]; } ``` |
17
LigeLaige 2021-05-26 20:03:27 +08:00
<code>
int recur(int n) { if (map_x.find(n) != map_x.end()) { return map_x[n]; } count_x++; if (n < 3) { map_x[n] = 1; } else { map_x[n] = recur(n-1) * recur(n-2) * recur(n-3); } return map_x[n]; } </code> |
18
hitmanx 2021-05-26 20:12:45 +08:00
@wutiantong 好吧,谢谢解释。原来是这个意思。
不过,如果是指这一行内的求值顺序的话,题目为啥要特意强调一下?除非这个顺序对于这个题目的答案(total # of recur() invoked)会有影响,但是基于 memoisation 的话两者应该一样?还是我忽略了啥 即 // 1) auto n_3 = recur(n-3); auto n_2 = recur(n-2); auto n_1 = recur(n-1); return n_3 + n_2 + n1; 2) auto n_1 = recur(n-1); auto n_2 = recur(n-2); auto n_3 = recur(n-3); return n_1 + n_2 + n3; |
19
hitmanx 2021-05-26 20:25:27 +08:00
@AkideLiu 这个取决于你的 cache lookup op 是在 caller side 还是 callee side~
像 15 楼一样,放在 caller side 的话,就会实质上而不是概念上减少 recur 调用的数量。 |
20
no1xsyzy 2021-05-27 09:55:19 +08:00
|
21
wutiantong 2021-05-27 10:25:18 +08:00
@hitmanx 如果有并行求值的情况呢?
|
22
bibitiger 2021-05-27 19:04:57 +08:00
题目本身不严谨,我觉得应该说明是最少调用次数。
如果是最少调用次数的话,那应该在 caller 的时候对 recur(n-1),recur(n-2),recur(n-3)也进行查表,这样就不会进入 recur()。 而要得出 f(n-1),必然会得到 f(n-2),f(n-3)...f(n-n), 所以 f(n)对于 f()的调用必然等于 n+1 。 int count_x = 0; unordered_map<int,int> map_x; int recur(int n) { count_x++; if (map_x.find(n) != map_x.end()) { return map_x[n]; } if (n < 3){ map_x[n] = 1; return 1; } int temp_n1 = map_x.find(n-1) == map_x.end()?recur(n-1) :map_x[n-1]; int temp_n2 = map_x.find(n-2) == map_x.end()?recur(n-2) :map_x[n-2]; int temp_n3 = map_x.find(n-3) == map_x.end()?recur(n-3) :map_x[n-3]; map_x[n] = temp_n1*temp_n2*temp_n3; return map_x[n]; } |