特別注意：本文的算法問題對很多專業(yè)計算機的人來說，很簡單，但是注意看文章的人物背景。
五一后的第一周，由于搬家腰扭傷了，沒注意導致壓迫神經(jīng)，躺在床上休息了好幾天。所以沒事就掛 qq，一個網(wǎng)友突然問了我一個算法問題。所以有了這篇文章。感觸很深，所以特發(fā)此文，以紀念和寫給新朋友，以及那些熱愛編程的非專業(yè)人事。本人可能技術(shù)含量很低，但都很真實。雖然我只花了很少的時間，但解決了這個網(wǎng)友困惑了1年的問題，這個網(wǎng)友倒是特別感激，而我倒是感覺特別心塞。那大家喝杯茶，看看這個過程吧。
1.人物背景
這個網(wǎng)友我也是后來聊天才了解到他的情況。他是1個1977年出生的湖北網(wǎng)民，為了分析相關數(shù)據(jù)，自學了vb.net，這個年齡的人還學了這個，真的不容易，而且能夠用vb.net開發(fā)比較復雜的數(shù)據(jù)分析界面。其實后來了解到這些，自愧不如啊。所以對算法問題，這個朋友遇到困難，也可以理解。
其實這個朋友很早就是我的qq好友，也知道都是做數(shù)據(jù)分析，所有我有新的算法方面的文章會發(fā)給他看，偶爾聊一下，但沒有問過我問題。上個月發(fā)表了一篇文章：機器學習之pagerank算法應用與c#實現(xiàn)(1)算法介紹，發(fā)表之后，他看到后，才問我這個問題。
我：其實我也是個半吊子，對算法也不精通，只是業(yè)余研究感興趣而已。。說實話你要我寫個二分搜索，我一時半會還搞不定，但我看看論文和資料，可以寫個馬爾可夫鏈或者貝葉斯之類的。。。這個東西怎么說呢，在很多問題中，空間效率和時間效率，特別是在硬件條件如此富裕的情況下，可以考慮得更少一點。。當然這里絕對不是說算法是沒有用的，只是對很多非常普通的人來說，研究的規(guī)模太小，而且由于經(jīng)驗和特殊原因，沒有算法和數(shù)據(jù)結(jié)構(gòu)基礎，只能不考慮了，以解決實際問題為主吧。
2.原始問題
該網(wǎng)友的原始問題是這樣的，我從qq聊天記錄里直接copy過來：
有兩組隨機生成的（0～99999）int32數(shù)據(jù)a和b，將a按順序判斷在b中是否存在并記錄在boolean型的c中，我分別嘗試了array與list（of t),在vs2010下以我的破電腦的速度array大概需要4秒，而list（of t）則要24秒，以下是我用array和list(of t）的代碼，請高手指點， 順便問下有無秒殺的方法。（注：他的vb代碼我就不貼了，思路知道就可以了）
幫我看看用什么方法解決，謝謝
有人說用哈希，可惜我不會，也沒百度到
他的開發(fā)環(huán)境是vs2010 vb.net
我收到他的消息的時候是正在用手機qq上的，他還貼了段vb的代碼，我是比較反感直接貼代碼的人。不過當時躺在床上，也沒啥事，好奇嘛，就仔細看了一下這個問題，代碼真的沒看。
3.解決問題的過程
由于是手機上的，所以也沒開電腦敲代碼。就想了一下。
網(wǎng)友的原始代碼中的比較都是使用array.indexof，可以想象7萬的數(shù)組，速度慢也正常 。
1.首先我是把哈希給否定了的。其實后來想起來，是我錯了，我以為他說的哈希是把每個元素求哈希值后對比，這不是多此一舉么。。本來計算哈希就要時間，還是要比較。。。那何必呢。。。后來我才想到，他說的可能是“哈希表”，這是后話，不提了，哈希表這個方法怎么樣不知道，應該也還可以吧；但還是先看看我的方法。
2.我當時先給了他一個初步的方案，解決問題有時候不是一步到位的，先試試看咯。我的想法是使用indexof查找會浪費很多時間。所以，你先把b排序，或者b在實際構(gòu)造過程中就可以進行排序存儲，然后a依次對比的時候，采用二分法搜索，甚至有條件，a也可以先排序，然后搜索的時候記錄起點，二分法搜索，這樣可以節(jié)省不少時間。a和b排序的問題，其實根據(jù)他的情況，是可以在實際過程中就排序好的，而不是生成后排序，這樣就更費時間了。
這個網(wǎng)友也很迅速，過了大概1個小時，測試出來說：“我用的隨機數(shù)測試了下，速度提升相當明顯，比array.indexof要快多了”
3.上面手機溝通不方便，也就隨便說了一下，沒想到他很快做出來了。雖然快了很多，但具體時間我也沒問。然后我洗澡的時候，感覺這個問題不是那么回事，我以前貌似也做過類似的，應該還有更快的方法。然后洗澡過程中，思考了若干秒。。。一個思路也有了，雖然這個想法我感覺很土，但我想實際效果應該很好，所以洗完澡，馬上開電腦，跟網(wǎng)友說了一下思路，考慮到他有可能無法理解算法的偽代碼或者比較嚴格的表述(實際上我也不知道該怎么嚴格表述)，所以就直接打了一個比方，在這里為了方便大家理解，我先大概寫了個思路，應該會看得懂吧。至于問題中的記錄在c中，我具體沒問他怎么記錄，其實這和問題關系不大，核心在前面如何確定是否包括：
我給那位網(wǎng)友是這么打比方的(原始有點亂，我寫博客的時候稍微整理了下)，不知道大家有沒有歧義，感覺還是上面的偽代碼容易理解，但是開心的是，這個網(wǎng)友還是理解了 ：
a數(shù)組:不管，隨意，也不用排序, b數(shù)組：[5，2，4，1],假設最大為5，注意沒有3 初始化一個長度為5（最大數(shù)）的布爾數(shù)組:a[1],[2],[3],[4],[5] 循環(huán)b,將b中值作為a的下標，對應位置標記為true，例如 a[5]= true; a[2]= true; a[4]= true; a[1]= true; 注意a[3]沒有，為false 最后循環(huán)a，直接對比下標，如果a={2，3},那么： a[2]=true,說明存在，則c[2]=true，到c中標記true a[3]=false，則沒有。c中標記為false 如果你最大為99999,那么這個數(shù)組要這么長你可以直接設置為99999，浪費一點空間； 如果你業(yè)務中可以直接求出最大值，那是最好的了。自己試一試。
這個思路理解了非常簡單。這個網(wǎng)友也很快理解了，過了一會就把他的結(jié)果告訴我了。
下降到10毫秒左右，他把數(shù)據(jù)擴大到10萬，速度也挺快的。
4.后記與c#實現(xiàn)
解決他的問題后，第二天我們又聊了一會，他表示很感謝，說這個方法速度非?？?。說這1年來，他問過很多人，也找過很多計算機方面的人，但效果都不好。。。
據(jù)說還問過一個拿過什么微軟認證的人。。。說他的電腦不行，要去換一下。。。這個有點過份操蛋了。。才幾萬的數(shù)組，能耗多少內(nèi)存，都是簡單的比較計算，需要很好的cpu么。。。
后來我也給他分析過說，其他人可能沒有完全理解你的問題，都一根筋考慮效率和速度的問題了，所以考慮的東西多了，給你的建議也不一定合適。對這些小問題，犧牲一點空間，何況又不多，而且內(nèi)存也便宜，現(xiàn)在動不動2g，4g。。換時間也是夠劃算的。我這里說的空間，是直接初始化數(shù)組c的長度包括所有的數(shù)字個數(shù)，因為我也不了解他實際的數(shù)據(jù)怎么來的，當然如果能計算最大值，肯定最好了。這樣稍微計算一下時間復雜度，循環(huán)2遍就能解決問題。至于我第一次提到的排序和二分法的問題，也只是剛開始想到的，沒有更深入的思考，因為也是考慮到他的數(shù)據(jù)是可以在生成的時候就進行排序的，這樣也可以省時間，而不是所有的都indexof，不慢才怪。
4.1 c#代碼實現(xiàn)原始方法
閑的沒事，我用c#實現(xiàn)了一下網(wǎng)友原始的方法，代碼如下：
static void validatearrayelement2() { stopwatch sp = new stopwatch(); sp.start(); //開始計時 random rand = new random(); int32 maxvalue = 120000; //元素最大值，是一個假定值 int32 length = 70000; // a,b的長度 int32[] a = new int32[length]; int32[] b = new int32[length]; boolean[] c = new boolean[length]; //隨機初始化a，b數(shù)組 for (int i = 0; i < length; i ) { a[i] = rand.next(maxvalue); b[i] = rand.next(maxvalue); } //循環(huán)a，驗證是否存在，將c對應位置標記為true for (int i = 0; i < a.length; i ) if (b.contains(a[i])) c[i] = true; sp.stop(); console.writeline(sp.elapsedmilliseconds); }
測試了下，我機器是x200 t9400，3g內(nèi)存。加上數(shù)據(jù)初始化總共時間是4.3秒，所以實際的時間是4秒左右，和網(wǎng)友的結(jié)論是差不多的?？纯次蚁旅娴姆椒ǎ?br>4.2 c#代碼實現(xiàn)上述算法
使用第3節(jié)提出的方法，我測試一下時間：
static void validatearrayelement() { stopwatch sp = new stopwatch(); sp.start(); random rand = new random(); int32 maxvalue = 120000; //元素最大值，是一個假定值 int32 length = 70000; // a,b的長度 int32[] a = ne