Re: [問題] 學code要看天分嗎?

[tropical72 (藍影)]

以下技巧與心得參考一下。

零、 請先考慮可讀性

任何一段程式碼可讀性應為第一優先考量，為何？
這是一個掀起議戰的話題，因即使你寫得非常累贅，
compiler 還是有能力幫你整理過、幫你優化過 (記得開 O2)。

但任何一段程式碼若太過追求精簡，二、三個月再回來看它，
很容易忘記之前為何會這麼寫，可能還要再慢慢拆回來看。

真的想練習簡潔碼的話，有個題目可以讓你練將近一個月 - 質數問題。

分別以

暴力法、暴力優化、2n 法則、sqrt(n) 法則、6n 法則、
質數篩法、質數篩法 2n 法則、質數篩法 6n 法則、
質數篩法 bitwise 操作 (每個數用 1 個 bit 去存，用不到 char 或 int)、
線性篩法

十個主題實作。注意，同一份 code 可能會寫 3 次並不意外，
因後面都在作化簡、整理敘述句、去除多餘變數動作。

質數問題做累、做煩的話，建議直接再把以前的 homework 抓出來，
重新練習2~3次。


壹、 先對 bitwise operator 有一定認識

bitwise operator application，變態可以到很變態，
但其實沒很建議去硬鑽，原因在於到最簡化後維護性、可讀性反而沒那麼高。

即使看別人的 sample code，一開始寫起來並沒那麼短碼、複雜，
只是初版寫完之後，會做以下動作

ˇ 原本要 2 個回圈的動作，是否可合併成一個回圈。
ˇ 原本用 if-else 之寫法，是否可改成非 if-else 寫法。
ˇ 是否有累贅之變數存在。

即使是一段小小簡單的 code，寫完第一篇再 review 、思考，最後整理成一段。

關於 bitwise 之操作，上網 google bitwise hacker 會有很多資訊，
太難的就不要去鑽它，原因有二，
第一點是它們 present 出來的背景知識可能太過雄厚，又或要徹底了解它們並不容易。
第二點是主因，它們的寫法經過 compiler 動過手腳後 "未必" 會比較快，

最常見的例子是 swap(a,b)，一般的寫法

void swap(int *a, int *b){
    int t=*a;
    *a = *b;
    *b = t;
}

或這麼寫

void swap(int *a, int *b){
    int x=*a, y=*b;
    *a=y, *b=x;
}

但 bitwise 寫法

void swap1(int *a, int *b) {
    *a^=*b;
    *b^=*a;
    *a^=*b;
}

其實這寫法對現代的 compiler 而言速度反而是比較慢的。
至於什麼時候要一般寫法、什麼時候用 bitwise 寫法，
心得大致如下

ˇ 能用 bitwise 及 (加減法) 取代掉 if-else 時  (不包含 bitwise+乘除)。
ˇ 能用 bitwise 取代特殊之 乘除法、取模 運算時。
ˇ 一些比較特殊的數學運算，較有名的如算 log2(x) 整數時。 


其它較基層的東西反而不建議用 bitwise 去完成，如

× bitwise 取絕對值 (pointer + and)、
× bitwise 判斷是否相等 ( xor)、
× bitwise 取負數 ( ~a+1)

效能上都是慢。


貮、 合理條件內，盡可能縮減 if 判斷


1. 累計功能

善用判斷式 true 傳回 1 / false 傳回 0 之特性。

int i, cnt;
for(i=cnt=0; i<10; ++i)
   if(i%3==0) cnt=cnt+1;

換成

for(i=cnt=0; i<10; ++i)
    cnt+=(i%3==0)

2. 熟悉回圈特性

不是說從 for 換 do-while、while，而且同一份 code、同一種 loop 寫法就很多種，
可以自己花點時間體會，效率未必會比較好，但主要是訓練觀查力與思考力。

假設要找某陣列裡第一個15之元素。

int i, arr[n];
for(i=0; i<n; ++i)
   if(arr[i]==15) break;
if(i<n) puts("find");

換成
for(i=0; i<n && a[i]!=15; ++i);
if(i<n) puts("find");

要找非 0 元素更方便

for(i=0; i<n && !a[i]; ++i)
if(i<n) puts("find");


再用暴力法判斷質數為例，提四種寫法 (還可以再擴)。

(method 1)
int IsPrime=1, Number=17;
for(int i=2; i<Number; ++i) {
    if(Number % i==0) {
       IsPrime=0;
       break;
    }
}
if(IsPrime) puts("prime");

(method 2)
int IsPrime=1, Number=17;
for(int i=2; i<Number; ++i) {
    if(Number % i==0) {
        i = Number;
        IsPrime=0;
    }
}
if(IsPrime) puts("prime");

(method 3)
int IsPrime=1, Number=17;
for(int i=2; i<Number && IsPrime; ++i)
    if(Number % i==0) IsPrime=0;
if(IsPrime) puts("prime");


(method 4 - IsPrime 被去掉了)
int i, Number =17;
for(i=0; i<Number  && (Number%i) ; ++i);
if(i==Number ) puts("prime");    

這些技巧在 while、do-while 也大同小異，大多在「終止條件」那裡花心思。

---

參、 小結

下面是最後一點心得

1. 先寫一段自己憑直覺、憑流程寫出來，可正常運作之程式碼。
2. 檢查 if-else 是否能以 bitwise 合理取代。
3. 檢查回圈敘述是否能被合併到終止條件 (提醒，有時合併未必是好處)
4. 以上步驟完成後，檢查是否有不必要或多餘變數。
5. 再回到步驟 2 ，重覆進行2~3次。

我不算是天份型，但我想應該不多人有恆心可以強迫自己
每天 coding + 看書 + 看網路上的code 4hrs (我知道這算少) 長達半年，
何況你也才剛上完一學期的程式課程而已，這還只是初步而已。

一點意見，參考。

--
    No matter how gifted you are,
       alone, can not change the world. 

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.78.41
推 diabloevagto:推！
→ diabloevagto:請問你上網看code都到那邊看？
   狂搜高手網誌，三份程式設計論壇，csdn(高手會有blog),stack overflow.
   二份適合初學者之地下論壇。

推 sjgau:讚！
推 flere:看完uva題目後仔細想想寫寫看,再找別人的解法看怎麼寫
推 target8917:有時if可轉成switch，增加可讀性
   同意。有時便變成了「可讀性」與「簡潔性」之取捨問題。

推 heymei0421:好文...
→ firejox:使用bitwise... 樹狀數組應該還蠻經典的...
推 tonyhsie:找某陣列裡第一個15之元素  把if搬進for迴圈 好像沒差啊?
   是沒差，不過以原po所說的「簡潔」，不就和原本程式碼差異不大嗎？
   這部份也特別聲明了，是在練習對回圈熟悉度、思考力、觀察力。

推 siriusu:同意
推 Raymond0710:好文推
→ loveme00835:好文雅
→ angleevil: cnt+=(i%3==0)<--這種寫法避免掉.
→ angleevil:有時候是看你對自己的要求多高.還有資料結構,演算法
→ angleevil:計算結構等理論的書打下基礎有多深. 實際上kiss原則
→ angleevil:是無數次的經驗累積和模仿得來的.天份只是催化劑而已
→ angleevil:實際上還是下苦功和多點人文的養成會比較好
→ stimim:http://www.dotspace.idv.tw/sofeeng/Duplicate_Code.htm
推 stonehomelaa:C不保證"true" 是1喔 cnt+=(i%3==0) 會出事滴
推 littleshan:standard 6.5.9p3 比較的結果相等時為1 不相等時為0
→ angleevil:我沒考慮到那層,我只是覺得這寫法要避免,這是個不小心
→ angleevil:就會造成bug的壞習慣.儘管是拿來做例子.
→ tonyhsie:內文貳裡的兩種case if判斷只是在字面上消失而已
→ tonyhsie:範例程式實際上還是一樣要作if判斷 這樣作法 比較不推
推 stonehomelaa:不知道C99有訂了 感謝指正
真想不到這段心得會引人這麼多高人的建議，回到 主旨面，原 po 裡一段話
每次看別人寫的code, 就覺得相當簡潔
我也同意二個構面會有一定衝突性：簡潔、可讀與維護，
同時 簡潔與效能並不搭上任何絕對之關係 ，可能小弟在 part 2 舉出的例子沒很好，
但已強調，該段之重點是在鼓勵熟悉 迴圈特性、多思考、多觀察，
對於基本面成長我認為有不少助益，但非鼓勵一定要用簡潔性之寫法，
原因便各版友也已從可讀性、效率面提及，
一樣的效率，程式碼較精簡，但能不能接受、好不好都是看個人，
不就像是原 po 所提到的 2 行 gcd 是一樣的意思嗎，實際上只是寫法簡潔，效能一樣 :)

※ 編輯: tropical72      來自: 180.177.78.41        (12/11 20:43)
推 deangogi:可以請問你說的那些論壇是哪些嗎
→ deangogi:我只知道stack overflow 0.0
→ tropical72:Programming-Club、Stack Overflow、CSDN、(CodeProj.)
→ tropical72:地下論壇就不放上了。
→ tropical72:不好意思，我忘了最重要的 ptt，其實這裡高手真的很多.
→ tonyhsie:簡潔應該還是要考量效能and/or可讀性 如果兩者皆不成立
→ tonyhsie:這樣的簡潔 只能減少程式碼的size 好像沒什麼作用啊 @@
→ tonyhsie:像貳之1 改寫後多了數次 cnt += 0 這種類似 nop 的運算..
→ tonyhsie:另一個問題是angleevil大推文 程式碼本身有隱形前提存在
→ tonyhsie:true=1 false=0存在 程式的正確性 是建立在隱形前提上
→ tonyhsie:風險跟後續的維護花費 便提高不少 一點淺見 還請見諒 @@"
→ tropical72:謝謝建議 :) 但我要說的是,我認為 cnt+=(i%3==0) 去掉
→ tropical72:branch 後,雖有數次 nop,但整體代價視 predict.err.定
→ tropical72:可能我運氣較好,往往去brach後效能快一點。
→ tropical72:至於true=1,false=0這前提,我以為這知識和假定電腦為二
→ tropical72:補數系統一樣,何況不少程式語言也有些約定.故以為常識.
→ tropical72:                                 此
→ diabloevagto:之前看過有些會定義true是1==1，false是1==0
→ tropical72:定義true=1,false=0的情況常在 C language 見到,原因是
→ tropical72:C 沒bool,故有時會再多加 typedef int bool;
→ tropical72:或 typedef unsigned char; 之類的.
→ tropical72:sorry,沒看清d大推文所敘,上面三樓跳了tone..
→ diabloevagto:所以好像有些定義不是像我們想的xdd
→ tropical72:那就要去看這篇文章了。 #1EPPULmS
→ angleevil:厄,我應該打清楚點, 那個寫法真正頭痛的問題是在人
→ angleevil:今天只是剛好i%3==0式子中,不小心打成=會被檢查出錯誤
→ angleevil:可是如果換成(i == 0)寫法,不小心寫成(i = 0)時.編譯器
→ angleevil:無法幫你找警告的(我已經用-Wall -Wextra)
→ angleevil:我不像版上一堆高手專研演算法或啃標準書.幾乎我給建議
→ angleevil:都是排版和撰寫習慣.這個東西是非常細微的習慣.但是我
→ angleevil:知道很多人是略過它.
→ xatier:如果寫成 i=0 會噴警告的話就不會有 a=b=c=0 這種慣用法了
→ angleevil:if (i = 0)會喔,但是(i = 0)不會.
→ shadow0326:為什麼我的gcc不會警告 if (i = 0)   o_0"
→ shadow0326:我已經加了-Wall -Wextra -pedantic
→ angleevil:警告：建議在做為真值的賦值敘述前後加上括號<-這讓很多
→ xatier:@angleevil: 我是指放在 if 外面的 i=0 XD
→ xatier:總不可能有人寫 if( a=b=c=0 ) 吧XDDDDD
→ angleevil:人霧煞煞. 實際上它的意思是把=和==做一個區隔.
→ angleevil:xatier,壞習慣一旦養成,會造成很多天兵code.尤其是趕專
→ angleevil:案時,特別會出現喔^.<. 不過這討論就停止吧!因為這偏向
→ angleevil:我個人習慣. ^.<我也很常寫出天兵code喔
→ xatier:不過 while ((c=getchar())) {...}  倒是蠻常見的XD
→ xatier:寫 code 時頭腦要清楚就好XD 只是常常腦袋不清楚就在趕工:P
→ angleevil:看來有結論了,所以我才不建議cnt+=(i%3==0)<-此習慣
→ angleevil:不過那是tropica舉例,只是給小建議.
→ angleevil:而且要讓true = 1,false = 0.要記得引用stdbool.h<-c99
推 littleshan:==的比較結果是傳回int，和stdbool.h無關
→ angleevil:<(__)> 謝謝littleshan
→ xatier:stdbool 是讓我們可以直接用 bool 來宣告東西吧@@?