這不是一本具體算法的講解或者代碼編寫的教程，但是從書中的字里行間，我們可以學(xué)到的是更多的軟知識(shí)：對(duì)編程新的認(rèn)識(shí)、更加發(fā)散的思維方式尼酿、更嚴(yán)格的代碼要求、堪比瑞士軍刀的小技巧…… 編程也許入門并不難植影，但是要想真正成為一名優(yōu)秀的軟件工程師裳擎，還是需要很多錘煉。內(nèi)外兼修思币，方成大器鹿响。
基礎(chǔ)篇
-
第一章 開篇
首先作者提出一個(gè)實(shí)際問題：
如何給磁盤的某個(gè)文件排序，更具體來說就是是對(duì)一個(gè)最多包含1千萬條記錄谷饿，每條記錄都是7位整數(shù)的文件惶我，而且只有1MB的內(nèi)存可以使用
從實(shí)際問題中提煉出更明確的數(shù)學(xué)定義：
輸入：一個(gè)最多包含n個(gè)整數(shù)的文件，每個(gè)數(shù)都小于n博投，其中n=10^7绸贡。可以保證輸入文件中不存在重復(fù)整數(shù)
輸出：按升序排列的輸入整數(shù)的列表
約束：1MB左右的內(nèi)存空間，充足的磁盤存儲(chǔ)空間听怕。運(yùn)行時(shí)間最多幾分鐘捧挺，控制在10秒內(nèi)不再需要進(jìn)一步優(yōu)化考慮一般的解法，直接讀入所有的整數(shù)尿瞭，然后進(jìn)行快排堆排之類的排序闽烙，時(shí)間復(fù)雜度很明顯是O(nlogn),但空間復(fù)雜度是O(n),即如果n=107 時(shí)，用4個(gè)字節(jié)的int型存儲(chǔ)每個(gè)整數(shù)声搁，那么需要的空間是(4*107)/210210=38MB,很顯然超出了內(nèi)存限制黑竞，而考慮實(shí)際n的大小限制和每個(gè)整數(shù)只會(huì)出現(xiàn)一次的限制，而所謂的排序也只是把從文件中的整數(shù)按在1－n內(nèi)出現(xiàn)的順序輸出而已疏旨，因此只要對(duì)n之內(nèi)出現(xiàn)的整數(shù)做一下標(biāo)記最后輸出標(biāo)記過的整數(shù)就可以了很魂，考慮到這，位向量（也叫位圖）就成了比較合適的數(shù)據(jù)結(jié)構(gòu)的選擇檐涝，每個(gè)位的0遏匆、1值表示一個(gè)數(shù)字是否出現(xiàn)過，實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(n),考慮n取最大值107時(shí)骤铃，需要的空間為107/8/210/210=1.2MB,代碼實(shí)現(xiàn)如下：
#include <iostream> #include <fstream> #include <bitset> #include <string.h> #define N 1000000 using namespace std; void intSort(){ bitset<N> numBits; ifstream = testFile("/Users/smy/temp/data.txt"); string s; int count = 0; while(testFile >> s){ numBits[atoi(s.c_str())-1] = 1; ++count; } testFile.close(); for(int i=0;i<N;++i){ if(numBits[i] == 1){ cout<<i+1<<endl; } } } int main(int argc, const char * argv[]) { intSort(); return 0; }那么進(jìn)一步考慮：
如果嚴(yán)格限制程序占用內(nèi)存不能超過1M，應(yīng)該怎么處理坷剧？
如果每個(gè)數(shù)最多出現(xiàn)10次惰爬，又應(yīng)該如何改動(dòng)算法？所用存儲(chǔ)空間是怎樣變化的呢惫企？在解決這個(gè)實(shí)際問題的方案中撕瞧，我們看到了不同于比較排序的一種排序方式：位向量排序，而且從這個(gè)問題中也引出了作者的一些思考和對(duì)讀者的啟示：
- 做一個(gè)"懶"工程師：處理問題時(shí)狞尔，即便是一看上去就知道解法的問題丛版，不要馬上動(dòng)手編寫代碼，花些時(shí)間去明確問題偏序，抽象問題模型页畦，結(jié)合問題的特點(diǎn)去分析，等靈光一現(xiàn)時(shí)再動(dòng)手研儒。作者在解決上題時(shí)首先是對(duì)問題進(jìn)行了數(shù)學(xué)定義豫缨，考慮到問題中數(shù)據(jù)的特點(diǎn)以向量的方式解決了問題并且時(shí)間復(fù)雜度和空間復(fù)雜度都較低。這樣的方式不僅能收到更好的編碼效果端朵，考慮的情況會(huì)更加完善好芭，調(diào)試起來的時(shí)間也會(huì)縮短，而且經(jīng)過深度思考再動(dòng)手的印象要深刻的多冲呢，等之后再遇到類似的問題時(shí)舍败，馬上就會(huì)涌現(xiàn)解決問題的思路，這樣才能積累真正的經(jīng)驗(yàn)。
- 時(shí)間和空間可以是雙贏的：確實(shí)很多時(shí)候也許我們會(huì)在時(shí)間和空間之間做折中的選擇邻薯，但是這種折中一定應(yīng)該是在我們仔細(xì)分析了某方面不能再有改善的情況下裙戏，而很多情況下因?yàn)樽约核惴芰Φ牟蛔愫退季S能力的局限，也許自己的算法可以在時(shí)間和空間雙重優(yōu)化弛说，這就要求一方面自己要深度思考當(dāng)前算法的優(yōu)化空間挽懦，另一方面可以向更優(yōu)秀的人請(qǐng)教是否有完全不同但是可以達(dá)到更好效果的方法或者對(duì)自己算法的建議，如果確實(shí)確定要做折中處理的話木人，要明確問題對(duì)時(shí)間和空間要求的嚴(yán)格性和最大容忍限度信柿，然后在合理犧牲某方面的前提下向預(yù)定目標(biāo)靠攏。
- 簡(jiǎn)單的設(shè)計(jì)：“設(shè)計(jì)者確定其設(shè)計(jì)已經(jīng)達(dá)到了完美的標(biāo)準(zhǔn)不是不能再增加任何東西醒第，而是不能再減少任何東西"渔嚷，在滿足要求的前提下盡量讓設(shè)計(jì)簡(jiǎn)潔，有利于今后的擴(kuò)展和排錯(cuò)稠曼，“大道至簡(jiǎn)“形病，設(shè)計(jì)需要的也許更多是簡(jiǎn)潔的美。
-
第二章 啊哈霞幅！算法
- 給定一個(gè)最多包含m=40億個(gè)隨機(jī)排列的n=32位整數(shù)的順序文件漠吻，找出一個(gè)不在文件中的32位整數(shù)。在內(nèi)存足夠的情況下如何解決該問題司恳？如果有幾個(gè)外部的“臨時(shí)文件“可用途乃，但是僅有幾百字節(jié)的內(nèi)存，又該如何處理扔傅？
- 將一個(gè)n元一維向量想做旋轉(zhuǎn)i個(gè)位置(如對(duì)n=3元向量“abc“耍共，當(dāng)i＝1時(shí)，結(jié)果為“bca“)
- 給定一個(gè)英文字典猎塞，找出其中的所有變位詞集合试读。（變位詞指的包含相同數(shù)量相同字母的單詞，因?yàn)樗麄兺ㄟ^調(diào)整字母的順序可以變?yōu)橐粋€(gè)單詞所以叫變位詞荠耽，如"stop"和"tops"和"pots"）
對(duì)于問題1钩骇，首先明確一下肯定是存在整數(shù)不在文件中的，因?yàn)?2位整數(shù)最多可以表示的數(shù)字是2^32=4294967296>4000000000
（1）在內(nèi)存充足的情況下铝量，可以用上述位向量的做法伊履，初始化232個(gè)位為0，每讀到一個(gè)數(shù)字就將對(duì)應(yīng)下標(biāo)的位數(shù)組的值置為1款违，最后統(tǒng)計(jì)值仍為0的元素就是沒有出現(xiàn)過的整數(shù)唐瀑，這樣的做法時(shí)間復(fù)雜度是O(2n),空間占用大約為O(2n/8)B,當(dāng)n＝32時(shí)占用空間大小約為2n/8/210/210=512MB
（2）內(nèi)存不夠有臨時(shí)文件可以使用時(shí)，又該如何做呢插爹？既然有臨時(shí)文件可以用哄辣，那可以將原來大文件中的數(shù)字分配到臨時(shí)文件中请梢，當(dāng)臨時(shí)文件的規(guī)模夠小時(shí)再采用上面說的位向量的算法。分配可以采用散列的方法力穗，比如通過簡(jiǎn)單的模上臨時(shí)文件的個(gè)數(shù)將結(jié)果相同的聚合到一個(gè)文件毅弧，判斷缺失元素在哪個(gè)文件的方法是在向臨時(shí)文件插入元素的時(shí)候統(tǒng)計(jì)每個(gè)臨時(shí)文件的數(shù)字個(gè)數(shù)，因?yàn)槲覀兪强梢灾栏鶕?jù)我們選定的散列算法在沒有元素缺失情況下的數(shù)字個(gè)數(shù)k的当窗，那么這樣就只需要比較散列完成后臨時(shí)文件的個(gè)數(shù)與k比較够坐，如果比k小的話那么這個(gè)臨時(shí)文件中就存在缺失元素，接下來以這個(gè)臨時(shí)文件為主文件崖面，再次采用前面所說的散列方法（此時(shí)散列算法的參數(shù)可能需要調(diào)整）如此迭代下去直到限制的內(nèi)存空間足以承載包含缺失元素的文件規(guī)模時(shí)元咙，回到第一種情況處理。 可以看到這也體現(xiàn)了二分搜索的思想巫员，只不過是以文件包含的一系列整數(shù)為范圍庶香，用包含這些整數(shù)的文件表示這個(gè)范圍，通過比較文件中整數(shù)個(gè)數(shù)與期望個(gè)數(shù)判定缺失元素所在文件范圍简识，從而達(dá)到了縮小問題規(guī)模的效果將問題轉(zhuǎn)換成內(nèi)存充足的情況赶掖。對(duì)于問題二，看起來比較簡(jiǎn)單七扰，代碼實(shí)現(xiàn)起來也不難奢赂，不過作者提供的幾個(gè)巧妙的算法倒讓人耳目一新。
我一開始的想法是作者所說的“雜技算法“颈走，void rotate(string str,int k){ int len = str.length(); if(len > 1 && k % len != 0){ //控制k在［1膳灶，len－1］內(nèi)方便下標(biāo)操作 k = (k > len) ? k%len : k; k = (k < 0) ? k+len : k; char curr_val = str[k]; //將被調(diào)整的值 int to_pos = 0; //將被調(diào)整到的位置 char to_val = str[to_pos]; //現(xiàn)在將被調(diào)整到的位置對(duì)應(yīng)的值 int count = 0; while (count != len) { str[to_pos] = curr_val; curr_val = to_val; to_pos = (to_pos-k+len)%len; to_val = str[to_pos]; ++count; } } cout<<str<<endl; }時(shí)間復(fù)雜度為O(n),額外的空間復(fù)雜度為O(1),比較理想的一種算法计维，不過先不要滿足蜈块，再來看一種跌破眼睛卻又不得不為之叫好的算法：
void rotate2(string str,int k){ //假設(shè)k已經(jīng)在[1,len-1]范圍內(nèi)，處理同上 reverse(str.begin(), str.begin()+k); reverse(str.begin()+k, str.end()); reverse(str.begin(), str.end()); cout<<str<<endl; }具體來看這種算法的理論支持：可以把向量x看作兩段子向量的集合即x=ab,其中b[0]=x[k],我們的目的是使x=ba,但b和a的內(nèi)部不會(huì)變化，想象線性代數(shù)中我們會(huì)怎么做拆吆，yes:
ab -> a^b -> ab ->(ab)=ba，a表示a的逆向量
嘗試下用左右手模擬10元數(shù)組向上旋轉(zhuǎn)5個(gè)位置的例子脂矫，相信你也會(huì)感嘆它的神奇枣耀，雖然它要比上面那種算法稍慢一些，因?yàn)樗隽酥虚g轉(zhuǎn)換庭再，每個(gè)字符不是一次性地移到目標(biāo)位置捞奕，但是這種拆分向量用數(shù)學(xué)運(yùn)算簡(jiǎn)化算法的思想確實(shí)值得借鑒。再來看問題三拄轻，千萬不要想通過排列組合的方式去解決颅围，要知道一個(gè)有26個(gè)字母的單詞就可能有26! 種排列方式『薮辏考慮一下變位詞的定義院促，它們有共通點(diǎn)：組成字母集合相同筏养。也就是說我們只要為每個(gè)單詞選擇標(biāo)識(shí)和聚集相同標(biāo)識(shí)的單詞就好了。標(biāo)識(shí)可以是按所包含字母順序排列的單詞常拓，比如"pots","stop","tops"的標(biāo)識(shí)都是 "opst"渐溶。
#include <iostream> #include <fstream> #include <string.h> #include <algorithm> #include <map> #include <vector> using namespace std; map<string,vector<string> > getWords(){ map<string,vector<string> > words; ifstream testFile("/Users/smy/wuque/study/ios/pro/demo/data.txt"); string s; while(testFile >> s){ string preStr = s; sort(s.begin(),s.end()); if(words.count(s)==0){ vector<string> lines; lines.push_back(preStr); words.insert(pair<string, vector<string>>(s,lines)); }else{ words.find(s)->second.push_back(preStr); } } testFile.close(); return words; } void lookup(map<string,vector<string> > words,string word){ sort(word.begin(), word.end()); if(words.count(word) == 0){ cout<<"no results"<<endl; return ; } vector<string> lines = words.find(word)->second; for(vector<string>::iterator iter = lines.begin();iter != lines.end();++iter){ cout<<*iter<<endl; } } int main(int argc, const char * argv[]) { // intSort map<string,vector<string> > words = getWords(); string word; cout<<"please input a word to lookup:"; cin>>word; lookup(words, word); return 0; }這一章圍繞這三個(gè)問題，作者在給我們解決問題思路的同時(shí)也給我們留下更進(jìn)一步思考的空間弄抬，而其中體現(xiàn)出的一些解決問題的模式很有借鑒意義：
- 看起來很困難的問題也可以有一個(gè)簡(jiǎn)單的茎辐、意想不到的答案：有的事情看上去很復(fù)雜但經(jīng)過仔細(xì)分析后可能問題一下子就變得很簡(jiǎn)單了，而即便是真正困難的問題掂恕，也不見得解決方法也很復(fù)雜拖陆，比如漢諾塔問題，很多時(shí)候我們?nèi)狈Φ木褪菗荛_問題迷霧竹海、明確問題模型慕蔚、把握問題本質(zhì)的能力，而一旦這些都清楚了斋配，解決方法也就顯而易見了
- 其實(shí)很多解決問題的算法都是由一些基本操作組合而成的：這些基本操作中很多我們可能都已經(jīng)爛熟于胸孔飒，所以我們要做的一方面是擴(kuò)展自己的算法基礎(chǔ)，也就是多掌握一些基本的算法思想和高級(jí)數(shù)據(jù)結(jié)構(gòu)艰争，另一方面就是面對(duì)實(shí)際問題時(shí)能提取出問題的抽象模型坏瞄，找到適合的基本操作，再結(jié)合問題的特點(diǎn)甩卓，對(duì)算法進(jìn)行改進(jìn)甚至另辟蹊徑鸠匀，以一種巧妙的方式更簡(jiǎn)單地解決問題
-
第三章 數(shù)據(jù)決定程序結(jié)構(gòu)
這一章并沒有算法的具體內(nèi)容，作者只是舉了幾個(gè)程序員常犯的錯(cuò)誤逾柿，給出了避免錯(cuò)誤使用數(shù)據(jù)結(jié)構(gòu)導(dǎo)致的一系列問題的建議缀棍，比如使用數(shù)組重新編寫重復(fù)代碼、封裝復(fù)雜結(jié)構(gòu)机错、盡可能使用高級(jí)工具爬范、從數(shù)據(jù)得出程序的結(jié)構(gòu)等等。
- 恰當(dāng)?shù)臄?shù)據(jù)視圖實(shí)際上決定了程序的結(jié)構(gòu)弱匪，數(shù)據(jù)的表示形式是程序設(shè)計(jì)的根本：數(shù)據(jù)結(jié)構(gòu)＋算法＝程序青瀑，問題無非就是數(shù)據(jù)和算法，通過對(duì)問題的分析提取出問題模型萧诫，并結(jié)合合適的數(shù)據(jù)結(jié)構(gòu)來理清思路斥难，實(shí)際編寫代碼的時(shí)候采用語言提供的配套的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。數(shù)據(jù)組織好了帘饶，算法清晰了哑诊，程序也就自然而然地完成了，而且可以完成的很漂亮及刻，由此可見選對(duì)數(shù)據(jù)結(jié)構(gòu)對(duì)解決好問題的重要性
- 及時(shí)優(yōu)化代碼：不要覺得代碼雖然很亂但是足夠滿足需求就可以了镀裤，如果每次我們都是這么針對(duì)新需求添磚加瓦式的擴(kuò)展程序的話穷当，久而久之，代碼會(huì)丑的讓人難以直視淹禾，整個(gè)程序結(jié)構(gòu)也會(huì)臃腫不堪馁菜，后期維護(hù)多花費(fèi)的時(shí)間可能遠(yuǎn)遠(yuǎn)超過每次修改仔細(xì)審視并優(yōu)化代碼的時(shí)間，等程序真的大了的時(shí)候再說重構(gòu)可能就不是那么輕松了
- 發(fā)明家悖論"更一般性的問題也許更容易解決"：解決問題有的時(shí)候是由大化小铃岔，一點(diǎn)點(diǎn)的分析抓住問題的核心汪疮，而有的時(shí)候還需要由點(diǎn)到面的展開，不單去考慮n＝10的情況而是針對(duì)n為任意正整數(shù)的情況去做處理毁习，這樣也許會(huì)讓思路一下子展開智嚷，找到問題的共通點(diǎn)，而且在很多需求變更頻繁的業(yè)務(wù)上纺且，這樣的思考方式和編碼風(fēng)格會(huì)大大提高程序的通用性和兼容性
-
第四章 編寫正確的程序
這一章以二分搜索為例演示了算法驗(yàn)證的“三步曲“：初始化盏道、保持和終止
- 初始化：循環(huán)初次執(zhí)行的時(shí)候不變式為真
- 保持：如果在某次迭代開始的 時(shí)候以及循環(huán)體執(zhí)行的時(shí)候，不變式都為真载碌，那么猜嘱，循環(huán)體執(zhí)行完畢的時(shí)候不變式依然為真
-
終止：循環(huán)能夠終止，并且能夠得到期望的結(jié)果
程序編寫完成后測(cè)試的重要性并不亞于編碼本身嫁艇，由于思維邏輯的漏洞或者程序編寫時(shí)的手誤都有可能造成程序Bug朗伶，而測(cè)試正是發(fā)現(xiàn)Bug的過程，也只有發(fā)現(xiàn)了Bug步咪，找到Bug的原因才能徹底解決Bug论皆，保證程序的正確性和健壯性。
程序員也應(yīng)該充當(dāng)測(cè)試人員的一部分角色猾漫，證明所用算法的正確性（實(shí)際中并不用一字一句地去證明）点晴，用全面的測(cè)試用例驗(yàn)證程序結(jié)果，盡早在自己手中發(fā)現(xiàn)Bug悯周，雖然實(shí)際工作中程序員不需要也沒有時(shí)間像測(cè)試人員一樣逐個(gè)地去考察程序的各個(gè)指標(biāo)粒督，但一些顯而易見的邏輯漏洞和性能問題最好還是在提測(cè)之前主動(dòng)check一下才好。由于實(shí)際工作中队橙，提測(cè)坠陈、測(cè)試萨惑、提Bug單的流程會(huì)浪費(fèi)一定的時(shí)間捐康，而且突然的一個(gè)Bug單也會(huì)打亂現(xiàn)在工作的節(jié)奏，所以這樣可以在一定程度上縮短程序開發(fā)的總周期庸蔼，也可以增加別人對(duì)自己編程能力的肯定解总。試想如果你不時(shí)就會(huì)聽到測(cè)試人員對(duì)某位開發(fā)人員說“某某地方程序結(jié)果又有些不對(duì)啊“，想必這將會(huì)大大降低對(duì)這位開發(fā)者的信任程度姐仅。
-
第五章 編程小事
這一章主要是就實(shí)際編程中遇到的一些問題和調(diào)試手段給予讀者一些小技巧花枫，雖然小得或許不值一提或許我們都已經(jīng)了然于胸又或許我們并不清楚這些概念但卻在實(shí)實(shí)在在地使用刻盐。
- 使用“腳手架“（scaffolding）：在我看來，腳手架應(yīng)該是一個(gè)對(duì)方面我們測(cè)試的工具的形象比喻劳翰，為了方便頻繁地測(cè)試敦锌，我們可以先用偽代碼實(shí)現(xiàn)檢查沒有什么問題再用響應(yīng)的語言翻譯過來，可以編寫專門的測(cè)試腳本或者GUI界面佳簸，可以在main函數(shù)中控制讓測(cè)試者手動(dòng)輸入數(shù)據(jù)保證程序在測(cè)試過程中不用修改乙墙，可以使用斷言在程序運(yùn)行過程中檢測(cè)某段邏輯的結(jié)果（類似于自動(dòng)斷點(diǎn)，常用在單獨(dú)的測(cè)試文件中生均，比如unit）听想，可以使用自動(dòng)化工具只需要輸入數(shù)據(jù)自動(dòng)去跑測(cè)試用例，可以在程序中添加計(jì)時(shí)代碼評(píng)定程序性能……這些方法依據(jù)問題場(chǎng)景马胧、問題的復(fù)雜程度汉买，投入成本與測(cè)試成本的比重 而被選擇用來測(cè)試程序，我們的目的就用盡量少的時(shí)間發(fā)現(xiàn)盡量多的Bug佩脊。
- 調(diào)試手段：發(fā)現(xiàn)Bug蛙粘，首先要懷疑，根據(jù)Bug結(jié)果威彰、錯(cuò)誤日志等現(xiàn)有數(shù)據(jù)去懷疑可能會(huì)造成Bug的原因组题，然后再通過打日志、設(shè)斷點(diǎn)等手段去驗(yàn)證抱冷；而如果確實(shí)分析不出懷疑對(duì)象可以采用“控制變量“崔列，“二分搜索“等思想嘗試去改變程序的某一個(gè)變量或者某一段邏輯，比較結(jié)果的差異性旺遮。 如果問題在某種情況下發(fā)生而某種情況下不發(fā)生赵讯，首先比較兩種情況的不同之處，再結(jié)合錯(cuò)誤提示分析可能原因耿眉，上下夾擊可以更快地找到Bug原因边翼。找到Bug原因就已經(jīng)是解決Bug的一大半了，或者更武斷一點(diǎn)說 只要找到Bug的原因就肯定可以解決鸣剪。
以上為本書的基礎(chǔ)篇,通篇讀下來可以看到作者安排章節(jié)的順序和我們?nèi)粘．a(chǎn)品開發(fā)的流程是一致的：
分析問題->設(shè)計(jì)算法->結(jié)合語言選擇合適的數(shù)據(jù)結(jié)構(gòu)編程實(shí)現(xiàn)->測(cè)試->調(diào)試
保證流程的規(guī)范性和每段流程的嚴(yán)謹(jǐn)性必定會(huì)大幅度提高程序的質(zhì)量组底，減少后期維護(hù)的投入成本，在考慮輸出／投入比的前提下千萬不要理會(huì)那些“只要程序正常工作怎么改都行“的催促筐骇，在每個(gè)階段都保持程序的美觀债鸡、可擴(kuò)展性、健壯性等等都是一名優(yōu)秀程序員應(yīng)該具備的素質(zhì)铛纬。
性能篇
性能的重要性不言而喻厌均，但始終牢記“過早的優(yōu)化是萬惡之源“，When "I feel the need ...the need for speed",then just do it and do well.
-
第六章 程序性能分析
以一個(gè)大牛Andrew Appel在解決一個(gè)“重力場(chǎng)中多個(gè)物體相互作用的n體問題“的實(shí)際經(jīng)驗(yàn)告唆，描述了性能調(diào)優(yōu)的幾個(gè)方面：算法和數(shù)據(jù)結(jié)構(gòu)棺弊、算法調(diào)優(yōu)晶密、數(shù)據(jù)結(jié)構(gòu)重組、代碼調(diào)優(yōu)模她、系統(tǒng)軟件稻艰、硬件等等。
- 設(shè)計(jì)層次的架構(gòu)優(yōu)化是最有效的優(yōu)化：預(yù)防遠(yuǎn)勝于治療侈净，當(dāng)性能問題必須要解決時(shí)连锯，架構(gòu)上的優(yōu)化調(diào)整很可能會(huì)起到最大程度的效果。實(shí)際問題的解決方案都是受到整體架構(gòu)的制約的用狱，而設(shè)計(jì)一旦成型运怖，架構(gòu)上的改動(dòng)會(huì)影響系統(tǒng)的方方面面，穩(wěn)定性夏伊、可靠性摇展、可用性等等，考慮到這戲有時(shí)候智能采取層次內(nèi)或者模塊內(nèi)的優(yōu)化溺忧，可見架構(gòu)的重要性咏连。有關(guān)后臺(tái)架構(gòu)問題，有興趣的請(qǐng)看下我的《《大型網(wǎng)站架構(gòu)》》筆記鲁森，相信一定會(huì)有所裨益的祟滴。
- "貪心"的優(yōu)化策略：如果僅需要較小的優(yōu)化的話，先考慮“性價(jià)比“（收益／投入）最大的優(yōu)化方向歌溉，如果需要很大的優(yōu)化的話嘗試上面提到的幾個(gè)方面的優(yōu)化垄懂，如果它們彼此獨(dú)立的話，最后優(yōu)化的結(jié)果會(huì)是它們的乘積痛垛。
-
第七章 粗略估算
估算在建筑草慧、機(jī)械等工程方面的應(yīng)用比比皆是，幾乎成為了從業(yè)者的一項(xiàng)必備技能匙头，但顯然這項(xiàng)技能在軟件工程領(lǐng)域被很多人忽視了漫谷。估算可以做什么？如果你會(huì)時(shí)間復(fù)雜度和空間復(fù)雜度的估計(jì)就能僅從代碼分析出不同算法的優(yōu)劣蹂析，如果你知道你的計(jì)算機(jī)每秒鐘可以執(zhí)行多少條指令你甚至可以知道程序大概的運(yùn)行時(shí)間舔示，如果你知道一個(gè)項(xiàng)目的難度就會(huì)知道如何合理分配人力和資源安排項(xiàng)目的進(jìn)度……
- 估算要求對(duì)基本參數(shù)有一定的了解：機(jī)器每秒執(zhí)行的指令數(shù)，對(duì)這些基本參數(shù)的了解并不需要非常精確电抚，但是數(shù)量級(jí)不能相差太大惕稻，只有在對(duì)這些基本參數(shù)的了解的基礎(chǔ)上才能更準(zhǔn)確地在一段程序甚至整個(gè)項(xiàng)目中體現(xiàn)估算的最大價(jià)值。
- 多方面多方法的估算：也許一種估算方式得到的結(jié)果并不讓人放心喻频，那么多嘗試幾種方法比較它們結(jié)果缩宜，如果它們的結(jié)果一致的話很可能估算結(jié)果和實(shí)際值不會(huì)相差太大
- 常用估算方法：72法則肘迎、Little定律甥温、舍九檢驗(yàn)锻煌、量綱檢驗(yàn)
- 增加安全系數(shù)：如果事先不能對(duì)某方面足夠熟悉的話，適當(dāng)增加安全系數(shù)補(bǔ)償估算參數(shù)的錯(cuò)誤和對(duì)問題的了解不足姻蚓，保證估算的結(jié)果要在壞情況下依然可用
- 任何事都應(yīng)足夠簡(jiǎn)單宋梧，但不宜過于簡(jiǎn)單：估算并不是信口開河，結(jié)合前面的基本參數(shù)狰挡、估算方法捂龄、多方法的估算結(jié)果的比較和安全系數(shù)，估算簡(jiǎn)單加叁，但也不是那么簡(jiǎn)單_
-
第八章 算法設(shè)計(jì)技術(shù)
像第二章提到的一樣倦沧，算法上的靈機(jī)一動(dòng)也許就會(huì)讓程序更加高效，算法設(shè)計(jì)是一門技術(shù)它匕，也是一門藝術(shù)展融，我們把想法落實(shí)在代碼，然后從空間豫柬、時(shí)間告希、簡(jiǎn)潔性等等去分析程序，一點(diǎn)點(diǎn)地去調(diào)整去優(yōu)化烧给，直到達(dá)到我們滿意的效果燕偶。
問題：計(jì)算n元整數(shù)向量中連續(xù)子向量的最大和，比如[3,-2,3,-1]的最大連續(xù)子向量的和4础嫡，對(duì)應(yīng)向量為[3,-2,3].
解法一:一個(gè)一個(gè)地求每個(gè)子向量的和指么，記錄最大值
int maxSum(vector<int> nums){ int len = nums.size();//假定len>1 int maxSum = nums[0]; for(int i=0;i<len;++i){ for(int j=i+1;j<len;++j){ int tempSum = 0; for(int k=i;k<=j;++k){ tempSum += nums[k]; } maxSum = max(maxSum,tempSum); } } return maxSum; }這應(yīng)該是最粗魯最挫的一種方式了，O(n3)的時(shí)間復(fù)雜度榴鼎，而其中求和的n次內(nèi)循環(huán)其實(shí)是可以避免的
解法二:在以[i]開頭的向量中依次增加后面的元素值
int maxSum(vector<int> nums){ int len = nums.size();//假定len>1 int maxSum = nums[0]; for(int i=0;i<len;++i){ int tempSum = 0; for(int j=i+1;j<len;++j){ tempSum += nums[j]; maxSum = max(maxSum,tempSum); } } return maxSum; }解法三：還是消除求和的內(nèi)循環(huán)涧尿，不過是通過向量和之差計(jì)算
int maxSum(vector<int> nums){ int len = nums.size();//假定len>1 int tempSumArray[len＋1] = {0}; for(int i=0;i<len;++i){ tempSumArray[i＋1] = tempSumArray[i-1] + nums[i]; } int *tempArray = tempSumArray + 1; int maxSum = nums[0]; for(int i=0;i<len;++i){ int tempSum = 0; for(int j=i;j<len;++j){ tempSum = tempArray[j] - tempArray[i-1]; maxSum = max(maxSum,tempSum); } } return maxSum; }解法二和解法三都達(dá)到了將時(shí)間復(fù)雜度縮減為O(n2)的效果，解法二稍微好一點(diǎn)檬贰，解法三還引入了額外的O(n)空間姑廉。不過上面這三種算法都是對(duì)所有的子向量求和取最大值，而實(shí)際上通過遍歷整個(gè)向量可以篩選掉一些不可能作為目標(biāo)向量的向量翁涤，即求所有以每個(gè)元素作為目標(biāo)向量的元素的向量的和的最大值桥言，yes，動(dòng)態(tài)規(guī)劃的思想
int maxSum4(vector<int> nums){ int len = nums.size();//假定len>1 int maxSum = nums[0]; int* sumArray = new int[len]{0}; sumArray[0] = nums[0]; for(int i=1;i<len;++i){ int sum1 = sumArray[i-1] + nums[i]; int sum2 = nums[i]; sumArray[i] = max(sum1,sum2); maxSum = max(maxSum,sumArray[i]); } return maxSum; }算法四的時(shí)間復(fù)雜度為O(n),從數(shù)量級(jí)來看應(yīng)該是最低了葵礼，美中不足的是它還引入了額外的O(n)的空間号阿，如何在時(shí)間和空間折中就要根據(jù)實(shí)際條件而論了。
- 算法設(shè)計(jì)技巧：保存狀態(tài)避免重復(fù)計(jì)算鸳粉，信息預(yù)處理扔涧，分治，掃描，累加數(shù)組枯夜，下界弯汰，動(dòng)態(tài)規(guī)劃思想等等，這里可能只舉出了對(duì)于上面那個(gè)例子來說體現(xiàn)的技巧湖雹，而在算法設(shè)計(jì)中還有數(shù)不勝數(shù)的更多的技巧和思想
- 找到瓶頸逐步突破：程序優(yōu)化的關(guān)鍵在于找到優(yōu)化點(diǎn)咏闪，只有知道了可以在哪里優(yōu)化在哪里優(yōu)化會(huì)有最好的效果接下來的優(yōu)化才有意義也才有成效
-
第九章 代碼調(diào)優(yōu)
這一章作者以一個(gè)實(shí)際的圖形分析程序的調(diào)優(yōu)和整數(shù)取模、函數(shù)宏和內(nèi)聯(lián)代碼摔吏、順序搜索鸽嫂、二分搜索的搜索問題展示了調(diào)優(yōu)的一些技巧，這些問題實(shí)現(xiàn)起來都比較容易征讲，簡(jiǎn)要記錄一下調(diào)優(yōu)的過程据某。
- 整數(shù)取模問題：％運(yùn)算的開銷比一般的加減運(yùn)算要高1個(gè)數(shù)量級(jí)的時(shí)間，所以在不會(huì)讓代碼十分復(fù)雜而又需要性能調(diào)優(yōu)的話可以嘗試用等價(jià)的代數(shù)表達(dá)式替換模運(yùn)算：
k=(i+j)%len可以轉(zhuǎn)換為k=i+j;while(k>=n){k-=n;}
優(yōu)化效果取決于j的值诗箍，當(dāng)j＝1時(shí)哗脖，算法是順序訪問內(nèi)存的，根絕緩存的預(yù)見性扳还，可以提前取出下個(gè)要操作的值才避，運(yùn)算時(shí)間主要在模運(yùn)算上，而當(dāng)j過大時(shí)氨距，每次從數(shù)組中拿值時(shí)內(nèi)存都要重新加載到高速緩存中桑逝，時(shí)間大多消耗在這里，模運(yùn)算的消耗相比就小很多了俏让。因此實(shí)際優(yōu)化的時(shí)候還要考慮對(duì)應(yīng)的參數(shù)和機(jī)器類型楞遏、配置。 - 函數(shù)首昔、宏和內(nèi)聯(lián)代碼：一般來就運(yùn)算時(shí)間來說函數(shù)>內(nèi)聯(lián)代碼>宏
- 順序搜索：添加哨兵元素合并測(cè)試條件和展開循環(huán)獲得CPU多通道加速
- 二分搜索：通過添加哨兵元素寡喝、改變不變式為
x[l]<t<=x[u],合并了測(cè)試條件，減少了比較次數(shù)勒奇；等價(jià)的代數(shù)表達(dá)式將上下限的表示方法轉(zhuǎn)換成了下限與增量的表示法
- 過早的優(yōu)化是萬惡之源：效率和可用性预鬓、穩(wěn)定性等其他性質(zhì)一樣重要，不過在具體的情景下可能對(duì)某方面有所側(cè)重赊颠，而在程序的初開發(fā)階段一定是以保障可用性為前提的格二，明確認(rèn)識(shí)效率的角色才能在在各種指標(biāo)前做出正確的抉擇
- 性能度量：性能的好壞在不同問題上應(yīng)該有明確的指標(biāo)，判斷性能好壞也應(yīng)該有響應(yīng)的性能監(jiān)控工具來實(shí)時(shí)地監(jiān)控程序的性能竣蹦，一旦到達(dá)某個(gè)低點(diǎn)時(shí)自動(dòng)報(bào)警
- 沒有壞的話就不要修：只有真正意識(shí)到程序的性能真的成為問題時(shí)才去將性能優(yōu)化作為專門的課題去解決顶猜，這并不意味著在一開始編寫代碼時(shí)可以完全不考慮代碼的性能，只是說此時(shí)不必過度關(guān)注程序性能痘括，在不影響開發(fā)效率的情況下優(yōu)秀程序員自然會(huì)通過自己的經(jīng)驗(yàn)和對(duì)問題的理解寫出優(yōu)秀的代碼长窄，只要性能不要過分低或者有很明顯又很容易改進(jìn)的優(yōu)化點(diǎn)滔吠，可以暫時(shí)不優(yōu)化
- 整數(shù)取模問題：％運(yùn)算的開銷比一般的加減運(yùn)算要高1個(gè)數(shù)量級(jí)的時(shí)間，所以在不會(huì)讓代碼十分復(fù)雜而又需要性能調(diào)優(yōu)的話可以嘗試用等價(jià)的代數(shù)表達(dá)式替換模運(yùn)算：
-
第十章 節(jié)省空間
上一章的優(yōu)化主要是對(duì)時(shí)間優(yōu)化而言的，這一章重點(diǎn)在于優(yōu)化空間使用挠日。
假設(shè)一個(gè)200x200的地圖中有2000個(gè)點(diǎn)存在住戶i疮绷，1<=i<=2000,如何存儲(chǔ)這2000個(gè)住戶的位置？
方案1:最直接的就是用一個(gè)二維數(shù)組肆资，所有住戶在的位置置矗愧，其他置0灶芝，這樣需要200x200x4＝160000B＝156.25KB
方案1明顯浪費(fèi)了很多無用的空間存儲(chǔ)根本就不需要的值郑原，對(duì)于這類稀疏數(shù)據(jù)的存儲(chǔ)，可以用專門的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)
方案2:類似散列的存儲(chǔ)方式夜涕，可以把x坐標(biāo)作為散列值犯犁，對(duì)應(yīng)一個(gè)包括y坐標(biāo)和編號(hào)的列表：
0->2,17->3,14
1->3,12
...
2000
這樣就只存儲(chǔ)了需要的信息＋多余的指針，空間大概為2000*12+800=24800B=24KB,不過這種存儲(chǔ)方式在查找某位置的元素值時(shí)確實(shí)要比方案一直接用數(shù)組表示慢一些女器，因?yàn)槊看尾檎业臅r(shí)候都要對(duì)x鏈接的列表逐個(gè)查找- 節(jié)省空間的好處：空間的緊湊往往意味著數(shù)據(jù)結(jié)構(gòu)的合理酸役，意味著數(shù)據(jù)的冗余度減少，這樣會(huì)使程序變得更加簡(jiǎn)單驾胆，也會(huì)在運(yùn)行時(shí)間上得到想要的作用涣澡，而且小程序也會(huì)更快地被內(nèi)存加載，更容易加入到高速緩存中
- 簡(jiǎn)單性可以衍生出功能性丧诺、健壯性以及速度和空間
- 常用的數(shù)據(jù)空間技術(shù)：不存儲(chǔ)重新計(jì)算入桂、稀疏數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)壓縮驳阎、不同的分配策略抗愁、垃圾回收等等常用的技術(shù)都可以用于空間節(jié)省上，但首先還是要明確問題對(duì)時(shí)間和空間的要求呵晚，因?yàn)樯厦鎺追N方式在某些情況下雖然節(jié)省了空間但卻是以犧牲運(yùn)行速度為代價(jià)的
- 節(jié)省空間原理：先要搞清空間開銷的概念和實(shí)際問題真正的空間開銷蜘腌，發(fā)掘空間的“熱點(diǎn)”、熟悉空間的度量饵隙、正確處理空間與時(shí)間的折中撮珠、與運(yùn)行環(huán)境的協(xié)作、使用適合任務(wù)的正確工具金矛，都是節(jié)省空間的出發(fā)角度
以上是性能篇的大概內(nèi)容劫瞳，性能的重要性不言而喻，即使隨著硬件技術(shù)的發(fā)展硬件變得越來也便宜绷柒，作為程序員也應(yīng)該保持對(duì)性能的追求志于，追求用戶的極致體驗(yàn)。對(duì)性能的預(yù)估废睦、測(cè)試伺绽、監(jiān)控、優(yōu)化應(yīng)該是優(yōu)秀程序員必備的技能，在大型團(tuán)隊(duì)中奈应，在保證項(xiàng)目可用性和開發(fā)效率的情況下澜掩，可能還會(huì)設(shè)立單獨(dú)的性能調(diào)優(yōu)小組專門負(fù)責(zé)性能的測(cè)試和優(yōu)化。
應(yīng)用篇
這一部分是建立在第一部分和第二部分的基礎(chǔ)上杖挣，講解了幾個(gè)比較常用的算法肩榕，由于這些算法比較普遍，在一般的輔導(dǎo)書上也都有所講解惩妇，這里不再按每一章的內(nèi)容依次記錄株汉，只是把主要的內(nèi)容和需要注意的地方總結(jié)一下。
- 應(yīng)用：幾種常見排序,插排歌殃、快排（有幾種不同方式）乔妈，利用隨機(jī)數(shù)取樣，不同數(shù)據(jù)結(jié)構(gòu)下的搜索氓皱，堆數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)路召、堆排序和優(yōu)先級(jí)隊(duì)列的堆實(shí)現(xiàn)，關(guān)于字符串的一些問題波材，如單詞查找統(tǒng)計(jì)股淡、字串匹配、隨機(jī)文本生成廷区，這些問題的解決方案很多都用到了前面兩部分所介紹的方法和思想唯灵，可以說是前面兩部分的一個(gè)實(shí)際應(yīng)用測(cè)試
- 排序問題：幾種不同排序方式會(huì)在時(shí)間復(fù)雜度和空間復(fù)雜度有差異，在平均情況躲因、最壞情況和最好情況（一般不考慮）也會(huì)有所差異早敬，因此在選擇排序方式時(shí)要依據(jù)問題的要求選擇恰當(dāng)?shù)呐判蚍绞剑芏嗲闆r可以直接用封裝好的庫函數(shù)解決大脉，但要清楚庫函數(shù)的實(shí)現(xiàn)效率雖然高但是因?yàn)閷?duì)上的封裝和適配搞监，會(huì)降低執(zhí)行效率，如果發(fā)現(xiàn)在這方面確實(shí)可以有足夠大的優(yōu)化要自己手動(dòng)編寫特定的排序方式镰矿，比如我們第一章說的位向量排序
-
編程過程中的幾個(gè)步驟：在第一部分的總結(jié)里也已經(jīng)提到程序解決的步驟琐驴，這里再細(xì)化一下
- 正確分析理解面臨的問題
- 抽象問題，盡可能用數(shù)學(xué)語言表示
- 考慮盡可能多的解法秤标，一開始想出來的方法不一定就是最合適的方法绝淡，觀念的壁壘、思維的束縛甚至是之前類似問題的解決經(jīng)驗(yàn)都有可能造成不合適的第一想法苍姜，動(dòng)手之前多想一想牢酵，動(dòng)手的時(shí)候才會(huì)更快，動(dòng)完手后印象才能更深刻
- 回顧,"改進(jìn)的余地總是存在的",這就要求我們自己主動(dòng)去check可能出現(xiàn)的bug衙猪，去優(yōu)化程序的性能馍乙，去總結(jié)得到的經(jīng)驗(yàn)
-
小技巧：
- 使用哨兵簡(jiǎn)化代碼
- 迭代替換遞歸提高運(yùn)行速度
- 由于內(nèi)存的預(yù)加載機(jī)制布近、數(shù)據(jù)的連續(xù)性和大小插入元素等操作數(shù)組不一定會(huì)比鏈表慢
- 分配空間時(shí)可以一次性分配所需空間提高空間利用率和空間的連續(xù)性以便加載到內(nèi)存的時(shí)候更快
- 過程的抽象,每個(gè)數(shù)據(jù)結(jié)構(gòu)都要從它的兩方面去看，外部是規(guī)范丝格，說明了它能做什么撑瞧；內(nèi)部是實(shí)現(xiàn)，說明了是怎么做的,在編寫一個(gè)大函數(shù)時(shí)可以假定其中的一個(gè)獨(dú)立的函數(shù)已經(jīng)實(shí)現(xiàn)僅考慮它的功能搭好整個(gè)函數(shù)的算法框架显蝌，然后用同樣的方法去細(xì)化每個(gè)內(nèi)部函數(shù)的實(shí)現(xiàn)预伺，這樣會(huì)讓思路更清晰，代碼的易讀性也會(huì)更好
以上只是在讀書的時(shí)候做的一些筆記和總結(jié)曼尊，現(xiàn)在對(duì)這本書還遠(yuǎn)遠(yuǎn)沒有吃透酬诀，計(jì)劃先去補(bǔ)充一些算法知識(shí)，然后回過頭來再過一遍這本書涩禀，弄懂每一道習(xí)題料滥，學(xué)到真正的“編程珠璣”然眼。
