PTT職涯區 / Soft_Job (軟體人)

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

看板Soft_Job (軟體人)作者 (賺錢花錢賺錢花錢)時間13年前 (2012/12/20 18:48), 編輯推噓29(29推 0噓 34→)
留言63則, 27人參與, 最新討論串7/12 (看更多)
閒著沒事來解釋一下演算法工程師這個工作內容 先定義什麼叫演算法，演算法就是一個處理問題的方法。 可以在有限的步驟跟時間內解決問題而且得到答案就叫做演算法。 至於什麼叫有限的步驟跟時間，我用下面一個例子做解釋 問題: 算出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
推
12/20 20:01, , 1F
GJ
12/20 20:01, 1F
推
12/20 20:34, , 2F
超專業<(_ _)>
12/20 20:34, 2F
推
12/20 20:37, , 3F
推
12/20 20:37, 3F
推
12/20 21:37, , 4F
解法3好酷....XD
12/20 21:37, 4F
推
12/20 22:15, , 5F
我覺得要當一個好的演算法工程師最重要的是邏輯能力
12/20 22:15, 5F
→
12/20 22:16, , 6F
不過有時一個演算法職缺，並不一定真的需要...
12/20 22:16, 6F
→
12/20 22:17, , 7F
好的演算法工程師XDDD(不知是否有人能理解我的意思...)
12/20 22:17, 7F
→
12/20 22:51, , 8F
不懂樓上的意思
12/20 22:51, 8F
推
12/20 23:44, , 9F
實際上是看當時找得到怎樣的人就用吧,也不一定要很好的人.
12/20 23:44, 9F
推
12/20 23:51, , 10F
解法三 為何i起始值不是n?
12/20 23:51, 10F
→
12/21 00:12, , 11F
因為那個i只是個bit mask, 從32-bit int的MSB開始掃
12/21 00:12, 11F
推
12/21 00:37, , 12F
演算法除非真的上戰場 不然很多都可以嘴砲XD
12/21 00:37, 12F
推
12/21 13:59, , 13F
解法二才是數學...解法三根本是insane...
12/21 13:59, 13F
推
12/21 14:22, , 14F
我也覺得三在定義上不算"演算法" 只能說是寫程式的技巧
12/21 14:22, 14F
→
12/21 14:23, , 15F
不過或許業界定義的演算法跟書上的不盡相同吧
12/21 14:23, 15F
推
12/21 14:24, , 16F
那不是演算法 是偷吃步....
12/21 14:24, 16F
→
12/21 14:24, , 17F
>>1和/2在演算法上並沒有差別 但在機器上有差...
12/21 14:24, 17F
推
12/21 14:25, , 18F
小弟資質努頓....有人可以說一下3的想法嗎= =+
12/21 14:25, 18F
→
12/21 14:25, , 19F
我每次看到解法三這種code都很想殺人..硬體公司一堆這種
12/21 14:25, 19F
→
12/21 14:26, , 20F
有個int要乘0.3(不用到float) 正常解:寫*3/10
12/21 14:26, 20F
→
12/21 14:26, , 21F
加速解 * 77 >> 8 ,
12/21 14:26, 21F
推
12/21 14:34, , 22F
我覺得業界會喜歡這樣寫是有他的必要, 因為就是比較快
12/21 14:34, 22F
→
12/21 14:34, , 23F
業界比人家快就是強, 但是要稱"演算法"比較值得商榷
12/21 14:34, 23F
→
12/21 14:36, , 24F
還要配合平台有什麼HW的話就只是單純程式的技巧了
12/21 14:36, 24F
→
12/21 14:37, , 25F
少第三句XD "我認為演算法應該是用紙筆就可以推導的"
12/21 14:37, 25F
→
12/21 15:23, , 26F
乘除法最後還是要變成加減法的動作 不值得捨棄維護性
12/21 15:23, 26F
推
12/21 16:20, , 27F
>>1 /2 compiler應該會幫你處理好吧
12/21 16:20, 27F
→
12/21 16:21, , 28F
沒事不要覺得自己optimize會比compiler強
12/21 16:21, 28F
→
12/21 16:22, , 29F
而且這不是profile出來的瓶頸，就只是找維護的人麻煩
12/21 16:22, 29F
推
12/21 18:58, , 30F
回應樓上: 原po有說如果平台不支援 乘除指令
12/21 18:58, 30F
→
12/21 18:59, , 31F
如果是HW 的確是要自己轉 /2 = >>1
12/21 18:59, 31F
推
12/21 19:55, , 32F
不要跟Compiler作對......
12/21 19:55, 32F
→
12/21 21:29, , 33F
不支援指令理論上compiler也要幫你想辦法
12/21 21:29, 33F
→
12/21 21:30, , 34F
就像沒有FPU還是得幫你做慢到爆的軟體浮點
12/21 21:30, 34F
→
12/21 21:32, , 35F
至少乘除換位移應該是基礎最佳化功能
12/21 21:32, 35F
→
12/21 21:32, , 36F
除非你用的是什麼不支援乘除的奇妙語言
12/21 21:32, 36F
推
12/21 21:50, , 37F
做硬體的演算法就沒啊 必須把乘除法器換成位移運算
12/21 21:50, 37F
→
12/21 21:51, , 38F
每一個乘除法器 對硬體都是成本考量
12/21 21:51, 38F
推
12/21 21:54, , 39F
做硬體的思維和軟體不同
12/21 21:54, 39F
推
12/21 22:49, , 40F
看到討論演算法的文章，就不禁想到前幾個月的雷神之鎚 3
12/21 22:49, 40F
→
12/21 22:50, , 41F
12/21 22:50, 41F
推
12/21 23:12, , 42F
做硬體根本也不用shift,接線直接錯開1bit
12/21 23:12, 42F
推
12/22 00:22, , 43F
好的演算法工程師在台灣領多少?
12/22 00:22, 43F
推
12/22 01:32, , 44F
我覺得bitwise很難維護= ="如果單純只是要測效能，也許
12/22 01:32, 44F
→
12/22 01:33, , 45F
OK，但是真的用在開發當中會讓夥伴很累@@
12/22 01:33, 45F
→
12/22 10:46, , 46F
To gen: 解法三就是把小學教的直式乘法實做出來
12/22 10:46, 46F
→
12/22 10:46, , 47F
只不過是二進位版本
12/22 10:46, 47F
推
12/22 11:36, , 48F
難維護就難維護，反正是包在底層，上面的人看不到啊.....
12/22 11:36, 48F
→
12/22 13:59, , 49F
後來看懂了= ="感謝,比較少摸底層硬體很少看這種寫法= =
12/22 13:59, 49F
推
12/22 16:30, , 50F
GJ 這才是專業的!!
12/22 16:30, 50F
推
12/22 16:46, , 51F
為啥我把解法3跑起來答案不是5050啊? = =?!
12/22 16:46, 51F
→
12/22 16:47, , 52F
設置是i為int, sum為int初始0
12/22 16:47, 52F
→
12/22 18:47, , 53F
i 右移時左側會補 1 或補 0 不一定, 答案會不一樣
12/22 18:47, 53F
推
12/22 19:02, , 54F
有趣~
12/22 19:02, 54F
→
12/22 20:33, , 55F
右移通常都是補0吧~ Fuka 你不要一下子就n代100呀，試試n=3
12/22 20:33, 55F
→
12/22 20:36, , 56F
然後手算一次，不要真的去寫程式算(因為寫錯難debug)
12/22 20:36, 56F
推
12/22 22:32, , 57F
這種優化是編譯器該做的事,可讀性高易維護比較重要
12/22 22:32, 57F
→
12/23 14:45, , 58F
無號和有號的補法不一樣, 使用位移的時候請愛用無號數
12/23 14:45, 58F
推
12/24 17:13, , 59F
我的跑起來是補1 XD vs2008
12/24 17:13, 59F
→
12/24 17:13, , 60F
了解了 因為我用的是int~
12/24 17:13, 60F
→
12/24 17:13, , 61F
我再守算看看 感謝各位大大XD
12/24 17:13, 61F
推
12/29 18:46, , 62F
寫底層就不一定是維護性至上了吧,一定有些地方需要取捨
12/29 18:46, 62F
→
12/29 18:46, , 63F
不然上層寫了稍差一點就慢到破表了
12/29 18:46, 63F
‣ 更多 jengjian 的文章
文章代碼(AID): #1Gqkq67T (Soft_Job)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 7 之 12 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共12篇)
Soft_Job 近期熱門文章
更多 近期熱門文章 >>
PTT職涯區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 jengjian 的文章
文章代碼(AID): #1Gqkq67T (Soft_Job)