Jserv’s Solution to FizzBuzz 實做分析

陳奕熹
陳奕熹
Feb 7 · 9 min read

在 2018系統軟體秋季班最後一堂課,jserv 老師提到了 leet code 上一題乍看起來很普通的程式問題,但就是這題看似簡單的 fizzbuzz 題目卻是 Google 面試題目之一,到底這是怎樣的一個題目呢?

題幹非常的簡單:

給定數字 N,由 1 開始到 N 為止,只要該數字可被 3 整除就印出 “fizz” ,可被五整除就印出 “buzz” ,皆不能整除就印出該數字

看起來的確很簡單對吧,簡單到題目讀完到大概解法就出來了,透過一些基本的模數運算元 (mod operator) 加上一些條件判斷就可以完成了

for(int i = 1; i <= n; i++){
String result = "";
if(i%3 == 0) result += "Fizz";
if(i%5 == 0) result += "Buzz";
if(result.length() > 0)
System.out.println(result);
else
System.out.println(i);
}

以上這段程式碼是從 [心得] 學界轉業界…google面試洗臉心得簡單的 FizzBuzz 藏有 深度(google 面試題) 中直接複製貼上的 java 程式碼,基本上就是透過 result 這個空字串擴充塞下不同條件判斷下的 fizz/buzz/[數字]

恩,基本上如果 google 面試題拿出這題,他應該是不會想看這麼暴力的直覺解法,而是以這樣的解法為出發點做最佳化

那要先發現問題才能嘗試對這些問題做最佳化,這樣的程式又有什麼樣的問題呢?


能不要用模數運算(modulo operation)嗎?

可能是因為之前做過一連串 bitwise operation 的運算,看到這邊使用了取餘數的模數運算直覺就想到是否也是可以用別的簡便運算取代?要判斷三或五的倍數想到的自然就是國小教的「三的倍數是所有位數相加為三倍數」「五倍數結尾是五或零」,不過很可惜的是這些都是在十進位表示之下才會具有的特性;同時這樣的實做很有可能捨本逐末有更差的效率

最後這樣的實做可能會導致運算時間與數字大小多寡掛勾,也就是說無法達到「常數時間」的時間複雜度,這會有 timing attack 的資訊安全疑慮

分支判斷是否過多?

你可以從上方範例程式碼中看到每次迴圈都需要兩次條件判斷,一旦要做條件判斷就會有 branch prediction 造成指令 pipeline 平行處理上的問題;如果可以以 bitwise operation 取代不但可以更好的達到指令等級的平行化,同時也不需要擔心條件判斷下不同執行路徑執行時間不同的 timing attack

每次重新記憶體分配同樣的 string literal 是否過於浪費記憶體空間?

這個問題事實上我一開始並沒有發現(可能是因為目前寫的程式都不太要求減少使用記憶體空間),但是在 jserv 老師的實做裡我發現老師最主要花心思在「如何 re-use 這些固定字串」

根據題意,每次要印出來的其實固定是 “fizz”, “buzz”, “fizzbuzz”, “[number]”就幾種排列組合,如果可以找到一個方式宣告一個固定的 string 對象就可以不用像原作一樣分開處理不同條件判斷


前面部份針對「我目前看到的」原始程式分析能夠改善的方向,以下則是 jserv 老師放在 github 上的改善版專案程式碼實做部份

#include <stdio.h> 
#include <string.h>
/*
* Based on the way printf manipulating format strings, we can specify * a single string for each kind of thing we want to print, in power of * two lengths.
*
* For a single integer, “%u” length == 2
* For fizz or buzz, “fizz” or “buzz” length == 4
* For fizzbuzz, length == 8
*
* Even better, we can set up a string so the starts of our format are at
* powers of 2
*
* “fizzbuzz%u”
* 0 4 8
*/
#define MSG_LEN 8
#define DIV5(x) ((x & 2) >> 1)
#define DIV3(x) (x & 1)
int main(int argc, char **argv)
{
for (size_t i = 1; i <= 100; i++) {
/* Define mask/flags for storing divisibility */
unsigned int mask = 0;
/* Create bitmask of the form 000000ab
a — divisible by 5
b — divisible by 3 */
mask |= (!(i % 5) << 1) | !(i % 3);
unsigned int start =
// Shift down 1 if div5
(MSG_LEN >> DIV5(mask))
// Shift down another 4 if div3 */
>> (DIV3(mask) << 2);
// Default length is 2
// Shift up by one for each bit set
unsigned int length = (2 << (DIV3(mask))) << DIV5(mask);
// Shift up by 1 for each bit set
char fmt[MSG_LEN + 1];
strncpy(fmt, &”FizzBuzz%u”[start], length);
fmt[length] = ‘\0’;
printf(fmt, i);
printf(“\n”);
}
return 0;
}

可以看到這份程式有很優質的地方是「有附註解」,這對理解整份程式碼怎麼進行有極大幫助(好久沒看過這種詳細註解的程式碼覺得真感動)

註解一開始就寫到「以一個單一字串,(透過調整 offset 的方式),印出在不同情況下對應的 substring」

而這個神奇的單一字串就是 “fizzbuzz%u” ,後面的 %u 是該次輪到的數字(如果不是 3 或 5 的倍數要印出來)


我們知道 C 語言事實上並沒有 string 這樣的型態,而是透過字元陣列實現,那麼今天如果我們需要針對不同場合印出 fizzbuzz%u 的 substring,那麼我們只要知道「從哪裡開始印」(starting array index) 跟「印多少」(element count)就好了,舉例來說,可以被 3 整除的情況下,我們要印出 “fizzbuzz%u” [0] ~ “fizzbuzz%u” [3] 的部份


接下來我們可以看到 #define 這部份預處理,這部份只是要從之後的 mask 把不同狀況的代表值拿出來,這個 mask 實際上就是「可被三整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」

這樣的技巧事實上在 bitwise operation 上很常見,直接利用這些類似布林值概念的值去運算,而不是作為條件判斷的判斷式,這樣才能有效的減少 branch prediction

同時大型專案很喜歡用 #define 這樣的 macro,一方面是因為大專案的大型界面設計很多時候會導致某個 function call 事實上只是呼叫另外一個子函式實做,類似中間人的概念以方便抽象理解,但是這會導致 function call 的成本增加,因此大多數這類中間人概念的 function 都會以 #define 在 preprocess 時期就直接置換成對應的實做

此外需要注意到那個括弧是必要的,很多的 #define macro 在設計的時候會為了防止預處理時因程式執行邏輯順序錯亂而加上這些防範措施,以這個小括弧為例,主要是防止 operator priority 不同造成的問題;你有時候也可能會看到 do { … } while (0),這主要是為了防止一些像是 switch, goto 語法會找最近的跳躍點的問題(jserv 老師 你所不知道的 C 語言講座 中有提到),一開始看的時候我真的很黑人問號加這個沒有意義的 do while 到底是想做什麼


之後就是根據不同狀況用 bitwise 調到自己想要的數字(像是整除 3 就調成 start = 0, length = 4;整除 5 就調成 start = 4, length = 4 等等),由於這部份實在是多寫 bitwise (把 CMU CS:APP 的 data lab 做過一次就差不多了)就大概抓的到感覺的部份,因此就不多加解釋


以下就是各種寫法的效能分析了,測試環境是在 Linux Mint 18.1上

首先是第一種最暴力的解法

#include <stdio.h>int main () {
for (unsigned int i = 1; i < 100; i++) {
if (i % 3 == 0) printf(“fizz”);
if (i % 5 == 0) printf(“buzz”);
if ((i % 3 != 0) && (i % 5 != 0)) printf(“%u”, i);
printf(“\n”);
}
}

連 if else 都沒有用的情況下,測試下的結果是

原先暴力直覺解法

下列則是 jserv 老師的程式碼測試結果

減少分支後的結果?

可以看到儘管用時減少了 4.3 % ,同時 cache-miss rate 也降低了 20.2 %,但是 branch 分支數量並沒有減少 ?明明改善過後的程式碼已經沒有條件判斷但是還是會有 branch 分支且還會有 branch-misses ?


另外為了分析記憶體使用情況,我用 valgrind -tools=massif 加上 massif-visualizer 來分析

原始暴力解下會用到 1KB
bitwise 改善版圖跟上面一模一樣

最後意外的發現這麼努力的改善程式行為,盡量根據計算機特性去最佳化程式不但時間效益不是很巨大,同時記憶體使用情況也沒有改善很多?

真的是不實測,永遠不知道結果是好是壞 =(

陳奕熹

Written by

陳奕熹

應該要是一個工程師的……

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade