Re: [請益] 演算法以及微處理機?

[jengjian (賺錢花錢賺錢花錢)]

閒著沒事來解釋一下演算法工程師這個工作內容

先定義什麼叫演算法，演算法就是一個處理問題的方法。

可以在有限的步驟跟時間內解決問題而且得到答案就叫做演算法。

至於什麼叫有限的步驟跟時間，我用下面一個例子做解釋

問題: 算出1到n的正整數合

解法一:
for(i=1; i<=n; i++)
{
   sum += i;
}

解法二:
sum = (1+n)*n/2;

以上兩個方法都叫演算法，但傻子都知道那一個效率比較好。但如果說平台上
沒有支援乘或除的指令集，那勢必第二個方法就沒辦法實作。那接下來就只能
用第一種方法嗎??

解法三:
for(i=0x80000000; i!=0; i=i>>1)
{
   sum <<= 1;
   if(i&n)
   {
      sum += (1+n);
   }
}
sum >>= 1;

這個解法只要平台有移位跟邏輯運算就可以使用的演算法。雖然還是比第二個方法慢，
但至少time complexity從 O(n) 降到 O(log n)，但解法三是不是最好的演算法，除
非我可以去證明它是世界上最快的演算法(在剛剛的條件之下)，不然它只是一個方法。

好的演算法工程師，有辦法去了解一個問題，了解處理問題的工作平台限制，時間限制
找到一個最適合系統的最佳的解法。甚至有些演算法工程師還會直接把剛剛的演算法
直接設計成一個 hardware component 去處理它的問題，只要系統可以那就可以。


一個好的演算法工程師需要具備

1. 了解問題的能力
2. 了解這個問題已經存在的演算法 (這才是重點)
3. 根據平台的限制與資源選擇一個好的演算法或是開發一個新的演算法
4. 驗證與說明自己選擇的演算法跟其他演算法的優缺點

這樣一個演算法工程師要修什麼課，就要問天，才會知道了。

因為這是要取決於你處理的問題方向以及處理問題的平台。


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.130.53.5
推 parking111:GJ
推 hikaru677:超專業<(_ _)>
推 genius945:推
推 ilovebbs:解法3好酷....XD
推 thinkniht:我覺得要當一個好的演算法工程師最重要的是邏輯能力
→ thinkniht:不過有時一個演算法職缺，並不一定真的需要...
→ thinkniht:好的演算法工程師XDDD(不知是否有人能理解我的意思...)
→ ken1325:不懂樓上的意思
推 bxxl:實際上是看當時找得到怎樣的人就用吧,也不一定要很好的人.
推 KiroKu:解法三 為何i起始值不是n?
→ leav:因為那個i只是個bit mask, 從32-bit int的MSB開始掃
推 eterbless:演算法除非真的上戰場 不然很多都可以嘴砲XD
推 amozartea:解法二才是數學...解法三根本是insane...
推 wzbird:我也覺得三在定義上不算"演算法" 只能說是寫程式的技巧
→ wzbird:不過或許業界定義的演算法跟書上的不盡相同吧
推 amozartea:那不是演算法  是偷吃步....
→ amozartea:>>1和/2在演算法上並沒有差別  但在機器上有差...
推 genius945:小弟資質努頓....有人可以說一下3的想法嗎= =+
→ amozartea:我每次看到解法三這種code都很想殺人..硬體公司一堆這種
→ amozartea:有個int要乘0.3(不用到float) 正常解:寫*3/10
→ amozartea:加速解 * 77 >> 8  ,
推 wzbird:我覺得業界會喜歡這樣寫是有他的必要, 因為就是比較快
→ wzbird:業界比人家快就是強, 但是要稱"演算法"比較值得商榷
→ wzbird:還要配合平台有什麼HW的話就只是單純程式的技巧了
→ wzbird:少第三句XD  "我認為演算法應該是用紙筆就可以推導的"
→ leiyan:乘除法最後還是要變成加減法的動作 不值得捨棄維護性
推 azureblaze:>>1 /2 compiler應該會幫你處理好吧
→ azureblaze:沒事不要覺得自己optimize會比compiler強
→ azureblaze:而且這不是profile出來的瓶頸，就只是找維護的人麻煩
推 fantoccini:回應樓上: 原po有說如果平台不支援 乘除指令
→ fantoccini:如果是HW  的確是要自己轉 /2 = >>1
推 snaketsai:不要跟Compiler作對......
→ azureblaze:不支援指令理論上compiler也要幫你想辦法
→ azureblaze:就像沒有FPU還是得幫你做慢到爆的軟體浮點
→ azureblaze:至少乘除換位移應該是基礎最佳化功能
→ azureblaze:除非你用的是什麼不支援乘除的奇妙語言
推 fantoccini:做硬體的演算法就沒啊  必須把乘除法器換成位移運算
→ fantoccini:每一個乘除法器 對硬體都是成本考量
推 fantoccini:做硬體的思維和軟體不同
推 gpmm:看到討論演算法的文章，就不禁想到前幾個月的雷神之鎚 3
→ gpmm:http://0rz.tw/o6c6T  http://0rz.tw/6dmWv
推 bxxl:做硬體根本也不用shift,接線直接錯開1bit
推 nhtyjm:好的演算法工程師在台灣領多少?
推 snaketsai:我覺得bitwise很難維護= ="如果單純只是要測效能，也許
→ snaketsai:OK，但是真的用在開發當中會讓夥伴很累@@
→ PEIRON:To gen: 解法三就是把小學教的直式乘法實做出來
→ PEIRON:只不過是二進位版本
推 LaPass:難維護就難維護，反正是包在底層，上面的人看不到啊.....
→ genius945:後來看懂了= ="感謝,比較少摸底層硬體很少看這種寫法= =
推 xyziscariot:GJ  這才是專業的!!
推 FukadaKyoko:為啥我把解法3跑起來答案不是5050啊? = =?!
→ FukadaKyoko:設置是i為int, sum為int初始0
→ lovdkkkk: i 右移時左側會補 1 或補 0 不一定, 答案會不一樣
推 funkastic:有趣~
→ PEIRON:右移通常都是補0吧~ Fuka 你不要一下子就n代100呀，試試n=3
→ PEIRON:然後手算一次，不要真的去寫程式算(因為寫錯難debug)
推 ggx1030:這種優化是編譯器該做的事,可讀性高易維護比較重要
→ uranusjr:無號和有號的補法不一樣, 使用位移的時候請愛用無號數
推 FukadaKyoko:我的跑起來是補1 XD vs2008
→ FukadaKyoko:了解了 因為我用的是int~
→ FukadaKyoko:我再守算看看 感謝各位大大XD
推 ku399999:寫底層就不一定是維護性至上了吧,一定有些地方需要取捨
→ ku399999:不然上層寫了稍差一點就慢到破表了