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

[thinkniht (不下棋=.=)]

※ 引述《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
推 chchwy:你這招叫loop unrolling，現在大部分的編譯器都會幫做了
我只是覺得這個比較適當拿來當例子
也沒想到更好的
如果不認同我第一點或者有更好的例子的話
可以提出來:P
※ 編輯: thinkniht       來自: 1.161.22.157         (12/21 20:27)
※ 編輯: thinkniht       來自: 1.161.22.157         (12/21 20:27)
→ atst2:有時候效能的差, 跟輸入的數量級是有關的, 不同的演算法
→ atst2:在輸入少量的時候可能沒什麼差異，但到一定數量級以上，差別
→ atst2:就出來了.
→ atst2:舉個例子來說, iOS現在有提供Fast Enumerate，另外也有提供
→ atst2:Concurrent Enumerate, 一般情形下，Fast Enumerate應該是最
→ atst2:快的，但在多核心的情況下，理論上Concurrent Enumerate，要
→ atst2:比Fast Enumerate更快. 可是實質上，要讓Concurrent Enu有用
→ atst2:資料最少要一百萬筆以上.那這樣的技術，在mobile device上,
→ atst2:用處就很少了,不如直接使用Fast Enumerate。
→ atst2:有時候，為了追求在實際的情景下無法發揮的效能，花太多心思
→ atst2:並不見得是好事.
→ atst2:但做為興趣來實證一下,倒也是不錯.
推 snaketsai:迴圈整開的話，編譯器有下優化選項應該都會作
→ snaketsai:像Gcc如果懶得調組合，下-O3就會作迴圈展開跟行內函式
→ snaketsai:抱歉講錯，要獨立開 -funroll-loops 這個選項的樣子@@
→ snaketsai:不過有些有些優化真的要手動去作，像是函數餵指標：
→ snaketsai:就應該要考慮到別名的問題：http://goo.gl/6jSK9
推 ckaha:不太懂調這些跟現代在處理的演算法的設計理念孰重孰輕
→ ckaha:一個要針對平台語言case by case 一個演算法在針對現有問題
→ ckaha:當陷入針對一個迴圈最佳化而且可能只有C/C++才能使用的技巧
→ ckaha:是不是應該要切出來給專業人士去弄
推 genius945:個人感覺是演算法是比較宏觀的,但這邊討論的有點像是同
→ genius945:樣O(n)的線性時間,在實務上如何讓5n化為n這樣@@"
我遇過一個情況 細節不方便說太細
這邊大概描述一下:
原本寫法是這樣的
有個兩層迴圈
[第一個迴圈 變數為i]
{
[第二個迴圈 變數為j]
{
...
//使用i和j分別取得對應的資料和做處理
}
}

我後來改成:
[第一個迴圈 變數為i]
{
使用i取得對應的資料，並存入區域變數中
[第二個迴圈 變數為j]
{
...
//使用j分別取得對應的資料和使用區域變數做處理
}
}

一般算時間複雜度的話...
我想兩種寫法都是O(n^2)
但是第二種寫法是把在第二層迴圈中會做的事情抽出迴圈外
很理所當然的...因為執行次數減少，所以執行時間也被減少了...

這種情況在當時處理的程式出現過很多次
累積的[使用i取得對應的資料]的次數並不少
這類的做法後來減少了不少執行時間而且也不影響輸出結果

另外這[取得對應的資料]都會產生新的實體
減少執行次數不僅減少執行時間，同時也能減少建立的實體的次數
雖然不過就區域變數而已，之後會自動被GC...
但是這樣的區域變數數量一多...對時間與空間的影響也是不該忽視的

這也就是我想表示的...
有時實作演算方法的寫法也很重要
※ 編輯: thinkniht       來自: 114.42.237.20        (12/23 22:25)
→ PEIRON:這樣類似把2n^2 改成 n + n^2 ，big O 上看不出差異
→ PEIRON:但實際上的確有差
→ PEIRON:基本上跟 genius 舉的 5n 跟 n 意思差不多呢