前言

第三單元的作業(yè)主要是為了幫助我們了解JML規(guī)格的設計和使用，我們需要通過閱讀JML規(guī)格說明書以及實際的表述來完成我們的代碼設計。本單元的主題是實現(xiàn)一個社交關系模擬系統(tǒng)，可以通過各類輸入指令來進行數(shù)據(jù)的增刪查改等交互。不同的人通過社交網(wǎng)絡建立各自的聯(lián)系，類似于微信、QQ等軟件，大家可以發(fā)送文字消息、表情包、紅包等等，從而體現(xiàn)本社交模擬系統(tǒng)的功能。涉及的算法包括迪杰斯特拉、深度優(yōu)先遍歷等圖論中的方法。

設計策略

整體框架如下圖：

圖中體現(xiàn)了不同類之間的關系，可以發(fā)現(xiàn)，我們的核心是MyNetwork類，它與所有的類之間都建立著緊密的聯(lián)系。除此之外，我們還有Message、Group、Person類，分別代表信息、群組、個人，然后是十個異常類。

下面重點談一談我的設計策略，本單元中需要精心設計的地方有許多，如果單純的不考慮性能的話，那問題就非常的簡單了，只需要按照JML規(guī)格一步一步的照做就可以了。但是由于強測涉及到性能的約束，因而我們需要采用更加快速、效率更高的算法。首先遇到的挑戰(zhàn)是isCircle方法，它需要我們判斷兩個人之間是否存在著一條路徑，即是否連通，面對這個問題，我們可能會使用到DFS等遍歷方法，如果找到了路徑就返回True，如果沒有就返回False，可是這樣無疑效率是不夠好的，于是受到啟發(fā)，我采用了這樣的思想：將所有人形成的社交網(wǎng)絡分成許多連通分量，每一個分量（或者稱為集合）中的元素都互相連通，存在路徑，隸屬于不同集合的兩個元素之間不存在通路，這樣在判斷isCircle的時候，只需要判斷兩個人的id是否在同一個集合中就可以了。對于集合的產(chǎn)生，我們在addPerson時，形成一個新的分量，在addRelation時，將具有relation的兩個集合合并即可。這樣很好的提高了效率，不用再進行多次的遍歷。

然后是getValueSum，需要我們獲取組內(nèi)人員兩兩之間的權(quán)值之和，我們同樣可以采取遍歷的方式來累加，但是如果有很多這樣的指令到來，就可能浪費了時間上的性能，如果我們考慮事先定義一個變量valueSum，在每次有人進入群組時，就將新產(chǎn)生的權(quán)值累加，有人退出時，就去除這些權(quán)值，在addRelation時，加入對應的權(quán)值，這樣，在getValueSum指令到來時，我們就可以直接返回valueSum了，這樣的思想同樣適合于求均值、求方差。

最后一個難點是求最短加權(quán)路徑長度，這時使用迪杰斯特拉算法效果還不錯。

測試方法

測試方法主要采取了Junit測試，對主要的方法編寫測試程序，示例如下：

如果出現(xiàn)錯誤將拋出異常，從而能夠知道出現(xiàn)錯誤的位置，同時也可以使用assert斷言方式，來進行判斷。

容器選擇

在容器的選擇上，我大部分采用了Arraylist，而在連通分量的地方使用的是Hashmap，在迪杰斯特拉的算法中使用的是二維數(shù)組構(gòu)成鄰接矩陣，這樣做都有著一定的道理。在異常類的計數(shù)方面，我使用了如下的變量：

all表示總次數(shù)，ID_LIST表示id序列，TIMES為對應id觸發(fā)異常的次數(shù)，現(xiàn)在想來其實也可以使用Hashmap或者Hashset來解決，能夠進一步簡化問題。

性能分析

本單元的性能要求比較高，我連續(xù)幾次強測都出現(xiàn)了CPU超時的現(xiàn)象，采用優(yōu)化的算法以后性能得到了一定的提升，但是仍然存在一兩個測試點無法通過，我認為問題可能出現(xiàn)在迪杰斯特拉算法上面，我采用的是鄰接矩陣，如果采用鄰接表的話可能效率會更高一些，或者使用其他更好的算法。

bug修復

產(chǎn)生的bug主要有兩種，一類是超時現(xiàn)象，前面已經(jīng)說過了，另一類是wrong answer，主要是一些細節(jié)的地方出現(xiàn)了紕漏，并且在測試中沒能檢查出來。這意味著我的測試還不夠全面，在一些自以為不會出現(xiàn)問題的地方?jīng)]有進行嚴格的測試，于是導致了bug的出現(xiàn)。

心得體會

這一單元給我的感受，或者說是印象，主要有三個方面，第一是程序的規(guī)范性，在JML規(guī)格的影響下，我逐漸意識到了代碼風格以及架構(gòu)方式的重要性，在以后的編程過程中，我會更加注重代碼的簡潔、標準、清晰性，保證結(jié)構(gòu)與內(nèi)容一目了然，使得自己或是其他人能更快的明白代碼的含義。第二是測試方法，以前的我基本上都是依靠課程的評測機、測試數(shù)據(jù)點來找自己程序的問題，這樣固然簡便，但是不能保證我的程序是完全沒有問題的，只有在課下充分測試、仔細閱讀代碼、分析步驟結(jié)構(gòu)、進行程序?qū)ε模拍芨玫耐晟谱约旱拇a。第三是性能的關注，之后的設計，或者是工作崗位的要求，往往工程量會越來越龐大，這時應當考慮性能的因素，盡量優(yōu)化算法，采取更為簡便高效的方法來解決問題，減小開銷。