程式設計珠玑

本文首發于個人部落格之程式設計珠玑,之後會陸續将部落格轉移至個人部落格，期待與各位的交流

這不是一本具體算法的講解或者代碼編寫的教程，但是從書中的字裡行間，我們可以學到的是更多的軟知識:對程式設計新的認識、更加發散的思維方式、更嚴格的代碼要求、堪比瑞士軍刀的小技巧…… 程式設計也許入門并不難，但是要想真正成為一名優秀的軟體工程師，還是需要很多錘煉。内外兼修，方成大器。

基礎篇

• 第一章 開篇

  首先作者提出一個實際問題：

  如何給磁盤的某個檔案排序，更具體來說就是是對一個最多包含1千萬條記錄，每條記錄都是7位整數的檔案，而且隻有1MB的記憶體可以使用

  從實際問題中提煉出更明确的數學定義：

  輸入：一個最多包含n個整數的檔案，每個數都小于n，其中n=10^7。可以保證輸入檔案中不存在重複整數

  輸出：按升序排列的輸入整數的清單

  限制：1MB左右的記憶體空間，充足的磁盤存儲空間。運作時間最多幾分鐘，控制在10秒内不再需要進一步優化

  考慮一般的解法，直接讀入所有的整數，然後進行快排堆排之類的排序，時間複雜度很明顯是O(nlogn),但空間複雜度是O(n),即如果n=10^7時，用4個位元組的int型存儲每個整數，那麼需要的空間是(4*107)/210210=38MB,很顯然超出了記憶體限制，而考慮實際n的大小限制和每個整數隻會出現一次的限制，而所謂的排序也隻是把從檔案中的整數按在1－n内出現的順序輸出而已，是以隻要對n之内出現的整數做一下标記最後輸出标記過的整數就可以了，考慮到這，位向量（也叫位圖）就成了比較合适的資料結構的選擇，每個位的0、1值表示一個數字是否出現過，實作的時間複雜度為O(n),空間複雜度為O(n),考慮n取最大值10^7時，需要的空間為107/8/210/210=1.2MB,代碼實作如下：

  #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 = ;
      while(testFile >> s){
          numBits[atoi(s.c_str())-] = ;
          ++count;
      }
      testFile.close();
  
      for(int i=;i<N;++i){
          if(numBits[i] == ){
              cout<<i+<<endl;
          }
      }
  }
  int main(int argc, const char * argv[]) {
      intSort();
      return ;
  }
             

  那麼進一步考慮：

  如果嚴格限制程式占用記憶體不能超過1M，應該怎麼處理？

  如果每個數最多出現10次，又應該如何改動算法？所用存儲空間是怎樣變化的呢？

  在解決這個實際問題的方案中，我們看到了不同于比較排序的一種排序方式：位向量排序，而且從這個問題中也引出了作者的一些思考和對讀者的啟示：
  • 做一個”懶”工程師：處理問題時，即便是一看上去就知道解法的問題，不要馬上動手編寫代碼，花些時間去明确問題，抽象問題模型，結合問題的特點去分析，等靈光一現時再動手。作者在解決上題時首先是對問題進行了數學定義，考慮到問題中資料的特點以向量的方式解決了問題并且時間複雜度和空間複雜度都較低。這樣的方式不僅能收到更好的編碼效果，考慮的情況會更加完善，調試起來的時間也會縮短，而且經過深度思考再動手的印象要深刻的多，等之後再遇到類似的問題時，馬上就會湧現解決問題的思路，這樣才能積累真正的經驗。
  • 時間和空間可以是雙赢的：确實很多時候也許我們會在時間和空間之間做折中的選擇，但是這種折中一定應該是在我們仔細分析了某方面不能再有改善的情況下，而很多情況下因為自己算法能力的不足和思維能力的局限，也許自己的算法可以在時間和空間雙重優化，這就要求一方面自己要深度思考目前算法的優化空間，另一方面可以向更優秀的人請教是否有完全不同但是可以達到更好效果的方法或者對自己算法的建議，如果确實确定要做折中處理的話，要明确問題對時間和空間要求的嚴格性和最大容忍限度，然後在合理犧牲某方面的前提下向預定目标靠攏。
  • 簡單的設計：“設計者确定其設計已經達到了完美的标準不是不能再增加任何東西，而是不能再減少任何東西”，在滿足要求的前提下盡量讓設計簡潔，有利于今後的擴充和排錯，“大道至簡“，設計需要的也許更多是簡潔的美。
• 第二章 啊哈！算法

  1. 給定一個最多包含m=40億個随機排列的n=32位整數的順序檔案，找出一個不在檔案中的32位整數。在記憶體足夠的情況下如何解決該問題？如果有幾個外部的“臨時檔案“可用，但是僅有幾百位元組的記憶體，又該如何處理？
  2. 将一個n元一維向量想做旋轉i個位置(如對n=3元向量“abc“，當i＝1時，結果為“bca“)
  3. 給定一個英文字典，找出其中的所有變位詞集合。（變位詞指的包含相同數量相同字母的單詞，因為他們通過調整字母的順序可以變為一個單詞是以叫變位詞，如”stop”和”tops”和”pots”）

  對于問題1，首先明确一下肯定是存在整數不在檔案中的，因為32位整數最多可以表示的數字是2^32=4294967296>4000000000

  （1）在記憶體充足的情況下，可以用上述位向量的做法，初始化2^32個位為0，每讀到一個數字就将對應下标的位數組的值置為1，最後統計值仍為0的元素就是沒有出現過的整數，這樣的做法時間複雜度是O(2^n),空間占用大約為O（2n/8）B,當n＝32時占用空間大小約為2n/8/210/210=512MB

  （2）記憶體不夠有臨時檔案可以使用時，又該如何做呢？既然有臨時檔案可以用，那可以将原來大檔案中的數字配置設定到臨時檔案中，當臨時檔案的規模夠小時再采用上面說的位向量的算法。配置設定可以采用散列的方法，比如通過簡單的模上臨時檔案的個數将結果相同的聚合到一個檔案，判斷缺失元素在哪個檔案的方法是在向臨時檔案插入元素的時候統計每個臨時檔案的數字個數，因為我們是可以知道根據我們標明的雜湊演算法在沒有元素缺失情況下的數字個數k的，那麼這樣就隻需要比較散列完成後臨時檔案的個數與k比較，如果比k小的話那麼這個臨時檔案中就存在缺失元素，接下來以這個臨時檔案為主檔案，再次采用前面所說的散列方法（此時雜湊演算法的參數可能需要調整）如此疊代下去直到限制的記憶體空間足以承載包含缺失元素的檔案規模時，回到第一種情況處理。 可以看到這也展現了二分搜尋的思想，隻不過是以檔案包含的一系列整數為範圍，用包含這些整數的檔案表示這個範圍，通過比較檔案中整數個數與期望個數判定缺失元素所在檔案範圍，進而達到了縮小問題規模的效果将問題轉換成記憶體充足的情況。

  對于問題二，看起來比較簡單，代碼實作起來也不難，不過作者提供的幾個巧妙的算法倒讓人耳目一新。

  我一開始的想法是作者所說的“雜技算法“，

  void rotate(string str,int k){
      int len = str.length();
      if(len >  && k % len != ){
          //控制k在［1，len－1］内友善下标操作
          k = (k > len) ? k%len : k;
          k = (k < ) ? k+len : k;
          char curr_val = str[k]; //将被調整的值
          int to_pos = ; //将被調整到的位置
          char to_val = str[to_pos]; //現在将被調整到的位置對應的值
          int count = ;
          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;
  }
             

  時間複雜度為O(n),額外的空間複雜度為O(1),比較理想的一種算法，不過先不要滿足，再來看一種跌破眼睛卻又不得不為之叫好的算法

  void rotate2(string str,int k){
      //假設k已經在[1,len-1]範圍内，處理同上
      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的内部不會變化，想象線性代數中我們會怎麼做，yes:

  ab -> a^b -> a^b^ ->(a^b^)^=ba，a^表示a的逆向量

  嘗試下用左右手模拟10元數組向上旋轉5個位置的例子，相信你也會感歎它的神奇，雖然它要比上面那種算法稍慢一些，因為他做了中間轉換，每個字元不是一次性地移到目标位置，但是這種拆分向量用數學運算簡化算法的思想确實值得借鑒。

  再來看問題三，千萬不要想通過排列組合的方式去解決，要知道一個有26個字母的單詞就可能有26！種排列方式。考慮一下變位詞的定義，它們有共通點：組成字母集合相同。也就是說我們隻要為每個單詞選擇辨別和聚集相同辨別的單詞就好了。辨別可以是按所包含字母順序排列的單詞，比如”pots”,”stop”,”tops”的辨別都是 “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)==){
              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) == ){
          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 ;
  }
             

  這一章圍繞這三個問題，作者在給我們解決問題思路的同時也給我們留下更進一步思考的空間，而其中展現出的一些解決問題的模式很有借鑒意義：
  • 看起來很困難的問題也可以有一個簡單的、意想不到的答案：有的事情看上去很複雜但經過仔細分析後可能問題一下子就變得很簡單了，而即便是真正困難的問題，也不見得解決方法也很複雜，比如漢諾塔問題，很多時候我們缺乏的就是撥開問題迷霧、明确問題模型、把握問題本質的能力，而一旦這些都清楚了，解決方法也就顯而易見了
  • 其實很多解決問題的算法都是由一些基本操作組合而成的：這些基本操作中很多我們可能都已經爛熟于胸，是以我們要做的一方面是擴充自己的算法基礎，也就是多掌握一些基本的算法思想和進階資料結構，另一方面就是面對實際問題時能提取出問題的抽象模型，找到适合的基本操作，再結合問題的特點，對算法進行改進甚至另辟蹊徑，以一種巧妙的方式更簡單地解決問題

• 第三章 資料決定程式結構

  這一章并沒有算法的具體内容，作者隻是舉了幾個程式員常犯的錯誤，給出了避免錯誤使用資料結構導緻的一系列問題的建議，比如使用數組重新編寫重複代碼、封裝複雜結構、盡可能使用進階工具、從資料得出程式的結構等等。

  • 恰當的資料視圖實際上決定了程式的結構，資料的表示形式是程式設計的根本：資料結構＋算法＝程式，問題無非就是資料和算法，通過對問題的分析提取出問題模型，并結合合适的資料結構來理清思路，實際編寫代碼的時候采用語言提供的配套的資料結構實作。資料組織好了，算法清晰了，程式也就自然而然地完成了，而且可以完成的很漂亮，由此可見選對資料結構對解決好問題的重要性
  • 及時優化代碼：不要覺得代碼雖然很亂但是足夠滿足需求就可以了，如果每次我們都是這麼針對新需求添磚加瓦式的擴充程式的話，久而久之，代碼會醜的讓人難以直視，整個程式結構也會臃腫不堪，後期維護多花費的時間可能遠遠超過每次修改仔細審視并優化代碼的時間，等程式真的大了的時候再說重構可能就不是那麼輕松了
  • 發明家悖論”更一般性的問題也許更容易解決”：解決問題有的時候是由大化小，一點點的分析抓住問題的核心，而有的時候還需要由點到面的展開，不單去考慮n＝10的情況而是針對n為任意正整數的情況去做處理，這樣也許會讓思路一下子展開，找到問題的共通點，而且在很多需求變更頻繁的業務上，這樣的思考方式和編碼風格會大大提高程式的通用性和相容性

• 第四章 編寫正确的程式

  這一章以二分搜尋為例示範了算法驗證的“三步曲“：初始化、保持和終止

  • 初始化：循環初次執行的時候不變式為真
  • 保持：如果在某次疊代開始的 時候以及循環體執行的時候，不變式都為真，那麼，循環體執行完畢的時候不變式依然為真

  • 終止：循環能夠終止，并且能夠得到期望的結果

    程式編寫完成後測試的重要性并不亞于編碼本身，由于思維邏輯的漏洞或者程式編寫時的手誤都有可能造成程式Bug，而測試正是發現Bug的過程，也隻有發現了Bug，找到Bug的原因才能徹底解決Bug，保證程式的正确性和健壯性。

  程式員也應該充當測試人員的一部分角色，證明所用算法的正确性（實際中并不用一字一句地去證明），用全面的測試用例驗證程式結果，盡早在自己手中發現Bug，雖然實際工作中程式員不需要也沒有時間像測試人員一樣逐個地去考察程式的各個名額，但一些顯而易見的邏輯漏洞和性能問題最好還是在提測之前主動check一下才好。由于實際工作中，提測、測試、提Bug單的流程會浪費一定的時間，而且突然的一個Bug單也會打亂現在工作的節奏，是以這樣可以在一定程度上縮短程式開發的總周期，也可以增加别人對自己程式設計能力的肯定。試想如果你不時就會聽到測試人員對某位開發人員說“某某地方程式結果又有些不對啊“，想必這将會大大降低對這位開發者的信任程度。

• 第五章 程式設計小事

  這一章主要是就實際程式設計中遇到的一些問題和調試手段給予讀者一些小技巧，雖然小得或許不值一提或許我們都已經了然于胸又或許我們并不清楚這些概念但卻在實實在在地使用。

  • 使用“腳手架“（scaffolding）：在我看來，腳手架應該是一個對方面我們測試的工具的形象比喻，為了友善頻繁地測試，我們可以先用僞代碼實作檢查沒有什麼問題再用響應的語言翻譯過來，可以編寫專門的測試腳本或者GUI界面，可以在main函數中控制讓測試者手動輸入資料保證程式在測試過程中不用修改，可以使用斷言在程式運作過程中檢測某段邏輯的結果（類似于自動斷點，常用在單獨的測試檔案中，比如unit），可以使用自動化工具隻需要輸入資料自動去跑測試用例，可以在程式中添加計時代碼評定程式性能……這些方法依據問題場景、問題的複雜程度，投入成本與測試成本的比重 而被選擇用來測試程式，我們的目的就用盡量少的時間發現盡量多的Bug。
  • 調試手段：發現Bug，首先要懷疑，根據Bug結果、錯誤日志等現有資料去懷疑可能會造成Bug的原因，然後再通過打日志、設斷點等手段去驗證；而如果确實分析不出懷疑對象可以采用“控制變量“，“二分搜尋“等思想嘗試去改變程式的某一個變量或者某一段邏輯，比較結果的差異性。 如果問題在某種情況下發生而某種情況下不發生，首先比較兩種情況的不同之處，再結合錯誤提示分析可能原因，上下夾擊可以更快地找到Bug原因。找到Bug原因就已經是解決Bug的一大半了，或者更武斷一點說 隻要找到Bug的原因就肯定可以解決。

以上為本書的基礎篇,通篇讀下來可以看到作者安排章節的順序和我們日常産品開發的流程是一緻的：

分析問題->設計算法->結合語言選擇合适的資料結構程式設計實作->測試->調試

保證流程的規範性和每段流程的嚴謹性必定會大幅度提高程式的品質，減少後期維護的投入成本，在考慮輸出／投入比的前提下千萬不要理會那些“隻要程式正常工作怎麼改都行“的催促，在每個階段都保持程式的美觀、可擴充性、健壯性等等都是一名優秀程式員應該具備的素質。

性能篇

性能的重要性不言而喻，但始終牢記“過早的優化是萬惡之源“，When “I feel the need …the need for speed”,then just do it and do well.

• 第六章 程式性能分析

  以一個大牛Andrew Appel在解決一個“重力場中多個物體互相作用的n體問題“的實際經驗，描述了性能調優的幾個方面：算法和資料結構、算法調優、資料結構重組、代碼調優、系統軟體、硬體等等。

  • 設計層次的架構優化是最有效的優化：預防遠勝于治療，當性能問題必須要解決時，架構上的優化調整很可能會起到最大程度的效果。實際問題的解決方案都是受到整體架構的制約的，而設計一旦成型，架構上的改動會影響系統的方方面面，穩定性、可靠性、可用性等等，考慮到這戲有時候智能采取層次内或者子產品内的優化，可見架構的重要性。有關背景架構問題，有興趣的請看下我的《《大型網站架構》》筆記，相信一定會有所裨益的。
  • “貪心”的優化政策：如果僅需要較小的優化的話，先考慮“成本效益“（收益／投入）最大的優化方向，如果需要很大的優化的話嘗試上面提到的幾個方面的優化，如果它們彼此獨立的話，最後優化的結果會是它們的乘積。

• 第七章 粗略估算

  估算在建築、機械等工程方面的應用比比皆是，幾乎成為了從業者的一項必備技能，但顯然這項技能在軟體工程領域被很多人忽視了。估算可以做什麼？如果你會時間複雜度和空間複雜度的估計就能僅從代碼分析出不同算法的優劣，如果你知道你的計算機每秒鐘可以執行多少條指令你甚至可以知道程式大概的運作時間，如果你知道一個項目的難度就會知道如何合理配置設定人力和資源安排項目的進度……

  • 估算要求對基本參數有一定的了解：機器每秒執行的指令數，對這些基本參數的了解并不需要非常精确，但是數量級不能相差太大，隻有在對這些基本參數的了解的基礎上才能更準确地在一段程式甚至整個項目中展現估算的最大價值。
  • 多方面多方法的估算：也許一種估算方式得到的結果并不讓人放心，那麼多嘗試幾種方法比較它們結果，如果它們的結果一緻的話很可能估算結果和實際值不會相差太大
  • 常用估算方法：72法則、Little定律、舍九檢驗、量綱檢驗
  • 增加安全系數：如果事先不能對某方面足夠熟悉的話，适當增加安全系數補償估算參數的錯誤和對問題的了解不足，保證估算的結果要在壞情況下依然可用
  • 任何事都應足夠簡單，但不宜過于簡單：估算并不是信口開河，結合前面的基本參數、估算方法、多方法的估算結果的比較和安全系數，估算簡單，但也不是那麼簡單^_^

• 第八章 算法設計技術

  像第二章提到的一樣，算法上的靈機一動也許就會讓程式更加高效，算法設計是一門技術，也是一門藝術，我們把想法落實在代碼，然後從空間、時間、簡潔性等等去分析程式，一點點地去調整去優化，直到達到我們滿意的效果。

  問題：計算n元整數向量中連續子向量的最大和，比如[3,-2,3,-1]的最大連續子向量的和4，對應向量為[3,-2,3].

  解法一:一個一個地求每個子向量的和，記錄最大值

  int maxSum(vector<int> nums){
      int len = nums.size();//假定len>1
      int maxSum = nums[];
      for(int i=;i<len;++i){
          for(int j=i+;j<len;++j){
              int tempSum = ;
              for(int k=i;k<=j;++k){
                  tempSum += nums[k];
              }
              maxSum = max(maxSum,tempSum);
          }
      }
      return maxSum;
  }
             

  這應該是最粗魯最挫的一種方式了，O(n3)的時間複雜度，而其中求和的n次内循環其實是可以避免的

  解法二:在以[i]開頭的向量中依次增加後面的元素值

  int maxSum(vector<int> nums){
      int len = nums.size();//假定len>1
      int maxSum = nums[];
      for(int i=;i<len;++i){
          int tempSum = ;
          for(int j=i+;j<len;++j){
              tempSum += nums[j];
              maxSum = max(maxSum,tempSum);
          }
      }
      return maxSum;
  }
             

  解法三：還是消除求和的内循環，不過是通過向量和之差計算

  int maxSum(vector<int> nums){
      int len = nums.size();//假定len>1
  
      int tempSumArray[len＋] = {};
      for(int i=;i<len;++i){
          tempSumArray[i＋] = tempSumArray[i-] + nums[i];
      }
      int *tempArray = tempSumArray + ;
  
      int maxSum = nums[];
      for(int i=;i<len;++i){
          int tempSum = ;
          for(int j=i;j<len;++j){
              tempSum = tempArray[j] - tempArray[i-];
              maxSum = max(maxSum,tempSum);
          }
      }
      return maxSum;
  }
             

  解法二和解法三都達到了将時間複雜度縮減為O(n2)的效果，解法二稍微好一點，解法三還引入了額外的O(n)空間。不過上面這三種算法都是對所有的子向量求和取最大值，而實際上通過周遊整個向量可以篩選掉一些不可能作為目标向量的向量，即求所有以每個元素作為目标向量的元素的向量的和的最大值，yes，動态規劃的思想

  int maxSum4(vector<int> nums){
      int len = nums.size();//假定len>1
      int maxSum = nums[];
  
      int* sumArray = new int[len]{};
      sumArray[] = nums[];
      for(int i=;i<len;++i){
          int sum1 = sumArray[i-] + nums[i];
          int sum2 = nums[i];
          sumArray[i] = max(sum1,sum2);
  
          maxSum = max(maxSum,sumArray[i]);
      }
  
      return maxSum;
  }
             

  算法四的時間複雜度為O(n),從數量級來看應該是最低了，美中不足的是它還引入了額外的O(n)的空間，如何在時間和空間折中就要根據實際條件而論了。
  • 算法設計技巧：儲存狀态避免重複計算，資訊預處理，分治，掃描，累加數組，下界，動态規劃思想等等，這裡可能隻舉出了對于上面那個例子來說展現的技巧，而在算法設計中還有數不勝數的更多的技巧和思想
  • 找到瓶頸逐漸突破：程式優化的關鍵在于找到優化點，隻有知道了可以在哪裡優化在哪裡優化會有最好的效果接下來的優化才有意義也才有成效

• 第九章 代碼調優

  這一章作者以一個實際的圖形分析程式的調優和整數取模、函數宏和内聯代碼、順序搜尋、二分搜尋的搜尋問題展示了調優的一些技巧，這些問題實作起來都比較容易，簡要記錄一下調優的過程。

  1. 整數取模問題：％運算的開銷比一般的加減運算要高1個數量級的時間，是以在不會讓代碼十分複雜而又需要性能調優的話可以嘗試用等價的代數表達式替換模運算：

     k=(i+j)%len

     可以轉換為

     k=i+j;while(k>=n){k-=n;}

     優化效果取決于j的值，當j＝1時，算法是順序通路記憶體的，根絕緩存的預見性，可以提前取出下個要操作的值，運算時間主要在模運算上，而當j過大時，每次從數組中拿值時記憶體都要重新加載到高速緩存中，時間大多消耗在這裡，模運算的消耗相比就小很多了。是以實際優化的時候還要考慮對應的參數和機器類型、配置。
  2. 函數、宏和内聯代碼：一般來就運算時間來說函數>內聯代碼>宏
  3. 順序搜尋：添加哨兵元素合并測試條件和展開循環獲得CPU多通道加速

  4. 二分搜尋：通過添加哨兵元素、改變不變式為

     x[l]<t<=x[u],合并了測試條件，減少了比較次數；等價的代數表達式将上下限的表示方法轉換成了下限與增量的表示法

  • 過早的優化是萬惡之源：效率和可用性、穩定性等其他性質一樣重要，不過在具體的情景下可能對某方面有所側重，而在程式的初開發階段一定是以保障可用性為前提的，明确認識效率的角色才能在在各種名額前做出正确的抉擇
  • 性能度量：性能的好壞在不同問題上應該有明确的名額，判斷性能好壞也應該有響應的性能監控工具來實時地監控程式的性能，一旦到達某個低點時自動報警
  • 沒有壞的話就不要修：隻有真正意識到程式的性能真的成為問題時才去将性能優化作為專門的課題去解決，這并不意味着在一開始編寫代碼時可以完全不考慮代碼的性能，隻是說此時不必過度關注程式性能，在不影響開發效率的情況下優秀程式員自然會通過自己的經驗和對問題的了解寫出優秀的代碼，隻要性能不要過分低或者有很明顯又很容易改進的優化點，可以暫時不優化

• 第十章 節省空間

  上一章的優化主要是對時間優化而言的，這一章重點在于優化空間使用。

  假設一個200x200的地圖中有2000個點存在住戶i，1<=i<=2000,如何存儲這2000個住戶的位置？

  方案1:最直接的就是用一個二維數組，所有住戶在的位置置，其他置0，這樣需要200x200x4＝160000B＝156.25KB

  方案1明顯浪費了很多無用的空間存儲根本就不需要的值，對于這類稀疏資料的存儲，可以用專門的資料結構存儲

  方案2:類似散列的存儲方式，可以把x坐标作為散列值，對應一個包括y坐标和編号的清單：

  0->2,17->3,14

  1->3,12

  …

  2000

  這樣就隻存儲了需要的資訊＋多餘的指針，空間大概為2000*12+800=24800B=24KB,不過這種存儲方式在查找某位置的元素值時确實要比方案一直接用數組表示慢一些，因為每次查找的時候都要對x連結的清單逐個查找

  • 節省空間的好處：空間的緊湊往往意味着資料結構的合理，意味着資料的備援度減少，這樣會使程式變得更加簡單，也會在運作時間上得到想要的作用，而且小程式也會更快地被記憶體加載，更容易加入到高速緩存中
  • 簡單性可以衍生出功能性、健壯性以及速度和空間
  • 常用的資料空間技術：不存儲重新計算、稀疏資料結構、資料壓縮、不同的配置設定政策、垃圾回收等等常用的技術都可以用于空間節省上，但首先還是要明确問題對時間和空間的要求，因為上面幾種方式在某些情況下雖然節省了空間但卻是以犧牲運作速度為代價的
  • 節省空間原理：先要搞清空間開銷的概念和實際問題真正的空間開銷，發掘空間的“熱點”、熟悉空間的度量、正确處理空間與時間的折中、與運作環境的協作、使用适合任務的正确工具，都是節省空間的出發角度

以上是性能篇的大概内容，性能的重要性不言而喻，即使随着硬體技術的發展硬體變得越來也便宜，作為程式員也應該保持對性能的追求，追求使用者的極緻體驗。對性能的預估、測試、監控、優化應該是優秀程式員必備的技能，在大型團隊中，在保證項目可用性和開發效率的情況下，可能還會設立單獨的性能調優小組專門負責性能的測試和優化。

應用篇

這一部分是建立在第一部分和第二部分的基礎上，講解了幾個比較常用的算法，由于這些算法比較普遍，在一般的輔導書上也都有所講解，這裡不再按每一章的内容依次記錄，隻是把主要的内容和需要注意的地方總結一下。

• 應用：幾種常見排序,插排、快排（有幾種不同方式），利用随機數取樣，不同資料結構下的搜尋，堆資料結構的實作、堆排序和優先級隊列的堆實作，關于字元串的一些問題，如單詞查找統計、字串比對、随機文本生成，這些問題的解決方案很多都用到了前面兩部分所介紹的方法和思想，可以說是前面兩部分的一個實際應用測試
• 排序問題：幾種不同排序方式會在時間複雜度和空間複雜度有差異，在平均情況、最壞情況和最好情況（一般不考慮）也會有所差異，是以在選擇排序方式時要依據問題的要求選擇恰當的排序方式，很多情況可以直接用封裝好的庫函數解決，但要清楚庫函數的實作效率雖然高但是因為對上的封裝和适配，會降低執行效率，如果發現在這方面确實可以有足夠大的優化要自己手動編寫特定的排序方式，比如我們第一章說的位向量排序
• 程式設計過程中的幾個步驟：在第一部分的總結裡也已經提到程式解決的步驟，這裡再細化一下
  1. 正确分析了解面臨的問題
  2. 抽象問題，盡可能用數學語言表示
  3. 考慮盡可能多的解法，一開始想出來的方法不一定就是最合适的方法，觀念的壁壘、思維的束縛甚至是之前類似問題的解決經驗都有可能造成不合适的第一想法，動手之前多想一想，動手的時候才會更快，動完手後印象才能更深刻
  4. 回顧,”改進的餘地總是存在的”,這就要求我們自己主動去check可能出現的bug，去優化程式的性能，去總結得到的經驗
• 小技巧
  • 使用哨兵簡化代碼
  • 疊代替換遞歸提高運作速度
  • 由于記憶體的預加載機制、資料的連續性和大小插入元素等操作數組不一定會比連結清單慢
  • 配置設定空間時可以一次性配置設定所需空間提高空間使用率和空間的連續性以便加載到記憶體的時候更快
  • 過程的抽象,每個資料結構都要從它的兩方面去看，外部是規範，說明了它能做什麼；内部是實作，說明了是怎麼做的,在編寫一個大函數時可以假定其中的一個獨立的函數已經實作僅考慮它的功能搭好整個函數的算法架構，然後用同樣的方法去細化每個内部函數的實作，這樣會讓思路更清晰，代碼的易讀性也會更好

以上隻是在讀書的時候做的一些筆記和總結，現在對這本書還遠遠沒有吃透，計劃先去補充一些算法知識，然後回過頭來再過一遍這本書，弄懂每一道習題，學到真正的“程式設計珠玑”