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