sysprog2020
目的: 檢驗學員對 bitwise 操作, 遞迴呼叫, 編譯器最佳化 的認知
1
給定兩個函式實作:
int funcA(int i)
{
if (i == 0)
return 0;
return 5 * funcA(i - 1);
}
int funcB(int i)
{
if (i == 0)
return 0;
return funcB(i - 1);
}
以 tail recursion 的觀點,請從下列選項挑出正確的陳述。
作答區
T = ?
(a)
funcA 和 funcB 都屬於 Tail recursion,適用編譯器的 tail call optimization (TCO)(b)
funcA 是 Tail recursion,但 funcB 不是 Tail recursion(c)
funcB 是 Tail recursion,但 funcA 不是 Tail recursion(d)
funcA 和 funcB 兩者都不是 Tail recursion延伸問題:
-O2
以上) 開啟時,上述程式碼的行為,以及 tail call optimization (TCO) 適用場景為何2
考慮測試 C 編譯器 Tail Call Optimization (TCO) 能力的程式 tco-test,在 gcc-8.4.0 中抑制最佳化 (也就是 -O0
編譯選項) 進行編譯,得到以下執行結果:
$ gcc -Wall -Wextra -Wno-unused-parameter -O0 main.c first.c second.c -o chaining
$ ./chaining
No arguments: no TCO
One argument: no TCO
Additional int argument: no TCO
Dropped int argument: no TCO
char return to int: no TCO
int return to char: no TCO
int return to void: no TCO
而在開啟最佳化 (這裡用 -O2
等級) 編譯,會得到以下執行結果:
$ gcc -Wall -Wextra -Wno-unused-parameter -O2 main.c first.c second.c -o chaining
$ ./chaining
No arguments: TCO
One argument: TCO
Additional int argument: TCO
Dropped int argument: TCO
char return to int: no TCO
int return to char: no TCO
int return to void: TCO
注意 __builtin_return_address 是 gcc 的內建函式:
This function returns the return address of the current function, or of one of its callers. The level argument is number of frames to scan up the call stack. A value of 0 yields the return address of the current function, a value of 1 yields the return address of the caller of the current function, and so forth. When inlining the expected behavior is that the function returns the address of the function that is returned to. To work around this behavior use the noinline function attribute.
The level argument must be a constant integer.
從實驗中可發現下方程式無法對 g
函式施加 TCO:
void g(int *p);
void f(void) {
int x = 3;
g(&x);
}
void g(int *p) { printf("%d\n", *p); }
因為函式 f
的區域變數 x
在返回後就不再存在於 stack。考慮以下程式碼:
int *global_var;
void f(void)
{
int x = 3;
global_var = &x;
...
/* Can the compiler perform TCO here? */
g();
}
思考程式註解,在第 8 行能否施加 TCO 呢?選出最適合的解釋。
作答區
Q = ?
(a)
編譯器不可能施加 TCO(b)
編譯器一定可施加 TCO(c)
只要函式 g
沒有對 global_var
指標作 dereference,那麼 TCO 就有機會延伸問題:
3
軟體開發者 Max Howell 在 Twitter 講述他在 2015 年是怎麼在 Google 面試時被刷掉: (出處)
「Google:我們 90% 的工程師都用你寫的軟體(Homebrew),但你沒辦法在白板上實作 Invert Binary Tree,所以因此我們決定不聘用你」
摘自 iOS 神人應徵工作之滑鐵盧事件:
LeetCode 226. Invert Binary Tree 本質上就是找出二元樹的鏡像 (mirror):
以下是參考實作:
struct TreeNode *invertTree(struct TreeNode *root)
{
if (!root)
return NULL;
if (!root->left && !root->right)
return root;
struct TreeNode *tmp = root->left;
root->left = root->right;
root->right = tmp;
invertTree(root->left);
invertTree(root->right);
return root;
}
若將上述程式碼的第 12 行和第 13 行對調,是否會影響最終輸出?
作答區
P = ?
(a)
會影響,程式執行將會錯誤(b)
不影響,依然可產生符合預期的輸出延伸問題:
4
LeetCoee 201. Bitwise AND of Numbers Range 給一個範圍
以 0
。
以下是一個對應的解法:
int rangeBitwiseAnd(int m, int n)
{
if (m == 0) return 0;
int diff = n - m;
int count = diff ? 32U - __builtin_clz(diff) : 0;
return m & n & MASK;
}
作答區
MASK = ?
(a)
~((1U << count) - 1)
(b)
~(1U << count)
(c)
(~1U - count)
(d)
~((1U << count) + 1)
(e)
(~1U ^ count)
(f)
(~1U ^ (1 << count))
(g)
(~1U ^ (1 << count) - 1)
延伸問題:
5
LeetCode 97. Interleaving String:
大意是判斷給定的字串 s1 與 s2 可否交錯形成字串 s3。從上圖可見,走訪 s3 所有字元,其字元必定是來自 s1 或來自 s2,並且 s1 與 s2 的字元也是依序取出,也就是 s3[i3]
必定為 s1[i1]
或 s2[i2]
,其中 i1
, i2
, i3
分別為 s1, s2, s3 目前的位置。
考慮一項 Dynamic Programming (動態規劃) 的實作如下:
bool isInterleave(char *s1, char *s2, char *s3)
{
size_t n = strlen(s1), m = strlen(s2);
if ((n + m) != strlen(s3))
return false;
bool dp[m + 1];
memset(dp + 1, false, m * sizeof(bool));
dp[0] = true;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0 && j == 0)
continue;
int p = RRR;
if (i == 0)
dp[j] = dp[j - 1] & (s2[j - 1] == s3[p]);
else {
dp[j] &= (s1[i - 1] == s3[p]);
if (j > 0)
dp[j] |= dp[j - 1] & (s2[j - 1] == s3[p]);
}
}
}
return dp[m];
}
請補完程式碼,使其符合 LeetCode 題目規範。
sizeof(bool)
is implementation-defined. 不必然為1
延伸閱讀:
作答區
RRR = ?
(a)
i + j
(b)
i + j - 1
(c)
j - 1
延伸問題: