高級算法和數據結構 Advanced Algorithms and Data Structures

這是一本關於“高級/進階”算法和數據結構的圖書，主要介紹了用於Web應用程序、系統編程和數據處理領域的各種算法，旨在讓讀者瞭解如何用這些算法應對各種棘手的編碼挑戰，以及如何將其應用於具體問題，以應對新技術浪潮下的“棘手”問題。

本書對一些廣為人知的基本算法進行了擴展，還介紹了用於改善優先隊列、有效緩存、對數據進行集群等的技術，以期讀者能針對不同編程問題選出更好的解決方案。書中示例大多輔以圖解，並以不囿於特定語言的偽代碼以及多種語言的代碼樣本加以閘釋。

學完本書，讀者可以瞭解高級算法和數據結構的相關內容，並能運用這些知識讓代碼具備更優性能，甚至能夠獨立設計數據結構，應對需要自定義解決方案的情況。

本書可作為高等院校電腦相關專業本科高年級學生以及研究生的學慣用書，也可供從事與算法相關工作的開發者參考。

Marcello La Rocca现为一家电商公司的高级软件工程师，曾参与开发Twitter、微软和苹果等公司的大型Web应用程序和数据基础设施，并发明了NeatSort这一自适应排序算法。他的主要研究领域为图、算法优化、机器学习和量子计算。

第 1章　初識數據結構　1

1.1　數據結構　2

1.1.1　定義數據結構　2

1.1.2　描述數據結構　3

1.1.3　算法與數據結構有區別嗎　4

1.2　設定目標：閱讀本書後的期望　4

1.3　打包背包：數據結構與現實世界的結合　5

1.3.1　抽象化問題　5

1.3.2　尋找解決方案　6

1.3.3　拯救大家的算法　7

1.3.4　打破常規來思考問題　8

1.3.5　完美的結局　9

1.4　小結　9

第 一部分　改進基本數據結構

第 2章　改進優先隊列：d叉堆　12

2.1　本章結構　13

2.2　問題：處理優先級　13

2.3　已知解決方案：讓列表保持有序　15

2.4　描述數據結構API：優先隊列　15

2.4.1　使用優先隊列　16

2.4.2　優先級為何非常重要　17

2.5　具體數據結構　17

2.5.1　性能比較　18

2.5.2　正確的具體數據結構是什麽　18

2.5.3　堆　18

2.5.4　優先級、最小堆和最大堆　20

2.5.5　高級變體：d叉堆　21

2.6　如何實現堆　22

2.6.1　向上冒泡　22

2.6.2　向下推動　25

2.6.3　插入　27

2.6.4　移除頂部元素　28

2.6.5　修改　30

2.6.6　處理重復優先級　31

2.6.7　堆化　32

2.6.8　API之外的方法：包含　34

2.6.9　性能回顧　34

2.6.10　從偽代碼到實現　35

2.7　用例：找到最大的k個元素　35

2.7.1　選擇正確的數據結構　36

2.7.2　正確地使用數據結構　36

2.7.3　代碼寫起來　36

2.8　更多的用例　37

2.8.1　圖中的最小距離：Dijkstra算法　37

2.8.2　更多的圖算法：Prim算法　37

2.8.3　數據壓縮：霍夫曼編碼　38

2.9　對分支因子進行分析　41

2.9.1　是否需要d叉堆　41

2.9.2　運行時間　42

2.9.3　尋找最佳分支因子　42

2.9.4　分支因子與內存的關系　43

2.10　性能分析：尋找最佳分支因子　43

2.10.1　剖析　44

2.10.2　解釋結果　45

2.10.3　堆化的謎團　49

2.10.4　選擇最佳分支因子　49

2.11　小結　50

第3章　樹堆：使用隨機化來平衡二叉搜索樹　52

3.1　問題：多索引　53

3.2　解決方案：描述與API　53

3.3　樹堆　54

3.3.1　旋轉　57

3.3.2　一些設計問題　60

3.3.3　實現搜索方法　61

3.3.4　插入　61

3.3.5　刪除　64

3.3.6　去頂、看頂以及修改　66

3.3.7　返回最小鍵和最大鍵　67

3.3.8　性能回顧　67

3.4　應用：隨機樹堆　68

3.4.1　平衡樹　68

3.4.2　引入隨機化　70

3.4.3　隨機樹堆的應用　71

3.5　性能分析和剖析　72

3.5.1　理論：期望高度　72

3.5.2　剖析高度　74

3.5.3　剖析運行時間　76

3.5.4　剖析內存使用情況　78

3.5.5　結論　78

3.6　小結　80

第4章　布隆過濾器：減少跟蹤內容所需的內存　81

4.1　字典問題：跟蹤事物　82

4.2　實現字典的其他方法　83

4.3　描述數據結構API：關聯數組　83

4.4　具體數據結構　84

4.4.1　無序數組：快速插入，慢速搜索　84

4.4.2　有序數組和二分查找：慢插入，稍微快一些的搜索　85

4.4.3　哈希表：在不需要有序的情況下，具有平均常數時間的性能　86

4.4.4　二叉搜索樹：所有操作都是對數階的　86

4.4.5　布隆過濾器：與哈希表一樣快，但（由於一個缺陷而）更節省內存　88

4.5　錶面之下：布隆過濾器是如何工作的　88

4.6　實現　89

4.6.1　使用布隆過濾器　90

4.6.2　位的讀取和寫入　91

4.6.3　找到鍵存儲的位置　92

4.6.4　生成哈希函數　93

4.6.5　構造函數　93

4.6.6　查找鍵　94

4.6.7　存儲鍵　95

4.6.8　估計準確率　96

4.7　應用場景　97

4.7.1　緩存　97

4.7.2　路由　98

4.7.3　爬蟲　98

4.7.4　I/O提取器　98

4.7.5　拼寫檢查器　98

4.7.6　分佈式數據庫和文件系統　99

4.8　為什麽布隆過濾器是可行的　99

4.8.1　為什麽沒有假陰性　100

4.8.2　為什麽有假陽性　100

4.8.3　作為隨機算法的布隆過濾器　101

4.9　性能分析　101

4.9.1　運行時間　101

4.9.2　構造函數　102

4.9.3　存儲元素　102

4.9.4　查找元素　102

4.10　估計布隆過濾器的精確度　102

4.11　改進的變體　106

4.11.1　布隆表過濾器　106

4.11.2　組合布隆過濾器　106

4.11.3　分層布隆過濾器　106

4.11.4　壓縮布隆過濾器　107

4.11.5　可擴展佈隆過濾器　107

4.12　小結　108

第5章　不交集：次線性時間的處理過程　109

5.1　不同子集問題　110

5.2　解決方案的論證　111

5.3　描述數據結構API：不交集　112

5.4　簡單解決方案　113

5.5　使用樹狀結構　117

5.5.1　從鏈表轉移到樹　117

5.5.2　實現使用樹的版本　118

5.6　改進運行時間的啟發式算法　120

5.6.1　路徑壓縮　121

5.6.2　實現平衡性與路徑壓縮　122

5.7　應用程序　124

5.7.1　圖：連通分量　124

5.7.2　圖：最小生成樹的Kruskal算法　124

5.7.3　聚類　125

5.7.4　合一　126

5.8　小結　126

第6章　trie與基數樹：高效的字符串搜索　127

6.1　拼寫檢查　128

6.1.1　拼寫檢查器的設計　128

6.1.2　壓縮是關鍵　129

6.1.3　描述與API　129

6.2　trie　130

6.2.1　為什麽trie更好　132

6.2.2　搜索　134

6.2.3　插入　137

6.2.4　刪除　139

6.2.5　搜索最長前綴詞　140

6.2.6　返回匹配特定前綴的所有鍵　141

6.2.7　什麽時候應該使用trie　143

6.3　基數樹　144

6.3.1　節點和邊　146

6.3.2　搜索　148

6.3.3　插入　149

6.3.4　刪除　151

6.3.5　搜索最長前綴詞　153

6.3.6　返回匹配特定前綴的所有鍵　153

6.4　應用程序　154

6.4.1　拼寫檢查器　154

6.4.2　字符串相似度　156

6.4.3　字符串排序　157

6.4.4　T9　157

6.4.5　自動完成　158

6.5　小結　158

第7章　用例：LRU緩存　160

7.1　不要重復計算　160

7.2　第 一次嘗試：記住數據　163

7.2.1　描述與API　164

7.2.2　請保存新數據　164

7.2.3　處理異步調用　165

7.2.4　將緩存的值標記為“正在加載”　166

7.3　內存（真的）不夠　167

7.4　清除陳舊數據：LRU緩存　168

7.4.1　有時必須要重復解決問題　169

7.4.2　時間排序　170

7.4.3　性能　174

7.5　當新數據更有價值時：LFU　175

7.5.1　如何選擇緩存的清除策略　176

7.5.2　LFU緩存有什麽不同　176

7.5.3　性能　178

7.5.4　LFU緩存的不足　178

7.6　如何使用緩存也同樣重要　179

7.7　同步簡介　180

7.7.1　（在Java中）解決並發問題　182

7.7.2　鎖簡介　183

7.7.3　獲取鎖　183

7.7.4　重入鎖　184

7.7.5　讀鎖　185

7.7.6　解決並發的其他方法　186

7.8　緩存應用程序　186

7.9　小結　187

第二部分　多維查詢

第8章　最近鄰搜索　190

8.1　最近鄰搜索問題　190

8.2　解決方案　191

8.2.1　第 一次嘗試　191

8.2.2　有時緩存並不是答案　191

8.2.3　簡化事情以獲得靈感　192

8.2.4　謹慎選擇數據結構　193

8.3　描述與API　194

8.4　遷移到k維空間　195

8.4.1　一維二分查找　196

8.4.2　遷移到更高維度　196

8.4.3　用數據結構對二維空間進行建模　197

8.5　小結　198

第9章　k-d樹：索引多維數據　199

9.1　從結束的地方繼續　199

9.2　遷移到k維空間：循環遍歷

維度　199

9.2.1　構造BST　201

9.2.2　不變量　204

9.2.3　保持平衡的重要性　204

9.3　方法　205

9.3.1　搜索　206

9.3.2　插入　208

9.3.3　平衡樹　209

9.3.4　刪除　212

9.3.5　最近鄰搜索　218

9.3.6　區域搜索　224

9.3.7　所有方法的回顧　227

9.4　限制與可能的改進　228

9.5　小結　229

第 10章　相似性搜索樹：圖像檢索的近似

最近鄰搜索　230

10.1　從結束的地方繼續　230

10.1.1　一個新的（更復雜的）例子　231

10.1.2　剋服k-d樹的缺陷　232

10.2　R樹　232

10.2.1　先退一步：B樹簡介　232

10.2.2　由B樹到R樹　233

10.2.3　在R樹中插入點　236

10.2.4　搜索　237

10.3　SS樹　238

10.3.1　搜索　241

10.3.2　插入　244

10.3.3　插入：方差、均值與投影　249

10.3.4　插入：分裂節點　252

10.3.5　刪除　255

10.4　相似性搜索　259

10.4.1　最近鄰搜索　260

10.4.2　區域搜索　262

10.4.3　近似相似性搜索　263

10.5　SS+樹　265

10.5.1　SS樹會更好嗎　266

10.5.2　緩解超球體的限制　267

10.5.3　改進拆分啟發式算法　267

10.5.4　減少重疊　268

10.6　小結　270

第 11章　最近鄰搜索的應用　271

11.1　應用程序：查找最近的樞紐　271

11.1.1　解決方案的初稿　272

11.1.2　天堂里的麻煩　273

11.2　中心化應用程序　274

11.2.1　過濾點　274

11.2.2　復雜的決定　276

11.3　遷移到分佈式應用程序　278

11.3.1　處理HTTP通信的問題　279

11.3.2　保持庫存同步　281

11.3.3　經驗教訓　281

11.4　其他應用程序　282

11.4.1　色彩還原　282

11.4.2　粒子的相互作用　283

11.4.3　多維數據庫查詢的優化　285

11.4.4　聚類　287

11.5　小結　287

第 12章　聚類　288

12.1　聚類簡介　289

12.1.1　機器學習的類型　289

12.1.2　聚類的類型　290

12.2　k均值算法　291

12.2.1　k均值算法的問題　295

12.2.2　維度詛咒再次來襲　296

12.2.3　k均值算法的性能分析　297

12.2.4　用k-d樹來加快k均值算法　297

12.2.5　關於k均值算法的最後一些提示　300

12.3　DBSCAN算法　300

12.3.1　直接可達與密度可達　301

12.3.2　從定義到算法　302

12.3.3　實現　304

12.3.4　DBSCAN算法的優缺點　305

12.4　OPTICS算法　307

12.4.1　定義　308

12.4.2　OPTICS算法的核心思想　308

12.4.3　從可達距離到聚類　311

12.4.4　分層聚類　314

12.4.5　性能分析和最終的考慮　318

12.5　評估聚類結果：評估指標　318

12.6　小結　322

第 13章　並行聚類：MapReduce與樹冠聚類　323

13.1　並行化　323

13.1.1　並行計算與分佈式計算　324

13.1.2　並行化k均值算法　325

13.1.3　樹冠聚類　325

13.1.4　應用樹冠聚類　327

13.2　MapReduce　328

13.2.1　MapReduce是如何工作的　328

13.2.2　先映射，後歸約　331

13.2.3　錶面之下，還有更多　334

13.3　MapReduce版本的k均值算法　334

13.3.1　並行化樹冠聚類　337

13.3.2　使用樹冠聚類來進行質心的初始化　339

13.3.3　MapReduce版本的樹冠聚類　340

13.4　MapReduce版本的DBSCAN 算法　343

13.5　小結　348

 

第三部分　平面圖與最小交叉數

第 14章　圖簡介：尋找距離最短的

路徑　350

14.1　定義　351

14.1.1　圖的實現　351

14.1.2　作為代數類型的圖　353

14.1.3　偽代碼　354

14.2　圖的屬性　354

14.2.1　無向　355

14.2.2　連通　355

14.2.3　無環　356

14.3　圖的遍歷：BFS與DFS　357

14.3.1　優化配送路線　357

14.3.2　廣度優先搜索　359

14.3.3　重建到目標的路徑　361

14.3.4　深度優先搜索　362

14.3.5　再次比較隊列與堆棧　364

14.3.6　投遞包裹的最佳路線　365

14.4　加權圖中的最短路徑：迪傑斯特拉 算法　365

14.4.1　與BFS算法的區別　366

14.4.2　實現　367

14.4.3　分析　368

14.4.4　投遞包裹的最佳路線　369

14.5　超越迪傑斯特拉算法：A*

算法　370

14.5.1　A*算法到底有多好　372

14.5.2　將啟發式函數作為平衡實時數據的一種方式　375

14.6　小結　376

第 15章　圖嵌入與平面性：繪制具有最少相交邊的圖　377

15.1　圖嵌入　378

15.1.1　一些基礎定義　379

15.1.2　完全圖與完全二分圖　380

15.2　平面圖　381

15.2.1　在實踐中使用庫拉托夫斯基定理　381

15.2.2　平面性測試　382

15.2.3　用於平面性測試的樸素算法　383

15.2.4　提高性能　386

15.2.5　高效的算法　388

15.3　非平面圖　389

15.3.1　找到交叉數　391

15.3.2　直線交叉數　392

15.4　邊的交叉點　393

15.4.1　直線線段　394

15.4.2　折線　397

15.4.3　貝塞爾曲線　397

15.4.4　二次貝塞爾曲線之間的交點　398

15.4.5　頂點與頂點相交以及邊與頂點相交　401

15.5　小結　402

第 16章　梯度下降：（不僅是）圖的優化問題　403

16.1　用於交叉數的啟發式算法　404

16.1.1　剛才提到啟發式了嗎　404

16.1.2　擴展到曲線邊　408

16.2　優化的工作原理　409

16.2.1　成本函數　410

16.2.2　階躍函數與局部最小值　412

16.2.3　優化隨機抽樣算法　412

16.3　梯度下降　414

16.3.1　梯度下降中的數學描述　415

16.3.2　幾何解釋　416

16.3.3　什麽時候可以應用梯度下降　418

16.3.4　梯度下降的問題　418

16.4　梯度下降的應用　419

16.5　使用梯度下降進行圖嵌入　422

16.5.1　另一種標準　423

16.5.2　實現　425

16.6　小結　426

第 17章　模擬退火：超越局部最小值的優化　427

17.1　模擬退火　428

17.1.1　有時候需要先向上爬才能到達底部　429

17.1.2　實現　431

17.1.3　為什麽模擬退火是有效的　432

17.1.4　短程與長程的轉換　434

17.1.5　變體　435

17.1.6　模擬退火與梯度下降：應該選擇哪一個呢　436

17.2　模擬退火與旅行推銷員　436

17.2.1　精確解與近似解　438

17.2.2　可視化成本　438

17.2.3　修剪域　440

17.2.4　狀態轉換　440

17.2.5　相鄰交換與隨機交換　443

17.2.6　TSP近似算法的應用　444

17.3　模擬退火與圖嵌入　444

17.3.1　最小邊交叉　445

17.3.2　力導向繪制　446

17.4　小結　450

第 18章　遺傳算法：受生物學啟發的快速收斂優化　451

18.1　遺傳算法簡介　451

18.1.1　來自大自然的靈感　453

18.1.2　染色體　456

18.1.3　種群　457

18.1.4　適應度　458

18.1.5　自然選擇　459

18.1.6　選擇交配的個體　461

18.1.7　交叉操作　466

18.1.8　突變操作　468

18.1.9　遺傳算法模板　469

18.1.10　遺傳算法在什麽時候效果最好　470

18.2　TSP　471

18.2.1　適應度、染色體與初始化　471

18.2.2　突變操作　472

18.2.3　交叉操作　472

18.2.4　結果與參數調整　473

18.2.5　超越TSP：優化整個車隊的路線　476

18.3　最小頂點覆蓋　477

18.3.1　頂點覆蓋的應用　478

18.3.2　實現遺傳算法　478

18.4　遺傳算法的其他應用　480

18.4.1　最大流問題　480

18.4.2　蛋白質折疊　481

18.4.3　超越遺傳算法　482

18.4.4　算法，超越本書　483

18.5　小結　483

附錄A　偽代碼快速指南　485

附錄B　大O符號　494

附錄C　核心數據結構　500

附錄D　類似於優先隊列的容器　511

附錄E　遞歸　514

附錄F　分類問題與隨機算法的度量指標　520