OO第三單元總結(jié)(JML規(guī)格)
前言
第三單元的作業(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)化算法,采取更為簡便高效的方法來解決問題,減小開銷。
浙公網(wǎng)安備 33010602011771號