小時候家裡定了《讀者》的月刊，裡面記錄一個故事：說有有個偏僻的鄉村一日突然來了一個美女，她攜著萬貫家財子女在當地安家落戶，成了當地的鄉紳。她讓她的子女世世代代的保守這個秘密，直到這個秘密不會再對家族帶來災難。她就是陳圓圓。當年吳三桂領清兵入關，衝冠一怒為紅顏，改寫了中國的歷史，自己卻能全身而退的那個 ...
小時候家裡定了《讀者》的月刊，裡面記錄一個故事：說有有個偏僻的鄉村一日突然來了一個美女，她攜著萬貫家財子女在當地安家落戶，成了當地的鄉紳。她讓她的子女世世代代的保守這個秘密，直到這個秘密不會再對家族帶來災難。她就是陳圓圓。當年吳三桂領清兵入關，衝冠一怒為紅顏，改寫了中國的歷史，自己卻能全身而退的那個人。
周五例行公事的查看一下離線數據推送項目的數據和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(n2)
shell排序：縮小增量的插入排序，不穩定，有賴於增量因數序列的選取，最壞時間複雜度是O(n2)
簡單選擇排序：在要排序的數中選擇最小或最大與第一個未排序位置交換，最壞時間複雜度是O(n2)
二元選擇排序：每趟簡單選擇排序確定兩個元素，可減少一半的迴圈。
堆排序：樹形選擇排序，大根堆，小根堆。最壞時間複雜度是O(N*logN)
冒泡排序：每次相鄰的兩個數比較，交換，最壞時間複雜度是O(n2)
快速排序：選擇基準元素，每次將待排序元素分割，最壞時間複雜度是O(n2)
歸併排序：將兩個有序表合成一個新的有序表，最壞時間複雜度是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，搜索引擎也還是要做的。只是一個怎樣分配時間的問題。
我其實是喜歡去碰壁的，大概是自己還不想那麼快長大吧。如果天天表現的很成熟優雅的樣子，就需要隱藏一些自己不擅長的，或者有可能出錯的事兒。結果每天日子也會很開心，但是可能一輩子也就這樣了。歷史上有很多著名的人物，原本都是紈絝子弟，後家道中落才逆襲成為偉人的。書里，人生的轉折有遇到貴人，和遇到挫折兩種。年輕時心態開放，遇到貴人打開思路就可以頓悟了。而隨著經歷的增多，人會更加有選擇的接收周圍的信息，這時候大概需要遇到很大的挫折才能重新思考人生。如果能看到更好的未來，我願獨孤一擲，破釜沉舟。大起大落總好過一年如一日，要活就活的精彩~~
