面向對象設計與構造——第一單元總結

OO_Unit1_Summary

寫在前面

OO課程的第一單元結束了，第一單元，以多項式求導程式為中心，不斷增加新的功能，我學到了很多：

1. 熟悉了Java基本文法；
2. 初步建立起了面向對象的設計思路；
3. 認識到了代碼可拓展性的重要；
4. 學會了建構自動化測試工具。

Complexity Metrics（複雜度分析）

因為下面要用到複雜度分析，是以先在此給出一些相關概念。

我們需要使用的主要是方法和類的複雜度分析。

方法的複雜度分析主要基于循環複雜度的計算。循環複雜度是一種表示程式複雜度的軟體度量，由程式流程圖中的“基礎路徑”數量得來。

1. ev(G)：即Essentail Complexity，用來表示一個方法的結構化程度，範圍在[1,v(G)]​之間，值越大則程式的結構越“病态”，其計算過程和圖的“縮點”有關。
2. iv(G)：即Design Complexity，用來表示一個方法和他所調用的其他方法的緊密程度，範圍也在[1,v(G)]​之間，值越大聯系越緊密。

3. v(G)：即循環複雜度，可以了解為窮盡程式流程每一條路徑所需要的試驗次數。

   對于類，有OCavg和WMC兩個項目，分别代表類的方法的平均循環複雜度和總循環複雜度。

下面我将從程式結構，公測、互測以及bug分析幾個方面來總結我第一單元的三次作業。

第一次作業

作業要求

實作簡單多項式的格式判斷和求導，其中多項式由項相加減組成，項是幂函數或帶符号整數。

實作方式

讀入時用ArrayList存儲多項式的每一項，用公式求導後輸出。

代碼規模

第一次作業代碼規模如下圖。

類圖

第一次作業類圖如下，其中Main是主類，PolyList是多項式類，PolyNode是多項式項類。

複雜度分析

第一次作業的複雜度分析如下。

可以看出PolyList的構造方法和print方法的複雜度很高，因為這兩個方法有一個共同點，就是用了很複雜的if/else條件判斷語句。

而PolyList的構造方法條件語句複雜，是對正規表達式應用不熟練導緻。

Bug分析

公測

筆者的程式在公測中沒有出現正确性錯誤，但是由于優化輸出的時候忘記-1*x中的1可以省略，導緻一個點性能分不滿。

互測

筆者的程式在互測中被發現一個bug，原因是筆者在做輸出優化時，隻考慮了最後隻剩一個系數為0的項，如果出現類似0*x^3+0*x^4​，這種兩個系數為0的項，就會沒有輸出。

筆者在互測中，hack了其他人17次，大部分都是正規表達式的錯誤使用導緻的，主要表現在對輸入各種情況考慮不周全。

測試方法

• python的xeger包根據正規表達式生成測試資料。
• python的sympy計算正确輸出，調用Java的輸出，并用equals函數判斷正确性。
• 閱讀每個人的代碼尋找漏洞，在互測中有兩個bug是我讀代碼讀出來的。

第二次作業

實作簡單多項式的格式判斷和求導，其中多項式由項相加減組成，項是由因子相乘組成，因子包括sin(x)，cos(x)，幂函數，帶符号整數。

實作方法

• 存儲多項式：采用HashMap，其中key采用三元組（x的指數，sin(x)的指數，cos(x)的指數），value存放每一項的系數。
• 求導：公式求導。
• 化簡：DFS + 三角函數性質化簡。

第二次作業的代碼規模如下圖。

第二次作業類圖如下，其中PolyList存儲多項式，ItemDegs為自定義的三元組的key。

第二次作業的複雜度分析如下。

其中幾個方法複雜度稍高，下面給出分析：

• optimizeTwo方法是DFS對輸出表達式進行三角函數性質優化，有時周遊次數會比較多。
• PolyList構造方法比較冗長，有100行，裡面用了很多條件判斷，是以iv(G)和v(G)會比較大。
• 而三個print方法對問題類似第一次作業，用了很多複雜的條件判斷，造成了很高的代碼複雜度。

筆者的程式在公測中，未出現正确性錯誤，但由于隻進行了三角函數合并，未進行貪心拆項優化，故性能分未能拿到滿分。

筆者的程式在互測中被發現4個bug，主要來源于幾個方面：

• 優化過程中，調用HashMap的remove()方法，但是有的時候這個方法不能remove掉目前的key，效果和未執行一樣。而且筆者到現在也沒想明白是為什麼，如果有大佬知道其中的原因，筆者想請教一下。
• 在用正規表達式檢查非法空白字元的時候，誤用了Matcher的matches()方法，導緻無法檢測空白字元。（正确用法是用find()方法）
• 正規表達式TLE，主要是因為用了大正則以及貪婪模式，改為非貪婪模式即可正常輸出。

筆者在本次互測時未發現他人bug，主要是因為對拍器出了問題（捂臉），sympy的equals方法有時候不能正确判斷表達式的等價性，是以在第三次作業筆者重寫了對拍器，代值進行計算來判斷正确與否。

第三次作業

實作簡單多項式的格式判斷和求導。其中多項式由項相加減組成，項是由因子相乘組成，因子包括幂函數，帶符号整數，三角函數，表達式因子，其中表達式因子為一個表達式外面加括号，三角函數可以嵌套因子。

• 讀入：采用類似遞歸下降的思路，反複調用構造方法，直到剩餘的項為幂函數或帶符号整數，将表達式用ArrayList存儲。
• 建構：将表達式從ArrayList建構成表達式數，葉節點全部為幂函數或帶符号整數，分支節點為運算符。
• 求導：對表達式樹進行DFS求導，得到求導後的表達式樹。
• 優化：對表達式樹進行可能的優化，如：1*x = x，0*x=0，1*2=2等。

第三次作業的代碼規模如下圖。

第三次作業類圖如下，其中Poly是表達式類，Item是表達式項類，CalculateTree是表達式樹類，Node是表達式樹節點類。

第三次作業的複雜度分析如下。

對于其中幾個比較複雜的方法，分析如下：

• CalculateTree的構造方法是用雙棧法建構表達式樹，調用了很多其他方法，耦合性比較高。
• deriv求導函數是一個DFS周遊，複雜度較高。
• simplify函數是對表達式樹進行優化，也是DFS的方法，而且裡面有複雜的條件語句，是以複雜度很高。

結合三次作業的複雜度分析，仔細思考了可能的解決方法：

1. 利用多态和繼承，将每一類的因子建立類，并分别實作求導，化簡，輸出方法，可以有效避免都塞進一個類的複雜度爆表。
2. 對于各種條件語句，可以多寫幾種方法，然後合并到總的方法中，這樣一個方法隻專注于處理一件事，就不會出現十分複雜的條件語句了。

筆者的程式在公測中未出現正确性錯誤，但是也沒有拿到性能分，原因可能是：

• 對多餘括号的去除還沒有做的很好，隻是做了簡單的優化。
• 公測資料都是精心構造，這樣做過精心優化的同學能得到更短的輸出。

筆者的程式在互測中沒有被發現Bug

筆者發現其他人3個Bug，分别是：

• 指數範圍判斷錯誤，題目要求小于等于10000，那位同學可能了解成了小于10000。
• 常數求導後沒有輸出結果。
• 求導後的式子不符合格式要求。

而其中前兩個Bug是筆者用手動造的測試集發現的，這也說明了自動資料生成有時候并不好用，手動造的資料才更具有針對性。

由于第三次代碼較為複雜，是以采取完全黑箱測試，采用随機數生成帶n層嵌套的項，并結合第二次作業的生成器，生成表達式。正确性驗證是模拟評測機，采用sympy帶入100個數計算，Wrong Format判定采用python的異常處理機制。

關于設計模式的思考

在第一單元的學習中，自我感覺對繼承和接口方面的知識，以及對工廠模式還沒有完全掌握，是以第三次作業沒使用工廠模式。利用這周閑暇時間，又仔細研究了一下，感受到了工廠模式+借口的友善和強大。在之後的多線程學習中，進一步深化自己面向對象設計模式是必須的。