《編程珠璣》

第一部分 基礎(chǔ)

第1章 開篇

問題抽象描述：對10^7個正整數(shù)進行排序颓哮，只能使用1MB左右的內(nèi)存空間

解決方案：使用位圖铃芦，每個比特位代表一個整數(shù)迁筛，如果出現(xiàn)該整數(shù)則將該位置為1.

應(yīng)用：該方法適合輸入數(shù)據(jù)限制在相對較小的范圍內(nèi)咳蔚；數(shù)據(jù)沒有重復(fù)；而且對于每條記錄而言锯茄，除了單一的整數(shù)外厢塘，沒有任何其他關(guān)聯(lián)數(shù)據(jù)。位圖的數(shù)據(jù)結(jié)構(gòu)肌幽，描述了一個有限定義域內(nèi)的稠密集合晚碾。

第2章 啊哈！算法

問題抽象描述：
A.找出一個不在40億個隨機排列的32位整數(shù)的順序文件中的數(shù)牍颈，僅有幾百字節(jié)的內(nèi)存
B.將一個n元一維向量向左選裝i個位置迄薄，僅有數(shù)十個額外字節(jié)的存儲空間，在正比于n的時間內(nèi)完成向量的旋轉(zhuǎn)
C.找出一個英語字典所有變位詞集合煮岁。(pots,ptos, stop這種變位詞)

解決方法：
A.二分搜索：采用已知包含至少一個缺失元素的一系列整數(shù)作為范圍讥蔽，并使用包含所有這些整數(shù)在內(nèi)的文件表示這個范圍。通過統(tǒng)計中間點之上和之下的元素來探測范圍画机；或者上面或者下面的范圍具有至多全部范圍的一般元素冶伞。由于整個范圍中有一個缺失元素，因此我們所需的那一半范圍中必須也包含缺失的元素步氏。
B.其中以前在很多地方都看到過這個方法响禽，從ab開始，首先對a求逆得到c荚醒，然后對b求逆得到d芋类，最后整體求逆，就得到ba了界阁，然后各段的逆又可以在內(nèi)部再次求逆侯繁，以此遞歸。
C.標識字典中的每一個詞泡躯，使得在相同變位詞類中的單詞具有相同的標識贮竟。

第3章 數(shù)據(jù)決定程序結(jié)構(gòu)

對數(shù)據(jù)結(jié)構(gòu)所帶來的方便進行了一些簡述，這些在當今高級語言中都有所體現(xiàn)较剃。

第4章 編寫正確的程序

本章通過一些證明方法來證明了一個算法的正確性咕别，由于我已經(jīng)在《算法導(dǎo)論》里面飽受了數(shù)學(xué)的折磨了，這張直接跳過了写穴，完全看不懂惰拱。

本章還介紹了一種用于檢驗程序正確性的方法，斷言(assertion)或者叫不變式(invariant)啊送。由于輸入弓颈、程序變量和輸出之間的關(guān)系勾勒出了程序的“狀態(tài)”，斷言使得程序猿可以準確闡述這些關(guān)系删掀。

第5章 編程小事

本章寫了一些測試的方法翔冀，不過都是手動進行測試。毋庸置疑披泪，測試在編程中絕不是小事纤子，特別是大型項目的開發(fā)，作者以小見大款票，說明了測試對于系統(tǒng)的穩(wěn)定性和優(yōu)化所帶來的重大影響控硼。

第二部分 性能

第6章 程序性能分析

從設(shè)計層面將程序性分為了幾個方面：問題定義、系統(tǒng)結(jié)構(gòu)艾少、算法和數(shù)據(jù)結(jié)構(gòu)卡乾、代碼調(diào)優(yōu)、系統(tǒng)軟件缚够、硬件幔妨。也有一個簡單的分析方法就是看算法的復(fù)雜度鹦赎，用O來表示那種。

第7章 粗略估算

本章使用生活中大量的例子來描述如何進行粗略估算误堡，最近正好在看《蝎子網(wǎng)絡(luò)》古话，發(fā)現(xiàn)我的數(shù)學(xué)功底越來越差，實際生活中有大量的使用估算的地方锁施，比如陪踩，驗證一些生活常識、驗證一些新聞的正確性等悉抵。日常生活中的速算肩狂。

粗略估算的一些基本技巧：快速檢驗、經(jīng)驗法則(72法則)姥饰。還有一些估算定律：Little定律(隊列中物體的平均數(shù)量為進入速率與平均停留時間的乘積傻谁。)

第8章 算法設(shè)計的技術(shù)

本章主要講述了分治算法，這一算法我曾在算法導(dǎo)論上看過媳否。

本章還介紹了幾個重要的算法設(shè)計技術(shù)：保存狀態(tài)栅螟，避免重復(fù)計算；將信息預(yù)處理至數(shù)據(jù)結(jié)構(gòu)中篱竭；分治算法力图；掃描算法；累計掺逼；下界吃媒。

第9章 代碼調(diào)優(yōu)

本章介紹了優(yōu)化代碼的一些簡單的思想和方法。例如將最常見類型的空閑記錄緩存在一個鏈表中吕喘。然后赘那，就可以通過對該鏈表的快速訪問來處理常見的請求，而不必調(diào)用通用的內(nèi)存分配程序氯质。恰當使用函數(shù)募舟、宏和內(nèi)聯(lián)代碼。

”代碼調(diào)優(yōu)的最重要的原理就是盡量少用它.“

第十章 節(jié)省空間

Unix操作系統(tǒng)發(fā)明者(Dennis Ritchie和Ken Thompson)在論文中說道：“在系統(tǒng)及其軟件方面闻察，總是存在著相當嚴重的空間約束拱礁。如果同時對合理的效率和強大的能力提出要求，那么空間約束不僅具有經(jīng)濟上的意義辕漂，還會使設(shè)計更優(yōu)雅一些呢灶。”

其實節(jié)省空間在所有地方都可以看到钉嘹，比如在最初定義一個整數(shù)位數(shù)的時候鸯乃，我一直使用的是int，但是如果要節(jié)約空間就使用其他的一些分配方法跋涣。

hash(散列表)特別適合某些稀疏場合缨睡。

如果一定要消耗時間來節(jié)省空間鸟悴，在有些變量的計算上選擇不存儲，重新計算的方法更有效宏蛉。在給變量分配內(nèi)存時就使用動態(tài)分配遣臼。

第三部分 應(yīng)用

第11章 排序

作者通過自己對快速排序的幾種方法的改進超越了庫函數(shù)性置。就像其他任何強大的工具一樣拾并，我們經(jīng)常會在不該使用排序的時候使用排序，而在應(yīng)該使用排序的時候卻不使用排序鹏浅。

第12章 取樣問題

研究的一個問題就是輸出隨機數(shù)嗅义，雖然很多語言都提供了類似的隨機函數(shù)，但是感覺目前大多數(shù)語言隐砸，特別是傳統(tǒng)語言的隨機幾乎都無法做到真隨機之碗，必須自己在假隨機上進行修改。

第13章：搜索

線性結(jié)構(gòu)季希；二分搜索數(shù)褪那。并提到了庫的作用，C++標準模庫提供了一個實現(xiàn)起來很容易式塌，并且維護和擴展也比較簡單的通用解決方案博敬。當遇到涉及數(shù)據(jù)結(jié)構(gòu)的問題時，我們的第一反應(yīng)應(yīng)該是尋求解決問題的通用工具峰尝。當然偏窝，有些時候針對特定的問題，使用專用的算法可能會大大提高運行速度武学。我們還要使用代碼調(diào)優(yōu)方法祭往，比如將遞歸函數(shù)重寫為迭代版本可以使鏈表的速度提升為原來的3倍，對大多數(shù)結(jié)構(gòu)來說火窒，引入哨兵可以獲得清晰硼补、簡單的代碼，并縮短運行時間熏矿。

第14章：堆

堆其實也是一種二叉樹已骇，但其有兩個不同的性質(zhì)：一是順序性，任何結(jié)點的值都小于或等于其子結(jié)點的值曲掰。第二個性質(zhì)就是形狀疾捍，不是完整的三角形，右下角可以缺一點栏妖。

第15章：字符串

通過單詞乱豆、短語和文本幾個方面來處理字符串

《編程珠璣》(續(xù))

第一部分 編程技術(shù)

第1章 性能監(jiān)視工具

通過一些常用的代碼性能監(jiān)視工具，如行計數(shù)性能監(jiān)視吊趾、過程時間性能監(jiān)視等可以查看到一個程序里面各條語句的執(zhí)行情況宛裕，以查找代碼中執(zhí)行最慢的地方瑟啃，因為“一個程序中不到4%的語句通常占用了一半以上的運行時間”。我們最應(yīng)該優(yōu)化的就是這個地方揩尸。

第2章 關(guān)聯(lián)數(shù)組

貌似本書很多章都是使用的Awk來講解蛹屿，但是Awk中的關(guān)聯(lián)數(shù)組，我感覺就很像其他腳本語言中的字典岩榆，十分方便错负，但awk對字符串的處理可能更加方便，不過我是不喜歡其編碼風(fēng)格的勇边。

第3章 程序猿的懺悔

再次提到調(diào)試腳手架的重要性犹撒，這一點上，Awk語言確實能起到很大的幫助粒褒，“Awk是一種構(gòu)造算法原型的很好的語言识颊，其內(nèi)聯(lián)數(shù)組使你模擬許多常用的數(shù)組結(jié)構(gòu)，它的字段奕坟、隱式循環(huán)祥款、模式-動作對等設(shè)計極大地簡化了輸入輸出過程，隱式的變量聲明和初始化也使得程序更加簡潔月杉∪絮耍”。正如Fred Brooks認為“一個軟件產(chǎn)品中應(yīng)該有一半的代碼都是腳手架”沙合。

第4章 自描述數(shù)據(jù)

作者是使用的文檔生成器來描述奠伪，其實本章所說的自描述數(shù)據(jù)在某種意義上類似于其他語言的一種模版，比如留下%s等占位符首懈，讓其他變量來填充绊率。

第二部分 實用技巧

第5章 劈開戈爾迪之結(jié)

背景：在古希臘神話中，能解開戈爾迪之結(jié)者就可以當亞細亞之王究履，幾百年后亞歷山大大帝來了滤否。他沒有重蹈覆轍，而是拔出劍來最仑，將結(jié)直接劈開藐俺，隨即征服了亞洲。從那時起泥彤，“劈開戈爾迪之結(jié)”意味著為復(fù)雜問題找出聰明的解法欲芹。

我們在尋找解決問題的方法的需要考慮如下幾個問題：什么是用戶真正的需求(用戶要求可預(yù)測性甚于要求速度)；考慮成本與收益的平衡吟吝；別把問題弄得太復(fù)雜也別太簡單菱父；用正確的方法使用正確的工具；對員工的獎賞。浙宜。官辽。

簡單的方法誰都想要，但并不是每個人都能找得到粟瞬，我們還應(yīng)該考慮時間成本同仆，別花過多時間去思考簡單的方法，沒準一個你目前覺得復(fù)雜的方法可以很快完成項目裙品。

第6章 計算機科學(xué)箴言集

居然把一些計算機的箴言單獨列為一章俗批，我也是醉了。

第7章 粗略估算

在原書已經(jīng)有了幾乎一樣的內(nèi)容...

第8章 人員備忘錄

大神清酥，這是你自己的日記嗎扶镀？

第三部分 人性化I/O

第9章 小語言

作者以Pic為例子講解了一種小的語言是如何運行起來的蕴侣，相信看過編譯原理的同學(xué)都能理解焰轻。

第10章 文檔設(shè)計

原以為是要教我們關(guān)于PRD這樣的文檔的寫法，不過只是教了我們一些寫Word文檔的基本的規(guī)則昆雀，不過我覺得一個有基本審美觀的人無論怎么寫也不會寫得很差的辱志。

第11章 圖形化輸出

合理使用圖形工具。

第12章 對調(diào)查的研究

也是借調(diào)查這一事件來強調(diào)模版的好處狞膘。

第四部分 算法

第13章 絕妙的取樣

好吧揩懒，就是隨機數(shù)的一些個問題。

第14章 編寫數(shù)值計算程序

牛頓迭代挽封，這個我倒是完全理解已球。本章學(xué)到重要的一點就是“在特殊的上下文環(huán)境中針對特殊目的設(shè)計的代碼比通用的程序更有效”。

第15章 選擇

使用分治算法來進行選擇辅愿，太聰明了智亮。