資訊專欄INFORMATION COLUMN
摘要：除特別標(biāo)注外，文章非原創(chuàng)插圖全部來(lái)自課程相關(guān)資源。劇透預(yù)警內(nèi)容包含大作業(yè)的關(guān)鍵問(wèn)題解法分析。為的返回值此方案下，判斷只需要對(duì)應(yīng)，判斷使用結(jié)果準(zhǔn)確，判斷檢測(cè)的對(duì)應(yīng)是否為。更新此方法已確定違反的。
Princeton的算法課是目前為止我上過(guò)的最酣暢淋漓的一門課，得師如此夫復(fù)何求，在自己的記憶徹底模糊前，愿對(duì)這其中一些印象深刻的點(diǎn)做一次完整的整理和回顧，以表敬意。
注：
這是一篇更關(guān)注個(gè)人努力與完成任務(wù)項(xiàng)目過(guò)程相關(guān)的文章，內(nèi)容集中于課程背后值得提到的部分，不會(huì)介紹課程基本信息及學(xué)習(xí)時(shí)必讀的設(shè)定要求等部分，敬請(qǐng)諒解。
在學(xué)習(xí)一門課程的時(shí)候考慮為什么這么教是個(gè)人習(xí)慣，我會(huì)嘗試給出一些解讀，為什么這門課這么屌(awesome)。
優(yōu)化無(wú)止境，越學(xué)習(xí)才能越深刻地感受自己的無(wú)知，即使是作業(yè)內(nèi)已提到的額外內(nèi)容我也并沒(méi)有一一探究完整，這里只是謙卑地盡力記錄自己的努力，并無(wú)意與誰(shuí)比較，如有新的進(jìn)展還會(huì)回來(lái)更新。
除特別標(biāo)注外，文章非原創(chuàng)插圖全部來(lái)自課程相關(guān)資源。
每一小節(jié)的作業(yè)題目鏈接到specification，“√”鏈接到checklist，“〇”鏈接到code下載。
這里提供一個(gè)全文完整的資源樹。
劇透預(yù)警：
內(nèi)容包含大作業(yè)的關(guān)鍵問(wèn)題解法分析。
作為第一部分開學(xué)第一課，作業(yè)Percolation可謂精妙：
既沒(méi)有復(fù)雜的語(yǔ)法使用（僅數(shù)組操作），又著實(shí)比在基礎(chǔ)語(yǔ)言層面上升了一個(gè)檔次；
漂亮的visualizer動(dòng)畫效果激勵(lì)著初學(xué)者完成任務(wù)；
強(qiáng)大的autograder功能初次展現(xiàn)，評(píng)價(jià)算法的主要管道一目了然，每一微秒每一字節(jié)都很重要；
針對(duì)學(xué)習(xí)迅速的同學(xué)還隱含了一個(gè)很大的挑戰(zhàn)：在僅使用一個(gè)WeightedQuickUnionUF對(duì)象的前提下，解決backwash問(wèn)題。
下面主要聊聊backwash：
問(wèn)題的核心源自virtual top/bottom，一個(gè)強(qiáng)行被導(dǎo)師在課程視頻中提到的優(yōu)化方法，于是天真的同學(xué)們（我）就去開心地實(shí)現(xiàn)這個(gè)看似無(wú)辜而又性能楚楚動(dòng)人的方法，卻毫不了解導(dǎo)師在下一節(jié)中馬上提出的backwash問(wèn)題是何物，還覺(jué)得這種低級(jí)錯(cuò)誤怎么可能會(huì)發(fā)生：
java-algs4 PercolationVisualizer percolation/input10.txt
……
（我發(fā)誓這就是我看到的東西……）
把痛碎的心小心拼回，認(rèn)真思索一番后確定問(wèn)題根源出在virtual bottom，一個(gè)顯而易見(jiàn)的解決方案便浮現(xiàn)在眼前：使用兩個(gè)UF，一個(gè)使用vb一個(gè)不用，判斷percolate用前者，判斷full用后者，解決！
Raw Score 100.00 / 100.00
然而checklist的一句話又引起了我的注意：
However, many students consider this to be the most challenging and creative part of the assignment (especially if you limit yourself to one union-find object).
加上autograder特別溫馨的提醒“bonus failed”，我不得不重新開始審視這個(gè)問(wèn)題。
后來(lái)的事實(shí)證明，直到課程結(jié)束沒(méi)有一個(gè)問(wèn)題再讓我如此頭疼。經(jīng)過(guò)了一段可謂長(zhǎng)征式的思考，加之在forum的討論中得到了一點(diǎn)靈感(多加利用Find())，最終形成并實(shí)現(xiàn)了解決方案，方案核心如下（corner case另行處理）：
將原方案中表示open狀態(tài)的boolean數(shù)組改為byte數(shù)組，設(shè)定規(guī)則如下：初始化的默認(rèn)值0代表blocked site，賦1代表open site，賦2代表與尾行相連的open site；
每open一個(gè)site，如果位于尾行則賦2，否則賦1；
分別對(duì)每個(gè)鄰接site檢測(cè)：如任何一方的root site對(duì)應(yīng)byte值為2，將雙方Union后的root site設(shè)為2。（root為Find()的返回值）
此方案下，判斷open只需要對(duì)應(yīng)byte>0，判斷full使用UF結(jié)果準(zhǔn)確，判斷percolates檢測(cè)virtual top的root site對(duì)應(yīng)byte是否為2。
Raw Score 101.25 / 100.00
Test 2 (bonus): Check that total memory <= 11 N^2 + 128 N + 1024 bytes
==> passed
對(duì)這個(gè)作業(yè)來(lái)說(shuō)，上面這三行的成績(jī)凝聚了太多。
II. Resizing Array & Linked Lists與Randomized Queues and Deques √ 〇第二周課程正式展開，但在作業(yè)深度上相對(duì)稍有下降，根據(jù)指定的性能和API要求，選擇適當(dāng)?shù)膶?shí)現(xiàn)方式（動(dòng)態(tài)數(shù)組、單、雙向鏈表），實(shí)現(xiàn)Randomized Queue和Deque，主要訓(xùn)練基本的算法分析和編程嚴(yán)謹(jǐn)性（完善處理corner-case），但并無(wú)特別的難點(diǎn)。有兩個(gè)小技巧可以提出：鏈表可使用sentinel node(s)使代碼更簡(jiǎn)潔（checklist已提），寫client時(shí)可先shuffle再插入(bonus)。
2018更新：最近同學(xué)在做這道題時(shí)發(fā)現(xiàn)autograder已明確指出不可以使用數(shù)組，這就使得這個(gè)bonus變得有趣多了：
仔細(xì)想一下，既然API已經(jīng)把我們非常嚴(yán)格地限制在只能遍歷一遍輸入的情況下，而我們?nèi)匀幌Ｍ鸕Q不超過(guò)k個(gè)元素，那么在正常讀入k個(gè)元素后面對(duì)下一個(gè)元素我們只有兩個(gè)選擇，dequeue一個(gè)舊元素然后enqueue新元素，或直接忽略這個(gè)新元素；所以問(wèn)題的關(guān)鍵就變成了一個(gè)概率問(wèn)題，兩個(gè)選擇應(yīng)當(dāng)如何權(quán)衡，才能保證每個(gè)元素最終留在RQ中的概率相等呢？
相對(duì)應(yīng)地，autograder也有完整的假設(shè)檢驗(yàn)(t-test)來(lái)實(shí)際檢測(cè)，小伙子你真的做對(duì)了嗎？
不必多說(shuō)，擼起袖子上吧，撿起高中的排列組合知識(shí)，仔細(xì)分析一下，你算出的忽略當(dāng)前新元素的概率應(yīng)該是這樣：
$$mathrm{P}_{discard}=frac{mathrm{C}_{n-1}^k}{mathrm{C}_n^k}=frac{n-k}{n}$$
plug it in and feel the magic! 不得不說(shuō)這個(gè)作業(yè)的設(shè)計(jì)之精巧，看似非常不起眼的一個(gè)小bonus，竟然也幾乎是蘊(yùn)含著Monte Carlo方法的一些基礎(chǔ)啟發(fā)，真是妙啊。
過(guò)程中一并學(xué)習(xí)了Java的Generics，Iterable，Iterator概念，在大學(xué)課程部分已學(xué)習(xí)掌握得比較熟練，可不談，the result speaks：
Raw Score 100.19 / 100.00
Test 3 (bonus): Check that maximum size of any or Deque or RandomizedQueue object created is <= k
==> passed
結(jié)合兩次作業(yè)特性，可看出一些值得一提的點(diǎn)：
作業(yè)任務(wù)要求與說(shuō)明往往面面俱到細(xì)致入微，在給定公有API框架及其對(duì)應(yīng)時(shí)間空間復(fù)雜度的基礎(chǔ)上，結(jié)合課程視頻知識(shí)內(nèi)容，這種“受指導(dǎo)”的編程過(guò)程變得十分清晰，尤其是其中API的設(shè)計(jì)，風(fēng)格簡(jiǎn)潔高效到自成一家，我認(rèn)可自己的代碼風(fēng)格已很簡(jiǎn)潔，而algs4.jar讓我第一次看到了更高；
給定充足的測(cè)試材料，包括各類corner-case或相對(duì)有趣的輸入數(shù)據(jù)（如sedgewick60.txt），及合適情況下生動(dòng)的可視化工具（如PercolationVisualizer.java），都使得學(xué)生可以全力，高效，有動(dòng)力地，將精力集中在核心算法本身上。
III. Sorting與Pattern Recognition - Collinear Points √ 〇本周的課程介紹了兩大經(jīng)典排序：Mergesort和Quicksort，自然作業(yè)也與sorting緊密相關(guān)。Collinear Points（找出所有4個(gè)或以上共線的點(diǎn)構(gòu)成的點(diǎn)集）是第一個(gè)在運(yùn)行時(shí)見(jiàn)證“好的算法”與“暴力算法”直觀差別的作業(yè)，這樣的對(duì)比能給學(xué)生帶來(lái)深刻的影響：忙了好久，為了什么？
上圖為暴力算法(~N^4)求解100個(gè)數(shù)據(jù)點(diǎn)(input100.txt)，下圖為基于排序的算法(~N^2logN)求解1423個(gè)數(shù)據(jù)點(diǎn)(rs1423.txt)
測(cè)試數(shù)據(jù)還有很多。圖中示例對(duì)快速算法給定數(shù)據(jù)量龐大了不止10倍，運(yùn)行時(shí)間卻與不到1/10數(shù)據(jù)量下的暴力算法接近；對(duì)上圖數(shù)據(jù)，快速算法基本看不到找線的動(dòng)畫過(guò)程就完成了；對(duì)下圖數(shù)據(jù)，暴力算法在可以忍受的時(shí)間里基本找不到幾條線。
這樣的運(yùn)行結(jié)果可以給學(xué)生一種非常好的對(duì)自己努力的掌控感，正是這樣一個(gè)個(gè)美妙的瞬間使學(xué)生能以最好的狀態(tài)與飽滿的好奇心在算法之路上繼續(xù)走下去。
作業(yè)說(shuō)明中對(duì)核心算法的描述非常清晰，應(yīng)當(dāng)特別小心的技術(shù)點(diǎn)（浮點(diǎn)誤差、正負(fù)零等等）也都在checklist中予以強(qiáng)調(diào)，因而實(shí)現(xiàn)難度不算很大，其中使用了Java的Comparable與Comparator，排序過(guò)程調(diào)用Arrays.sort()，詳細(xì)思考問(wèn)題理清關(guān)系后，實(shí)現(xiàn)非常自然，前提是編程基本功必須扎實(shí)。
值得提到的點(diǎn)：
checklist鼓勵(lì)初學(xué)者開始編寫快速算法時(shí)先不要擔(dān)心5個(gè)或以上的點(diǎn)共線的情況，而實(shí)際上對(duì)基本功扎實(shí)的同學(xué)，從開始便考慮這個(gè)問(wèn)題更為合適；
checklist提到compare()和FastCollinearPoints類可以完全避免浮點(diǎn)數(shù)用整形運(yùn)算實(shí)現(xiàn)，我想到的唯一符合要求（Point.java注釋中規(guī)定不得依賴toString()）的方法是，對(duì)Point類的compareTo()方法返回值增加意義（不單純返回正負(fù)1），以獲取兩點(diǎn)的坐標(biāo)之差（因題目給定坐標(biāo)取值范圍0-32767，可在返回值低兩位字節(jié)存儲(chǔ)x坐標(biāo)差， 高兩位字節(jié)存儲(chǔ)y坐標(biāo)差），再利用坐標(biāo)差判斷斜率是否相等。雖依然完全符合題目要求，但已有一點(diǎn)奇技淫巧之嫌，并且不一定能夠通過(guò)autograder（評(píng)分時(shí)會(huì)替換Point類去測(cè)試FastCollinearPoints），不多討論。（更新：此方法已確定違反FastCollinearPoints的API。）
最終實(shí)現(xiàn)版本拿到了100分，未發(fā)現(xiàn)關(guān)于bonus的討論。
IV. Priority Queue與8 Puzzle √ 〇剛剛講解完使用Binary Heap實(shí)現(xiàn)的Priority Queue，便迎來(lái)了這周的8 Puzzle——使用PQ實(shí)現(xiàn)A*解決NP難問(wèn)題，所以——重點(diǎn)在優(yōu)化咯。
(Image Source Here)
左邊是目標(biāo)狀態(tài)，右邊是起始狀態(tài)；對(duì)，就是那個(gè)——小時(shí)候功能手機(jī)上的蒙娜麗莎。
隨著學(xué)習(xí)的深入，這次作業(yè)的復(fù)雜度有了一個(gè)明顯的上升，但這門課最美妙的地方之一也就在這里：面臨的問(wèn)題越來(lái)越復(fù)雜，而導(dǎo)師給出的指導(dǎo)思路依然保持最大程度的簡(jiǎn)潔優(yōu)雅，每一步驟的設(shè)定都直指問(wèn)題核心，并在實(shí)現(xiàn)功能基礎(chǔ)上提供非常豐富的優(yōu)化選擇，以及每個(gè)優(yōu)化會(huì)帶來(lái)的影響分析。
"It"s a funny feeling being took under the wings of a dragon. It"s warmer than you think." —— Gangs of New York
整個(gè)問(wèn)題相對(duì)比較復(fù)雜，但經(jīng)過(guò)給定API的劃分和給定的限制后，問(wèn)題變成了實(shí)現(xiàn)一個(gè)個(gè)目標(biāo)明確的小方法而已，其中最復(fù)雜的不過(guò)是A*的實(shí)現(xiàn)，而周到合理的封裝和PQ的使用也使得這個(gè)過(guò)程無(wú)比自然，在此之前我從未意識(shí)到我可以將A*在如此短小清晰的代碼中實(shí)現(xiàn)：（源碼如此，僅省略了聲明過(guò)程）
while (!pq.min().board.isGoal()) {
cur = pq.delMin();
for (Board nb : cur.board.neighbors()) {
if (cur.prev != null && nb.equals(cur.prev.board)) continue;
pq.insert(new Node(nb, cur.moves+1, cur));
}
}
PQ使用了Manhattan Priority作為Comparator，Node為封裝Board的單鏈表節(jié)點(diǎn)，結(jié)束后獲取最短路徑只需取PQ中最小Node，利用prev指針遍歷。
解決8 Puzzle這一NP難問(wèn)題的核心代碼便完成了。
當(dāng)然，在其余部分還是有不少值得提到的點(diǎn)：
用char[]存儲(chǔ)一個(gè)Board的狀態(tài)比用int[][]好太多，但使用前需要詳細(xì)測(cè)試將char做數(shù)字使用與直接用int的區(qū)別；
Board的equals()方法只需比較char[]構(gòu)成的String即可，早期因圖省事直接比較了toString()的返回值（one-liner），造成了很大的性能損失，最后尋找問(wèn)題來(lái)源也費(fèi)了不少功夫（教訓(xùn)：看似再簡(jiǎn)單的部分也要在腦袋里多轉(zhuǎn)一轉(zhuǎn)再下手，devil in the details，…，you name it）；
Solvability: 這篇文章描述的解決方案應(yīng)為checklist所述方案，但需要脆弱地依賴toString()反推Board內(nèi)容，在本期課程的API設(shè)定中已被明確禁止，要求使用兩個(gè)同步A*的方案解決（最好使用一個(gè)PQ），但未來(lái)session可能會(huì)在兩方案對(duì)應(yīng)API設(shè)定間切換，所以我都實(shí)現(xiàn)了一遍，上面出現(xiàn)的A*代碼來(lái)自文章所述方案；
實(shí)現(xiàn)Priority的cache時(shí)需要稍多做思考，直覺(jué)想到的第一方案是儲(chǔ)存在Node中與A*過(guò)程配合，而這將使A*代碼迅速腫脹，且沒(méi)有很好地利用更多規(guī)律：如checklist所指出，對(duì)相鄰Board每次重新計(jì)算Priority其實(shí)也有很多重復(fù)工作，我的做法是將cache過(guò)程作為Board類一個(gè)私有構(gòu)造函數(shù)，構(gòu)造相鄰Priority只需做對(duì)應(yīng)增量操作即可，以最簡(jiǎn)潔的手段達(dá)到了目的。
我的最終測(cè)試文件及結(jié)果在這里，運(yùn)行于i5-2450 (8G)，結(jié)尾幾個(gè)復(fù)雜的4x4開始因內(nèi)存不足報(bào)錯(cuò)，論壇查到大概需要5-6G超出了我的空閑內(nèi)存，即使要測(cè)也會(huì)用到虛擬內(nèi)存，因而結(jié)果參考意義不大。
對(duì)于這個(gè)作業(yè)，努力的最終匯報(bào)便是，看著終端中puzzle一個(gè)個(gè)被正確解決沾沾自喜，然后到相關(guān)的拓展材料中去體驗(yàn)無(wú)知，發(fā)現(xiàn)更大的世界。
這一周的Balanced Search Trees課程令我印象深刻。在進(jìn)入作業(yè)討論前，我希望先聊聊這次的課程內(nèi)容：
在前一周的課程中就已引入了二叉樹的概念，一個(gè)無(wú)比經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，這我在大學(xué)課程中便已了解到，只是認(rèn)識(shí)非常淺薄，并從未，也從未認(rèn)為我能夠，動(dòng)手實(shí)現(xiàn)過(guò)。
可如果說(shuō)在上一周的學(xué)習(xí)中彌補(bǔ)了我的這個(gè)問(wèn)題，對(duì)二叉樹有了更深刻的理解，那么這一周的課程徹底顛覆了曾經(jīng)心中幼稚的見(jiàn)解，所謂質(zhì)變，我應(yīng)該是在這里體會(huì)到的：
從小學(xué)四年級(jí)開始在少年宮學(xué)習(xí)BASIC到初中的PASCAL，以致雖然后來(lái)停止學(xué)習(xí)，但因?yàn)榻佑|時(shí)間遠(yuǎn)早于同齡人而在此方面經(jīng)歷了各種優(yōu)勢(shì)，但從小在我心中“程序”，以及它背后所代表的機(jī)械邏輯始終被認(rèn)為是“就那么回事兒”的。我天真地認(rèn)為自己早已掌握“程序”界的終極真理，無(wú)非就是嚴(yán)絲合縫一步不差地執(zhí)行、再執(zhí)行，只要“機(jī)械”性地認(rèn)真下去，便沒(méi)有什么解決不了的，以至于從小就在性格中造就了一面“徹頭徹尾的唯物+實(shí)用主義者”，不相信任何世間美好。
有這句天真的話在前，接著慢慢成長(zhǎng)，讀書，行路，閱人，歷事，自然會(huì)學(xué)到原來(lái)這個(gè)世界真的不是那樣，開始理解愛(ài)與人性，開始理解這個(gè)世界的美妙。加上比較幸運(yùn)，因而“唯心+浪漫主義者”的一面在我的性格里也發(fā)展得很好。但大學(xué)開始繼續(xù)學(xué)習(xí)計(jì)算機(jī)，多少，對(duì)“程序”這一徹頭徹尾“唯物+實(shí)用”精神的產(chǎn)物，還是抱著一些看法的。
結(jié)束這一周的課程學(xué)習(xí)后，我改變了這個(gè)看法。
課程開始先講解了2-3 search trees，一種引入了新規(guī)則樹型結(jié)構(gòu)。這是一個(gè)“理解容易，實(shí)現(xiàn)復(fù)雜”的Symbol table方案，它可以對(duì)任何輸入數(shù)據(jù)保證樹形結(jié)構(gòu)的平衡以達(dá)到保證各項(xiàng)操作logN的復(fù)雜度，而規(guī)則卻足夠簡(jiǎn)單到可以在課堂中很快描述清楚，可以算是課程中第一個(gè)令我驚艷的算法。
這時(shí)我想：果然在一步步深入后算法變得高深莫測(cè)了起來(lái)呢，這個(gè)2-3 tree，理解起來(lái)容易，要實(shí)現(xiàn)起來(lái)可真是困難吶。已經(jīng)不是二叉樹那么簡(jiǎn)單的東西了，以后是不是只會(huì)更難啊，看來(lái)我遇到了一個(gè)屏障，這是不是我能走到的最遠(yuǎn)了啊。（開始有一點(diǎn)點(diǎn)擔(dān)心）
直到視頻結(jié)尾出現(xiàn)關(guān)于implementation的討論：
Bottom Line: Could do it, but there"s a better way.
緊接著下一節(jié)就是我們的主角：左傾紅黑二叉樹(LLRB)。
它只做到了一件事：將2-3 tree帶回了二叉樹世界，卻僅對(duì)樸素的二叉樹做極其微小的改動(dòng)——每個(gè)節(jié)點(diǎn)增加1 bit，用以表示“顏色”，加之無(wú)比簡(jiǎn)潔的引導(dǎo)，便在現(xiàn)實(shí)世界中實(shí)現(xiàn)了原先只是構(gòu)想的2-3 tree幾乎全部的優(yōu)點(diǎn)。
紅黑樹本身就是70年代Sedgewick教授參與提出的，而LLRB是由他一手提出的極其簡(jiǎn)潔的紅黑樹實(shí)現(xiàn)版本，尤其是它的insertion，在課堂上作為重點(diǎn)講解，僅在原樸素二叉樹實(shí)現(xiàn)代碼基礎(chǔ)上，增加了3個(gè)小工具函數(shù)（左旋、右旋、翻轉(zhuǎn)）和遞歸插入過(guò)程中的4行代碼（如圖），便完成了所有工作。
在徹底理解LLRB后，我想我被征服了。程序不再僅僅是徹頭徹尾“唯物+實(shí)用”精神的產(chǎn)物，而是我們理解世界的工具，也見(jiàn)證著我們改變世界過(guò)程，它與其他一切事物一樣，可以充滿真正的美。
我想可以這樣評(píng)價(jià)紅黑樹背后的思想：
它就像人類從蒙昧?xí)r代開啟智慧的一道光，將原來(lái)松散無(wú)序的組織變得優(yōu)雅而高效，并且還尊重了所有舊時(shí)代的傳統(tǒng)；
也正是因?yàn)樽鹬貍鹘y(tǒng)，才使得新的秩序得以穩(wěn)定存在；
新的秩序完整了傳統(tǒng)，成為了傳統(tǒng)當(dāng)中，最為亮麗的部分。
這樣的成果也不是憑空出現(xiàn)的：
勇于跳出傳統(tǒng)的框框，用自由的視角審度；（2-3 tree已不是二叉樹）
回到現(xiàn)實(shí)在一點(diǎn)一滴中細(xì)膩體驗(yàn)；（發(fā)現(xiàn)除繁瑣的直接實(shí)現(xiàn)外其他實(shí)現(xiàn)方式的可能性）
不妄自菲薄出身，用尊重的態(tài)度行動(dòng)。（選擇回到經(jīng)典二叉樹模式，試圖在舊傳統(tǒng)上建立新秩序）
知行合一，至此可謂正途。
同為插入255個(gè)隨機(jī)節(jié)點(diǎn)，左圖為樸素二叉樹，右圖為左傾紅黑二叉樹。
作為第一部分的最后一個(gè)作業(yè)，kd-tree其實(shí)難度沒(méi)有它看起來(lái)那么大。課程部分已很完整地討論過(guò)很多種經(jīng)典的樹形結(jié)構(gòu)（分析+實(shí)現(xiàn)），到這個(gè)階段學(xué)生應(yīng)已對(duì)樹形結(jié)構(gòu)非常熟悉了，實(shí)現(xiàn)kd-tree已是水到渠成。
同樣的，編程嚴(yán)謹(jǐn)性在這個(gè)作業(yè)中變得更加重要——情況相比前幾周又要復(fù)雜一些，從零編寫一個(gè)特定（且不簡(jiǎn)單的）規(guī)則下運(yùn)行的樹形結(jié)構(gòu)，主要功能是高效地插入與查找；
這次的作業(yè)同樣包含了一個(gè)暴力算法的版本（使用默認(rèn)的紅黑樹結(jié)構(gòu)），除了在執(zhí)行效率上可以做比較外，還提供了一個(gè)重要的軟件工程思路：面臨一個(gè)較為復(fù)雜，而優(yōu)化空間很大的問(wèn)題時(shí)，先實(shí)現(xiàn)一個(gè)最簡(jiǎn)單的暴力算法版本檢測(cè)結(jié)果（往往可以非常簡(jiǎn)便地實(shí)現(xiàn)），再考慮進(jìn)階的算法與數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)性能優(yōu)化，并在實(shí)現(xiàn)期間，暴力算法可以作為檢驗(yàn)算法正確性最直接的參考。
實(shí)現(xiàn)過(guò)程中值得提到的點(diǎn)：
節(jié)點(diǎn)的奇偶性是一個(gè)不小的麻煩，編寫需要十分謹(jǐn)慎，我的做法是在Node類中添加了一個(gè)boolean用以表示奇偶，相信一定有更好的方法（不存儲(chǔ)RectHV），還會(huì)回來(lái)探索；
Nearest Neighbor的查找過(guò)程需要思考清楚，剪枝的界限十分清晰，尤其是剪裁其中一個(gè)子樹的條件：如果本子樹中找到的最近點(diǎn)與給定點(diǎn)距離 已小于 給定點(diǎn)到另一子樹矩形區(qū)域的距離（點(diǎn)到點(diǎn)距離比點(diǎn)到矩形距離還近時(shí)），才能跳過(guò)另一子樹的遍歷過(guò)程。
左圖為Nearest Neighbor，右圖為Range Search。（根據(jù)鼠標(biāo)狀態(tài)信息）
圖中紅色部分為暴力算法運(yùn)行結(jié)果，藍(lán)色部分為kdtree運(yùn)行結(jié)果；在增加數(shù)據(jù)量后多帶帶測(cè)試，暴力解法效率明顯下降。
在一個(gè)學(xué)期的辛苦努力后，帶著滿滿的收獲與日益成熟的頭腦，第二部分正式開始了。
“相信經(jīng)過(guò)了第一部分的學(xué)習(xí)同學(xué)們都會(huì)有很大的提高，短暫休息后也恢復(fù)了飽滿的學(xué)習(xí)熱情，那么我有理由相信你們準(zhǔn)備好了接受點(diǎn)真正的考驗(yàn)?！?
—— 視頻中永遠(yuǎn)不會(huì)提到的導(dǎo)師內(nèi)心獨(dú)白（歷經(jīng)折磨后的腦補(bǔ)）
第二部分在課程與作業(yè)兩個(gè)方向的難度都比第一部分提升了一個(gè)檔次。好在不巧被導(dǎo)師言中，我的確有非常好的提升感和新一輪的熱情。
所以，放馬過(guò)來(lái)吧。
第一周便直奔主題，開啟了數(shù)據(jù)結(jié)構(gòu)領(lǐng)域的又一大領(lǐng)域：圖。
課程中出現(xiàn)了一個(gè)很有趣的分類值得提到，是形容問(wèn)題難度的：
任何程序員都能夠解決。
典型的勤奮的算法課學(xué)生能夠解決。
雇傭一個(gè)領(lǐng)域?qū)＜摇?/p>
非常難。
沒(méi)有人知道難度。
已證明不可能解決。
并舉出了一些符合條件例子來(lái)說(shuō)明這些分類，當(dāng)然可以料到的，有很多難度2的例子。
這針雞血打得，嘖嘖嘖，不留痕跡。
很好。諸位紅著眼的同學(xué)，準(zhǔn)備變身吧。
第一周的作業(yè)是WordNet，少了第一部分作業(yè)多圖多動(dòng)畫的喧鬧，不再為搏人眼球而吵吵嚷嚷，卻在安靜的terminal和腦中的抽象之海中展開了一場(chǎng)貨真價(jià)實(shí)的戰(zhàn)斗。
因文字方面中西文化背景截然不同，導(dǎo)致WordNet的概念不太方便簡(jiǎn)單地描述清楚，但作業(yè)說(shuō)明中已解釋得比較詳細(xì)，這里只放一張示意圖：
整個(gè)作業(yè)可以分為三大部分：選擇合適的結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)復(fù)雜的詞典及其網(wǎng)絡(luò)關(guān)系（基本功），實(shí)現(xiàn)正確高效的廣度優(yōu)先遍歷計(jì)算SAP（難點(diǎn)），和在此基礎(chǔ)上一層一層更細(xì)致的優(yōu)化（進(jìn)階）；
本次也是checklist優(yōu)化部分唯一標(biāo)注optional的作業(yè)，因?yàn)榈拇_實(shí)現(xiàn)起來(lái)有難度；分布如上所注。
詞典(synsets)為ID與單詞的多對(duì)多關(guān)系（一詞多號(hào)，一號(hào)多詞，釋義僅供參考無(wú)需讀?。?，上下位關(guān)系(hypernyms)是以ID為單位的樹形結(jié)構(gòu)（圖中的箭頭關(guān)系），可以明顯看出hypernyms使用有向圖表示，synsets存儲(chǔ)方式取決于訪問(wèn)需求，因程序中正反都會(huì)使用（以詞求號(hào)，以號(hào)求詞，求詞存在），我選擇了空間換時(shí)間：
