所謂的算法,有時候幾十行代碼就能搞定!
很多人認(rèn)為,算法是數(shù)學(xué)的內(nèi)容,學(xué)起來特別麻煩。我們不能認(rèn)為這種觀點(diǎn)是錯誤的。但是我們也知道,軟件是一種復(fù)合的技術(shù),如果一個人只知道算法,但是不能用編程語言很好地實(shí)現(xiàn),那么再優(yōu)秀的算法也不能發(fā)揮作用。
有一次,一個人問我:“你寫的都是小兒科的東西,幾十行代碼就能搞定,能不能整一點(diǎn)高深的算法?”
我反問他什么是他所理解的高深的算法,他答復(fù)說:“像遺傳算法、蟻群算法之類的。”于是我給了他一個遺傳算法求解0-1背包問題的例子,并告訴他,這也就是幾十行代碼的算法,怎么理解成是高深的算法?他剛開始不承認(rèn)這是遺傳算法,直到我給了他Denis Cormier公開在北卡羅來納州立大學(xué)服務(wù)器上的遺傳算法的源代碼后,他才相信他一直認(rèn)為深不可測的遺傳算法的原理原來是這么簡單。
還有一個人直言“用三個水桶等分8升水”之類的問題根本就稱不上算法,他認(rèn)為像“阿法狗”那樣的人工智能才算是算法。我告訴他計(jì)算機(jī)下棋的基本理論就是博弈樹,或者再加一個專家系統(tǒng)。但是他認(rèn)為博弈樹也是很高深的算法,于是我給了他一個井字棋游戲,并告訴他,這就是博弈樹搜索算法,非常智能,你絕對戰(zhàn)勝不了它(因?yàn)榫制逵螒蚝芎唵危@個算法會把所有的狀態(tài)都搜索完)。我相信他一定很震驚,因?yàn)檫@個算法也不超過100行代碼。
對于上面提到的例子,我覺得主要原因在于大家對算法的理解有差異,很多人對算法的理解太片面,很多人覺得只有名字里包含“XX算法”之類的東西才是算法。而我認(rèn)為算法的本質(zhì)是解決問題,只要是能解決問題的代碼就是算法。
一個人只有有了很好的計(jì)算機(jī)知識和數(shù)學(xué)知識,才能在算法的學(xué)習(xí)上不斷進(jìn)步。不管算法都么簡單,都要自己親手實(shí)踐,只有不斷認(rèn)識錯誤、不斷發(fā)現(xiàn)錯誤,才能不斷提高自己的編程能力,不斷提高自己的業(yè)務(wù)水平。
其實(shí)任何算法都有自己的應(yīng)用環(huán)境和應(yīng)用場景,沒有算法可以適用于所有的場景。這一點(diǎn)希望大家明白。同時,我們也要清楚復(fù)雜的算法都是由普通的算法構(gòu)成的,沒有普通的算法就沒有復(fù)雜的算法可言,所以復(fù)雜變簡單,由大化小,這就是算法分治遞歸的基本思想。
我們可以下面一個數(shù)組查找的函數(shù)說起。一句一句講起,首先我們開始從最簡單的函數(shù)構(gòu)造開始:
1. int find(int array[], int length, int value)
2. {
3. int index = 0;
4. return index;
5. }
這里看到,查找函數(shù)只是一個普通的函數(shù),那么首先需要判斷的就是參數(shù)的合法性:static void test1()
{
int array[10] = {0};
assert(FALSE == find(NULL, 10, 10));
assert(FALSE == find(array, 0, 10));
}
這里可以看到,我們沒有判斷參數(shù)的合法性,那么原來的查找函數(shù)應(yīng)該怎么修改呢?int find(int array[], int length, int value)
{
if(NULL == array || 0 == length)
return FALSE;
int index = 0;
return index;
}
看到上面的代碼,說明我們的已經(jīng)對入口參數(shù)進(jìn)行判斷了。那么下面就要開始寫代碼了。int find(int array[], int length, int value)
{
if(NULL == array || 0 == length)
return FALSE;
int index = 0;
for(; index < length; index ){
if(value == array[index])
return index;
}
return FALSE;
}
上面的代碼已經(jīng)接近完整了,那么測試用例又該怎么編寫呢?static void test2()
{
int array[10] = {1, 2};
assert(0 == find(array, 10, 1));
assert(FALSE == find(array, 10, 10));
}
運(yùn)行完所有的測試用例后,我們看看對原來的代碼有沒有什么可以優(yōu)化的地方。其實(shí),我們可以把數(shù)組轉(zhuǎn)變成指針。int find(int array[], int length, int value)
{
if(NULL == array || 0 == length)
return FALSE;
int* start = array;
int* end = array length;
while(start < end){
if(value == *start)
return ((int)start - (int)array)/(sizeof(int));
start ;
?????}??
return FALSE;
}
如果上面的代碼參數(shù)必須是通用的數(shù)據(jù)類型呢?template<typename type>
int find(type array[], int length, type value)
{
if(NULL == array || 0 == length)
return FALSE;
type* start = array;
type* end = array length;
while(start < end){
if(value == *start)
return ((int)start - (int)array)/(sizeof(type));
start ;
}
return FALSE;
}
此時,測試用例是不是也需要重新修改呢?static void test1()
{
int array[10] = {0};
assert(FALSE == find<int>(NULL, 10, 10));
assert(FALSE == find<int>(array, 0, 10));
}
static void test2()
{
int array[10] = {1, 2};
assert(0 == find<int>(array, 10, 1));
assert(FALSE == find<int>(array, 10, 10));
}
最后,我們總結(jié)一下:(1)我們的算法需要測試用例的驗(yàn)證;
(2)任何的優(yōu)化都要建立在測試的基礎(chǔ)之上;
(3)測試和代碼的編寫要同步進(jìn)行;
(4)算法的成功運(yùn)行時一步一步進(jìn)行得,每一步的成功必須確立在原有的成功之上。
END
來源:網(wǎng)絡(luò)版權(quán)歸原作者所有,如有侵權(quán),請聯(lián)系刪除。
▍