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. 驗證與說明自己選擇的演算法跟其他演算法的優缺點
: 這樣一個演算法工程師要修什麼課，就要問天，才會知道了。
: 因為這是要取決於你處理的問題方向以及處理問題的平台。
我想回應一下這篇文章
1.我覺得除了演算方法外...實現方法也很重要
假設有個數字陣列
int[] array;
要取其陣列內容總和
常見方法就是使用
int sum=0;
for(int i=0;i<array.length;i++)
{
sum+=array[i];
}
以時間複雜度來講是O(n)
但如果換另一種寫法
sum+=array[0]+array[1]+array[2]+...以此類推
一個個加起來的話
我記得我以前用C#測試是有比較快一點
以時間複雜度來說是一樣的
但執行時間是有差別的
當然...我相信大家不會為了減少那一點時間用那麼麻煩的寫法的XD
2.沒經過測試證明
不要太相信自己的寫法真的比較快
有時候你以為比較快的改法
但現實可能就是沒甚麼差別甚至反而更慢
有時候你以為沒甚麼差的改法
反而減少很多的執行時間
這點是我以前調整某個跑超慢的程式速度的感想
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.161.22.157
推
12/21 20:20, , 1F
12/21 20:20, 1F
我只是覺得這個比較適當拿來當例子
也沒想到更好的
如果不認同我第一點或者有更好的例子的話
可以提出來:P
※ 編輯: thinkniht 來自: 1.161.22.157 (12/21 20:27)
※ 編輯: thinkniht 來自: 1.161.22.157 (12/21 20:27)
→
12/21 20:46, , 2F
12/21 20:46, 2F
→
12/21 20:46, , 3F
12/21 20:46, 3F
→
12/21 20:46, , 4F
12/21 20:46, 4F
→
12/21 20:47, , 5F
12/21 20:47, 5F
→
12/21 20:48, , 6F
12/21 20:48, 6F
→
12/21 20:49, , 7F
12/21 20:49, 7F
→
12/21 20:49, , 8F
12/21 20:49, 8F
→
12/21 20:50, , 9F
12/21 20:50, 9F
→
12/21 20:50, , 10F
12/21 20:50, 10F
→
12/21 20:51, , 11F
12/21 20:51, 11F
→
12/21 20:52, , 12F
12/21 20:52, 12F
→
12/21 20:52, , 13F
12/21 20:52, 13F
推
12/22 01:26, , 14F
12/22 01:26, 14F
→
12/22 01:27, , 15F
12/22 01:27, 15F
→
12/22 01:29, , 16F
12/22 01:29, 16F
→
12/22 01:35, , 17F
12/22 01:35, 17F
→
12/22 01:36, , 18F
12/22 01:36, 18F
推
12/22 12:51, , 19F
12/22 12:51, 19F
→
12/22 12:52, , 20F
12/22 12:52, 20F
→
12/22 12:53, , 21F
12/22 12:53, 21F
→
12/22 12:53, , 22F
12/22 12:53, 22F
推
12/22 13:57, , 23F
12/22 13:57, 23F
→
12/22 13:57, , 24F
12/22 13:57, 24F
我遇過一個情況 細節不方便說太細
這邊大概描述一下:
原本寫法是這樣的
有個兩層迴圈
[第一個迴圈 變數為i]
{
[第二個迴圈 變數為j]
{
...
//使用i和j分別取得對應的資料和做處理
}
}
我後來改成:
[第一個迴圈 變數為i]
{
使用i取得對應的資料，並存入區域變數中
[第二個迴圈 變數為j]
{
...
//使用j分別取得對應的資料和使用區域變數做處理
}
}
一般算時間複雜度的話...
我想兩種寫法都是O(n^2)
但是第二種寫法是把在第二層迴圈中會做的事情抽出迴圈外
很理所當然的...因為執行次數減少，所以執行時間也被減少了...
這種情況在當時處理的程式出現過很多次
累積的[使用i取得對應的資料]的次數並不少
這類的做法後來減少了不少執行時間而且也不影響輸出結果
另外這[取得對應的資料]都會產生新的實體
減少執行次數不僅減少執行時間，同時也能減少建立的實體的次數
雖然不過就區域變數而已，之後會自動被GC...
但是這樣的區域變數數量一多...對時間與空間的影響也是不該忽視的
這也就是我想表示的...
有時實作演算方法的寫法也很重要
※ 編輯: thinkniht 來自: 114.42.237.20 (12/23 22:25)
→
12/24 20:23, , 25F
12/24 20:23, 25F
→
12/24 20:23, , 26F
12/24 20:23, 26F
→
12/24 20:26, , 27F
12/24 20:26, 27F
討論串 (同標題文章)
Soft_Job 近期熱門文章
PTT職涯區 即時熱門文章