第一单元总结：基于基础语言、继承和接口的简单OOP
前情提要
到目前為止，OO課程已經完成了前三次的作業，分別為：
第一次作業
功能介紹
對某種格式的多項式進行parsing，之后計算其導數，按相同格式輸出。
多項式由項組成，項有且僅有系數和x的冪。不存在多于兩個因子的項。
類圖
程序的大致結構如下圖：
第一次作業程序結構比較簡單，Main中構造一個Poly對象，Polynomial由Item聚合而成。
代碼分析
?可以看出，除了Polynomial類的構造函數，其他的方法的復雜度均不高。
而造成其構造函數復雜度稍高的原因是在不斷parsing的時候需要一定的分支、循環等邏輯。
雖然該構造函數僅有不到23行，但是當邏輯進一步復雜的時候，不如將循環體內部的一些操作移出到一個類似工廠的小靜態方法中。
測試與Bug
公測
不出意外，筆者的程序在公測階段沒有出現任何錯誤。
互測
不出意外，筆者的程序在互測階段沒有出現任何錯誤。
在互測中，筆者challenge中了同屋的5個數據點。其中有一個是當自己在剛開始寫程序時，同時手造的數據，為了驗證自己程序的正確性；其他的數據點均為數據生成器和對拍器發現的bug點。
在手造數據時，應該仔細針對輸入格式說明，從基礎的元件（如冪函數部分：x還是x^；x^后面的數是有符號還是無符號，是正是負）開始，逐步向上構造用例，使用“乘法原理”將不同的情況組合起來。
Bug分析與總結
- 正則中的"\s"是匹配所有空白字符，并不只有tab和space。
- Java的trim()是去掉所有ASCII碼比space小的字符，因此可能會將其他不期望的空白字符一并去掉，在使用時應該注意。
- 使用正則表達式嘗試完全匹配一個超長的字符串是慢且有爆棧可能性的，應該將重復的特征提取出來，并手動while()一段一段地匹配。
第二次作業
功能介紹
對含有sin(x)和cos(x)（及其冪）的多項式進行parsing，之后計算其導數，按相同格式輸出。
多項式由項組成，項有且僅有系數、x的冪、sin(x)的冪和cos(x)的冪。每個項的因子數不定，類型不定，類型順序不定、可重復。
類圖
可以看出，第二次作業的代碼結構復雜了許多。
Main調用ExpressionParser得到生產出的Expression。Expression由Item聚合而成。
除此之外，ExpressionParser還使用了輔助其進行遞歸下降的MatchType類；Expression還使用了輔助其進行合并同類項的Tuple類。這兩個類較為獨立，只執行很小的工作，與程序的主體耦合性很低。
代碼分析
（篇幅所限，部分復雜度極低的方法在圖中已隱去，現在只討論復雜度高的方法實現。）
不出意外，Item.toString()方法、Parser.factor()和Expression.simplify()方法的復雜度較高。下面對其逐一分析：
- Item.toString()方法和ExpressionParser.factor()方法：
由于比較懶（因為可以直接套公式求導，就直接在Item里面存了4類因子的指數/系數），這樣四種因子就沒有設計獨立的類，就導致了以下兩個潛在的問題：- 1. 在Item的toString()方法和ExpressionParser的factor()方法中，需要同時對4種因子逐一進行處理。這意味著需要至少4個功能相似的if語句，再將不同的factor組合起來。
不如將其分散到4個獨立的方法中，或者真的建立4個factor類的子類，將其單獨管理。 - 2. 可擴展性差，在第三次作業中需要重構。
- 1. 在Item的toString()方法和ExpressionParser的factor()方法中，需要同時對4種因子逐一進行處理。這意味著需要至少4個功能相似的if語句，再將不同的factor組合起來。
- Expression.simplify()方法：
層次混亂、自己和其調用的子函數的功能分界不明晰。
思考后，不如這樣總結：
在一個方法中，應該首先按“功能的基本單元”對其任務進行劃分。對于并列 / 有先后順序依賴的層級關系，應當將子任務剝離到子函數中，再在本方法中進行并列 / 順序的組合。
【本方法的核心任務是組合不同任務的執行結果，而不是首先執行不同的子任務再組合它們。該提取的就要提取。】
測試與Bug
公測
不出意外，筆者的程序在公測階段沒有出現任何錯誤。
互測
不出意外，筆者的程序在互測階段被challenge了一個TLE的點。
TLE的原因為，在嘗試進行輸出化簡時，對過多的DFS分支進行了遍歷，沒有控制好嘗試的次數因子。
而事實上，往往嘗試300次就可以得到（公測條件下的）最優解，而筆者為了一點小小的性能分貪心地設置多了一點嘗試的次數（分支數），最終導致了T。
在互測中，筆者challenge中了同屋的5個數據點。這5個數據點均為數據生成器和對拍器對拍發現的bug。其中大部分為相同的化簡導致的TLE。
Bug分析與總結
- 在互測中，筆者challenge了同屋的一個正則表達式匹配錯誤。
這個bug很神奇：在jdk8下會TLE，而在jdk10下將會秒過。
記得當時查到一篇文章（現在找不到了QAQ）說，java8中一些設計丑陋的正則表達式在回溯時將會瘋狂的吃時間。而巧合的是，這次作業中的這個同學，同樣的是想用一個完整的正則表達式去匹配一個完整的字符串。
這里引用一下學長的話：
“第一次據筆者觀察，很多同學還對java這門語言完全處于不熟悉的狀態，對于正則表達式等概念及其具體原理也完全不了解，更不用說面向對象的設計思想了。據筆者所知，像這樣試圖用一個龐大的正則表達式判斷格式的同學并不在少數。然而了解正則表達式相關原理的同學都應該清楚，正則表達式不是讓你這么用的。正則表達式更多的用于相對簡單且沒有復雜的重復和嵌套的一些的模式匹配，以及其內部關鍵位置信息的提取。” 這里的話就很精髓：正則表達式是為了我們提取匹配串中的特定位置的信息的工具，常用于檢查如輸入表單的合法性，提取URL、數字串、時間日期，或者類似于提取特定標簽內的內容等工作。
而處理含有復雜的語法規則的、擁有許多分支的類似“代碼”的串，并不是正則表達式的真正用武之地。
無論這個bug是不是java8的鍋，筆者認為到了第二次作業還想用大正則判斷合法性的想法，是不可取的。（可能僅僅是因為長度只有100，很多人才摸過一劫） - 在互測中，筆者還challenge了另外一個同學的"\u0010"bug。
這個bug，說實話可能會被認為很無聊。但是這位同學寫的其實是： 如果輸入串contains “\f” "\v"，就throw WrongFormatException。否則就認為不含有非法空白字符。 這樣的對輸入情況的特判，是極其沒有魯棒性的。同時這也提醒我們，在所有的分支邏輯處，都一定要思考清楚自己在干什么、程序在干什么，有沒有把該覆蓋的情況覆蓋全。
第三次作業
功能介紹
對含有嵌套的復雜表達式進行parsing，之后計算其導數，按相同格式輸出。
可推出如下形式的遞歸下降文法：
expr? ?::= SIGN? term { SIGN term }*
term? ?::= SIGN? factor { TIMES factor }*
factor ::= SIGNEDNUM | x^SIGNEDNUM | SIN(factor)^SIGNEDNUM | COS(factor)^SIGNEDNUM | (expr)
類圖（只顯示繼承、實現等關系）
第三次作業經過第二次作業的大修，終于將Item與Factor分離，設定了抽象類Factor，并繼承了數字、冪函數、三角嵌套函數、表達式因子等5種具體因子類。
同時，實現了Sortable接口，用于化簡時利用多態更易處理。
注意到，定義和實現的Derivative接口實際上是一個假接口，其與Sortable接口不同：
- SortOut()方法的返回值不定，比如ExprFactor.Sortout()的返回值并不一定是ExprFactor類型，
其可以是Expression類型、Item類型和其他Factor類型。使用接口則方便了許多，只需要將返回值聲明成Sortable類型； - 然而getDerivative()方法的返回值在不同類中均是確定的，不需要進行多態處理。
同時，在循環中調用getDerivative()方法時的this對象的類型也是確定的（因為Expression的List必是Item，Item的List必是Factor），這樣設計下接口的意義僅僅是“確保大家都實現了getDerivative方法”。
這樣的接口毫無意義，是為了設計而設計；或者說，不如將其與Sortable接口合并。這樣雖然現在沒有用，但是在以后的拓展性也還能保持。
代碼分析
?
（篇幅所限，部分復雜度極低的方法在圖中已隱去，現在只討論復雜度高的方法實現。）
很遺憾，在補充第二次作業的遞歸下降Parser的時候，筆者仍然菜到沒有將5種因子分別從Parser.factor()中剝離出去，才導致了metric分析出來方法三項指標都爆炸。
這樣不但導致了單方法的復雜度過高，還使其可拓展性、可維護性大大降低（試想如果今后加入更多種的因子，該方法將會變的冗長且有很多重復部分。）
而幾個equals()方法被判定ev過高是因為筆者采取了先判斷引用再判斷null再判斷同類、最后再判斷內部對象的寫法（從《Java核心技術》學來的），就會有三四個if，個人認為問題不大。
而兩個SortOut()方法的復雜度過高的主要原因為，要分別針對5種factor進行處理，然而處理中需要用到該方法的局部變量，所以就沒有將其下放的factor類中，或者是單獨實現5個方法。
思考后認為解決方法有：
- HashMap、ArrayList均為可變對象，可以作為參數傳入負責該問題的方法中對其進行修改，而也沒有進行clone等操作浪費時間；
- 靈活使用多態和null，減少不必要的邏輯分支
- 將不必要的for循環換成collection的addAll()方法
- 當時間性能要求低時，合理使用lambda去除分支語句
同樣的，從類復雜度度量中也可以看出，Item的部分操作應該下放到Factor中，并合理使用多態減少邏輯分支。
同時，ExpressionParser中存在部分冗余代碼，應該將其抽提出來。
測試與Bug
公測
在強測中，筆者的程序TLE了兩個點。（下文分析）
互測
在互測中，筆者的程序被challenge了一個TLE的點。（下文分析）
而筆者利用對拍器+數據生成器，共challenge成功10個數據點（此外還包括6個同質數據點）。其中大部分的bug均為：
- 對Format判定的準確度不夠，經常將正確數據判定成錯誤，也有少見的將錯誤數據判定成正確的情況。
大多數均是對文法設計不夠精確（從而暴露出自己在提交代碼之前沒有好好覆蓋測試的問題），也有在遞歸下降分析器中的bug。 - 在遞歸下降分析器中思路不夠清晰、容易遺漏情況，經常忘記形如"-(1+x+cos(x))"括號前面的負號的問題。
- 對遞歸下降的理解不夠深刻，稍微復雜的表達式就會出現TLE/爆棧錯誤。
此外，筆者還通過手構數據對關鍵的易錯點進行定點嘗試，成功發現了1個罕見的bug并challenge成功。
Bug分析與總結
筆者在公測和互測中TLE的3個點均為同質的惡性bug，分析如下：
首先看這樣一段代碼：
for (Item i : items) {i = i.SortOut();// do something with iif (some condition) {newItems.add(newI);} else {newItems.add(i);} }for (Item i : newItems) {i = i.SortOut();// do something with i }可以看到，為了優化當前表達式（由items組成），首先優化各個Item i，之后將其進一步處理。
然而，在中間變量newItems中，可以說大部分的元素都是已經調用過SortOut()方法，已經保證最優的了。只有少部分newI對象是沒有調用過
可是筆者在寫代碼時一時腦抽，想進一步確保i的最優性，于是重復調用了SortOut()，而且沒有對當前對象是否是已優化進行標記。于是造成了時間復雜度成指數增加的惡性bug。
顯然正確的寫法應該是：
for (Item i : items) {i = i.SortOut();// do something with iif (some condition) {newItems.add(newI.SortOut());} else {newItems.add(i);} }for (Item i : newItems) {// do something with i }這樣就確保每個newItems里面的對象，都有且僅有被調用過一次SortOut()方法。
這個bug的存在原因大致有三：
- 在寫代碼時沒有想清楚，拿起鍵盤就是干；
- 在oo作業中沒有去考慮時間復雜度（除了第二次作業的暴力），根本就沒有去像算法競賽似的去考慮會不會T的問題；
- 測試不到位，在手構數據基礎覆蓋測試的時候沒有“乘法原理”式的覆蓋所有可能的情況。
一個顯然的性能測試應該如下：- 首先測試基礎樣例，這里指所有不含冗余嵌套的規則輸入；如"x"、"sin(x)*x"、"sin(0)*x"、"sin(x)*5*x-4*x^3*cos(x^2)"等
- 之后嘗試冗余嵌套，包括在外部和在內部等，包括括號和三角函數等；
- 以在外部的冗余括號嵌套為例，測試時應當在"((((((?))))))"的?處填入所有基礎樣例中的數據，而不是僅僅測一組"((((((x))))))"就敷衍了事。
如果在自己測試的時候真正做到了這點，這個TLE的潛在可能就會被發現！
?設計模式探討
在基于metric的代碼分析中可以看到，ExpressionParser的部分方法的復雜度很高。
現在筆者使用的是直接由Parser看出需要創建什么樣的對象，并直接調取對應具體類的構造方法進行構造。
因此，在Parser中將會存在一些對“要創建什么樣的具體對象”的判斷工作。
而工廠方法模式對解決這個問題就很適合，下面引用一段介紹：
意圖
問題
一般來說有幾種情況需要用到Factory Method：
其實就現在而言，Parser就像一個大工廠：它先解析字符串，然后它既制造Expression，又制造Item，又制造Factor。
這樣的設計模式顯然是不夠優美的：Parser的工作應該是（且僅僅應該是）判斷接下來的一段字符串是一個Expression，還是一個Item，還是一個Factor。
換句話說，Parser應該來判斷是要創建expr、item、factor三棵樹中的哪一個（參見類圖），而不應該繼續探究“應該創建ROOT樹下的哪一個葉子節點（如numFactor、expFactor等等）”！
因此，為了
應當設計一個創建Factor的工廠。
工廠模式的簡要UML圖如下：（引用自https://blog.csdn.net/carson_ho/article/details/52343584）
總結
- 測試的問題
- 手構數據按照一定樹形結構和不同樹間的乘法原理，盡量覆蓋所有情況，不要有僥幸心理
- 對拍器+數據生成器的方法很好用，但是要保證數據生成器與oo代碼不能是高度一致的，否則沒有意義
- 性能
- 時間和空間的性能比所謂的長度優化更為重要，是程序設計的基礎
- 減少clone，多用引用
- 不要進行重復性的、無意義的工作
- 面向對象
- 利用多態和null等技巧，減少在上層不必要的邏輯、將邏輯下放，防止某一層結構的類和方法復雜度激增
- 每個方法各司其職，如有必要大膽創建子方法，在父方法中只進行組合（并列、順序等）關系的操作，具體的任務分散到子方法 / 子對象的方法中
- 盡量使用繼承和接口，提升自己上層類設計的復雜度，同時盡量更好地支持可拓展性和可維護性
- 基礎語言
- 正則表達式的正確打開方式，和不適宜的使用場景
- 可變對象可以作為參數傳入方法中，并可以對其進行修改。基于此，可以有效地降低方法的復雜度，使方法各司其職
轉載于:https://www.cnblogs.com/FuturexGO/p/10585564.html
總結
以上是生活随笔為你收集整理的第一单元总结：基于基础语言、继承和接口的简单OOP的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： windows下搜不到linux文件？
- 下一篇： 博客教程中百度网盘地址