很多人認為,演算法是數學的內容,學起來特別麻煩。我們不能認為這種觀點是錯誤的。但是我們也知道,軟體是一種複合的技術,如果一個人只知道演算法,但是不能用編程語言很好地實現,那麼再優秀的演算法也不能發揮作用。
有一次,一個人問我:「你寫的都是小兒科的東西,幾十行代碼就能搞定,能不能整一點高深的演算法?」
我反問他什麼是他所理解的高深的演算法,他答覆說:「像遺傳演算法、蟻群演算法之類的。」於是我給了他一個遺傳演算法求解0-1背包問題的例子,並告訴他,這也就是幾十行代碼的演算法,怎麼理解成是高深的演算法?他剛開始不承認這是遺傳演算法,直到我給了他Denis Cormier公開在北卡羅來納州立大學伺服器上的遺傳演算法的源代碼后,他才相信他一直認為深不可測的遺傳演算法的原理原來是這麼簡單。
還有一個人直言「用三個水桶等分8升水」之類的問題根本就稱不上演算法,他認為像「阿法狗」那樣的人工智慧才算是演算法。我告訴他計算機下棋的基本理論就是博弈樹,或者再加一個專家系統。但是他認為博弈樹也是很高深的演算法,於是我給了他一個井字棋遊戲,並告訴他,這就是博弈樹搜索演算法,非常智能,你絕對戰勝不了它(因為井字棋遊戲很簡單,這個演算法會把所有的狀態都搜索完)。我相信他一定很震驚,因為這個演算法也不超過100行代碼。
對於上面提到的例子,我覺得主要原因在於大家對演算法的理解有差異,很多人對演算法的理解太片面,很多人覺得只有名字里包含「XX演算法」之類的東西才是演算法。而我認為演算法的本質是解決問題,只要是能解決問題的代碼就是演算法。
一個人只有有了很好的計算機知識和數學知識,才能在演算法的學習上不斷進步。不管演算法都么簡單,都要自己親手實踐,只有不斷認識錯誤、不斷發現錯誤,才能不斷提高自己的編程能力,不斷提高自己的業務水平。
其實任何演算法都有自己的應用環境和應用場景,沒有演算法可以適用於所有的場景。這一點希望大家明白。同時,我們也要清楚複雜的演算法都是由普通的演算法構成的,沒有普通的演算法就沒有複雜的演算法可言,所以複雜變簡單,由大化小,這就是演算法分治遞歸的基本思想。
我們可以下面一個數組查找的函數說起。一句一句講起,首先我們開始從最簡單的函數構造開始:
1. int find(int array, int length, int value)
2. {
3. int index = 0;
4. return index;
5. }
這裡看到,查找函數只是一個普通的函數,那麼首先需要判斷的就是參數的合法性:
1. static void test1
2. {
3. int array[10] = {0};
4. assert(FALSE == find(NULL, 10, 10));
5. assert(FALSE == find(array, 0, 10));
6. }
這裡可以看到,我們沒有判斷參數的合法性,那麼原來的查找函數應該怎麼修改呢?
1. int find(int array, int length, int value)
2. {
3. if(NULL == array || 0 == length)
4. return FALSE;
5.
6. int index = 0;
7. return index;
8. }
看到上面的代碼,說明我們的已經對入口參數進行判斷了。那麼下面就要開始寫代碼了。
1. int find(int array, int length, int value)
2. {
3. if(NULL == array || 0 == length)
4. return FALSE;
5.
6. int index = 0;
7. for(; index < length; index++){
8. if(value == array[index])
9. return index;
10. }
11.
12. return FALSE;
13. }
上面的代碼已經接近完整了,那麼測試用例又該怎麼編寫呢?
1. static void test2
2. {
3. int array[10] = {1, 2};
4. assert(0 == find(array, 10, 1));
5. assert(FALSE == find(array, 10, 10));
6. }
運行完所有的測試用例后,我們看看對原來的代碼有沒有什麼可以優化的地方。其實,我們可以把數組轉變成指針。
1. int find(int array, int length, int value)
2. {
3. if(NULL == array || 0 == length)
4. return FALSE;
5.
6. int* start = array;
7. int* end = array + length;
8. while(start < end){
9. if(value == *start)
10. return ((int)start - (int)array)/(sizeof(int));
11. start ++;
12. }
13.
14. return FALSE;
15. }
如果上面的代碼參數必須是通用的數據類型呢?
1. template<typename type>
2. int find(type array, int length, type value)
3. {
4. if(NULL == array || 0 == length)
5. return FALSE;
6.
7. type* start = array;
8. type* end = array + length;
9. while(start < end){
10. if(value == *start)
11. return ((int)start - (int)array)/(sizeof(type));
12. start ++;
13. }
14.
15. return FALSE;
16. }
此時,測試用例是不是也需要重新修改呢?
1. static void test1
2. {
3. int array[10] = {0};
4. assert(FALSE == find<int>(NULL, 10, 10));
5. assert(FALSE == find<int>(array, 0, 10));
6. }
7.
8. static void test2
9. {
10. int array[10] = {1, 2};
11. assert(0 == find<int>(array, 10, 1));
12. assert(FALSE == find<int>(array, 10, 10));
13. }
最後,我們總結一下:(1)我們的演算法需要測試用例的驗證
(2)任何的優化都要建立在測試的基礎之上
(3)測試和代碼的編寫要同步進行
(4)演算法的成功運行時一步一步進行得,每一步的成功必須確立在原有的成功之上
更多精彩可進群交流~PS本文參考自網路