一個項目中常用的linux指令引發的經典演算法題

　　小时候家里定了《读者》的月刊，里面记录一个故事：说有有个偏僻的乡村一日突然来了一个美女，她携着万贯家财子女在当地安家落户，成了当地的乡绅。她让她的子女世世代代的保守这个秘密，直到这个秘密不会再对家族带来灾难。她就是陈圆圆。当年吴三桂领清兵入关，冲冠一怒为红颜，改写了中国的历史，自己却能全身而退的那个人。

　　周五例行公事的查看一下离线数据推送项目的数据和log。将log用awk分段之后，我想知道实时数据前10个被重复发送的数据ID都被重复发送了几次，从而找到进一步优化的入手点，天知道我对这个项目已经进行了多少次优化了。于是linux命令就是

 cat transmission.log |grep 'IncrementAlbumService.java:146'|awk '{print $6}'|awk -F ',' '{print $1}'| sort |uniq -c| sort -nr |head

　　得到的結果令我很自責

（資料安全，對於我們專案的ID規則部分不顯示）

雖然這和他們的操作有關，我本來就是該偵測到資料變更就發送出去，但是對於這麼大的重發率。不管從更新服務的介面上，或是離線服務上，能夠優化的點還是有的。姑娘我的思路一向與那些出場要用吹風機，人工噴壺製造畫面感的男神大佬思路不同。除了這個結果，我還在想另一個經典演算法問題：說是有一個文字文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前十個字。

　　這個演算法問題使用上面的linux指令就是sort|uniq -c |sort -nr | head。時間複雜度為下面幾項中最大的一個：

　　1>先是做一次排序，

　　　　直接插入排序：不斷將元素插入到有序表中去，最壞時間複雜度是O(n²)

　　　　shell排序：縮小增量的插入排序，不穩定，有賴於增量因子序列的選取，最壞時間複雜度是O(n ²)

　　　　簡單選擇排序：在要排序的數字中選擇最小或最大與第一個未排序位置交換，最壞時間複雜度是O(n² )

　　　　二元選擇排序：每趟簡單選擇排序確定兩個元素，可減少一半的循環。

　　　　堆排序：樹狀選擇排序，大根堆，小根堆。最壞時間複雜度是O(N*logN)

　　　　冒泡排序：每次相鄰的兩個數比較，交換，最壞時間複雜度是O(n² )

　　　　快速排序：選擇基準元素，每次將待排序元素分割，最壞時間複雜度是O(n²)

#　　　　歸併排序：將兩個個有序表合成一個新的有序表，最壞時間複雜度是O(N*logN)

　　　　桶排序：以空間換時間的演算法，複雜度接近O(n)  

　　　　基數排序：依照個十百千的位數進行分配收集，時間複雜度是O(dn)

　　 2>uniq 時間複雜度為O(n)

　　 3> ;sort時間服務度同1>

　　 4>已經排好序了時間複雜度就是O(1)

　　採用的演算法也和檔案的大小有關係，如果檔案太大，資料太多，就需要將檔案拆分，分別排序後做多路歸併。所以這裡說了文字數量。

　　不用linux指令，經​​典的解決方法是先用字典樹統計詞頻，再用大根堆。先介紹一下字典樹，也叫tire樹。因為搜尋引擎常用這個來做文字詞頻統計，分詞演算法也用這個作為基本資料結構，所以知道一些。它的優點是：最大限度的減少無謂的字串比較，查詢效率高於雜湊表。核心思想是以空間換時間，利用公共前綴來降低查詢時間的開銷。所以一說統計啥啥，首先想到的就是字典樹。如果在統計詞頻時維護一個前十位的最大詞頻數組之類的，在循環處理中比較，時間複雜度要翻10倍。所以還是先統計，再取top10時間效率上比較適合。

　　其實我不咋懂演算法，只是會用。我之前有同事看了我寫的一篇文章微信問我：「feed流是很有技術含量的工作嗎？」他這個問題讓我想起《仙劍》裡李逍遙在餐館裡非要裝高富帥，說要點最名貴的菜：“青菜炒牛肉”，眾人哄笑，靈兒問李逍遙：“逍遙哥哥，青菜炒牛肉是很名貴的菜嗎？”。雖然同事在真心問我的意見，因為他在京東，正在考慮要不要去陌陌，但我覺得自己像那個沒見過世面的李逍遙。 feed流這個業務邏輯怎麼都能做，有沒有技術含量取決於怎麼做。我寫過一篇專利，介紹feed流的一種拼裝方法，流程沒走完，這之前我就先不公開計算方法了。但是努力去想的話，優化點還是很多的。前年我還比較喜歡玩朋友圈的時候，常常會發現自己刪除的朋友圈又出現了，或者自己的或是別人的朋友圈突然最近的數據全沒了，只有很老的數據，比如一年前兩年前的數據，一天後自動恢復。都是策略的問題。微信朋友圈的問題還挺多的。鑑於我們有個人見人愛花見花開的產品mm是微信架構師家屬，我就不過多吐槽了。

　　雖說今天是星期日，可以腦洞大開一下，也得有個主題。前面的例子有個經典的top K問題。因為搜尋引擎會經常需要統計最熱門的查詢串，top K問題是基礎。 TopK問題用小根堆。維護一個K大小的小根堆，遍歷要比較的元素，分別與跟元素做對比，如果小於根元素，表示肯定進不了前K，淘汰掉。如果大於根元素，就淘汰根元素。再調整樹為最小堆，繼續比較。

　　最小堆的是一棵完全二元樹，每個非葉子節點的值都不大於其子節點的值。如果破壞了這個規律，就要從第一個非葉子節點開始向根節點這種自下往上的順序進行調整。

　　下週決定面一下hulu，還沒面，應該是面不過。兩年前原同事給推薦過亞馬遜，結果沒讓我去面試，安慰自己一下就是估計那時候他們其實是不招人的。從來沒去過這種外企面試，不知道是啥套路。如果現在開始準備的話，估計過了十一差不多能過。我想我自己去面試一定很不佔優勢。不是完全會不好，會很不穩定。看過我文章朋友大概會覺得我文章寫的很亂，很雜。生活中我也確實是這樣。知識面很廣，很異想天開，無所顧忌，這一方面為我的創造力奠定基礎，另一方面不利於我臨場發揮。大腦像是一台電腦。我的平行程式很多，記憶體不夠大，資料又多。記憶體分頁導致不斷和磁碟swap。面試這種有時效的動作很容易導致逾時返回。我有那麼多技術發明專利，現在讓我想，我一個都想不起來自己發明了啥。剛剛坐公車，因為人很少，司機師傅問我哪裡下車，意思是沒有人下車的地方就不停了。我想了很久才想起來。我的大腦比較運行在非同步非阻塞模式，其實面試這種事情同步阻塞反而會好一些。然而任何事情都有解決的方法，找不到方法就是能力不夠了，沒什麼不服的。然而面試是要考察綜合能力的，例如團隊合作，談吐能力等等。相信我們部門的人都不會對「曉靜很聰明「這句話有異議。也相信部門或工作上有合作的同事都不會覺得自己是個很難溝通或很難相處的人。但是在面試中我很可能會忘了該怎麼說話。但是如果因為這個問題我沒通過一個面試的話，我沒有怨言。因為面試官就是未來的同事和領導，如果不夠合拍的話，將來去了自己的能力也不一定能發揮出來。如果面試不好還覺得自己能力是夠的，那很有可能是自己格局不夠高，沒見過真正優秀的人是什麼樣子。然而我就是那種鐵定要碰壁的事還要做的人。如果有一件事我決定放棄了，原因肯定是不值得做。

　　喜歡工作，我的目標是60歲時還能有一份有創意的工作。所以怕國內網路公司會讓我40歲就退休。還有一件最重要的事：我想做自己的搜尋引擎中間件，國內的網路公司以用為主，怕是我很難有精力做這件事情。當然，去不了hulu，搜尋引擎還是要做的。只是一個怎樣分配時間的問題。

　　我其實是喜歡去碰壁的，大概是自己還不想那麼快長大吧。如果天天表現的很成熟優雅的樣子，就需要隱藏一些自己不擅長的，或是有可能出錯的事兒。結果每天日子也會很開心，但可能一輩子也就這樣了。歷史上有許多著名的人物，原本都是紈縐子弟，後家道中落才逆襲成為偉人的。書裡，人生的轉折有遇到貴人，和遇到挫折兩種。年輕時心態開放，遇到貴人打開思路就可以頓悟了。而隨著經歷的增多，人會更有選擇的接收周遭的訊息，這時候大概需要遇到很大的挫折才能重新思考人生。如果能看到更好的未來，我願獨孤一擲，破釜沉舟。大起大落總好過一年如一日，要活就活的精彩~~

以上是一個項目中常用的linux指令引發的經典演算法題的詳細內容。更多資訊請關注PHP中文網其他相關文章！