面向對象第一單元博客作業

面向對象第一單元三次作業介紹

　　面向對象課程第一單元的學習結束了，第一周的主要任務是使用面向對象思想進行了三次難度遞增的表達式求導。下表說明瞭三次作業的要求情況。

　　　下麵我將通過自己的分析總結三次作業的不足和經驗。

對第一次作業的分析

設計思路

　　第一次作業我的想法非常簡單。首先，我們先通過正則表達式判斷輸入的正確性。對於錯誤的輸入，直接輸出 “WRONG FORMAT” ，執行結束；對於正確的輸入，則進行下一步。在第二步，我設置了一個類StringProcessor，來處理字元串。其作用就是將字元串中的有用信息提取出來，並依次存入多項式類Polynomial中的HashMap中去，與此同時要控制多項式的同類項合併，方便優化。顯然這次作業的有用信息只有次數和繫數兩個。然後在Polynomial類中單獨實現Hashmap的合併、求導、輸出當前存入的表達式等操作。可以看出整體上來看，這樣的設計思路是簡單並且清晰的。但是實際實現中會有不理想的情況發生，這部分會在稍後闡述。

　　由於第一周作業難度並不是很大，所以在作業前期我就開始考慮優化的方法。方法最後大概考慮如下：

　　　　① 正數項放在最前面；

　　　　② 0繫數：該項不輸出，除非是唯一的項；

　　　　③ 1或-1繫數、次數：繫數不輸出；

　　　　④ 0指數：將該冪函數化成1再來考慮。

　　可以看出以上的四種優化情況我們都可以通過調整輸出來實現。所以對我們的架構沒有本質上的影響。

程式實現

　　如上所言，本程式一共有兩個類：Polynomial.class 和  StringProcessor.class。Polynomial中含有一個 Hashmap 數據結構，用來存儲繫數與指數的對應關係，並完成有關多項式求導、輸出的一系列操作。StringProcessor 主要是進行合法輸入字元串的讀取和有效信息的提取。下麵是本程式的UML圖。

複雜度度量　

　　複雜度度量如下所示。由於第一次作業類的耦合程度過高，每個方法的複雜度也很高，導致複雜度情況並不理想。尤其是顯示多項式的方法，由於對多種情況考慮都綜合在一起，比較影響程式性能。在讀取字元串的指數部分沒有對多種情況分開討論而是寫在了一個方法裡面，也是影響程式的一個點。

Bug修改、遇到的問題

　　Bug 1：（自測）由於一開始對正則表達式的理解不充分，使用了整個表達式全部匹配的方法。在測試的時候當項數達到200項以上，程式就出錯了。主要原因是因為正則表達式匹配是一種貪婪匹配，整個表達式進行匹配導致複雜度過大，程式崩潰。

　　解決方法：修改為每項匹配並檢查上次匹配末尾是否是本次匹配開頭的方法能夠有效處理這個問題。不僅如此，在交流過程中，我發現有很多同學是每項匹配結束後直接調用matcher的內部函數來處理當前項字元串的，也就是說討論問題的範圍縮小到了一項。這樣的方法顯然要比我現在的架構要好不少，並且更加的“面向對象”。但是因為最後沒有時間修改自己的架構了，故維持原樣。

　　Bug 2：（自測）在測試過程出現了大數運算溢出的問題。

　　儘管使用了long型變數，但原題並沒有給出數據的範圍。是我在看題目需求的時候疏忽了。後來經過查閱資料發現java中有內置的一個大數類BigInteger。這個類使用體驗極好，給本次作業提供了很好的便利。

　　沒有遇到特別困難的問題，主要是第一次作業還是對這種思想不熟悉，用起來感覺怪怪的。所以即使思路簡單，但效率並不高。

對第二次作業的分析

設計思路

　　吸取上一次的教訓，本次作業是使用了單項單項進行分析操作的方法。主要思路是讀取字元串後，查看當前項是不是符合定義。如果不符合，則輸出錯誤信息並跳出程式；如果符合，則使用StringProcessor 將他們的指數和繫數都存入到 Polynomial 中的 Hashmap 中去。值得註意的是，指數（也就是 Hashmap 的鍵值）已經不止是1個了，我們需要建立一個類來存放 x、sin(x)、cos(x) 三個函數的指數組成的整體，並把它作為 Polynomial 的 Hashmap 的鍵值。在 Hashmap 的 Key 值實現上需要對此方法的 hashCode() 方法和 equals() 方法進行改寫，這是存儲階段。在求導階段，使用鏈式求導法則，對於每一個項可以分離出一個只有一個指數的項以及一個混合項，（例如 3*x^3*sin(x)^7*cos(x) 可以分離為 x^3 和剩餘部分），使用鏈式法則遞歸求導。保存求導後的數據，進行合理優化的輸出。

　　本次實現的優化，在上次作業的基礎上增進了對於三角函數簡單合併的一些操作，主要說來是對以下三個恆等式的處理：

　　① sin(x)^2 + cos(x)^2=1

　　② 1-sin(x)^2=cos(x)^2

　　③ 1-cos(x)^2=sin(x)^2

　　同樣，這三個恆等式的化簡，我們只需要在輸出階段進行處理即可，不影響我們的架構。

程式實現

　　根據以上的想法，本程式主要分為以下五個類：Polynomial 負責控制整個程式的入口，判斷表達式中項的合法性，建立 HashMap 存儲當前的指數-繫數對，整個多項式的求導控制等；StringProcessor 對一項的內容進行處理，分解為指數、繫數，並反饋給 Polynomial；Key 類是Polynomial 中HashMap 的鍵值類型，存儲了三個繫數；Term是實例化一項的備用類，裡面的屬性是一個Key值和一個繫數值；SinglePower是在求導時分離出來的只有單獨一項的特殊類，是求導的基本單位。下圖是本次作業的UML圖。

複雜度度量

　　複雜度度量如下圖所示，由於Polynomial.toString涉及了多種輸出方式的優化，所以其複雜度非常高。事實上，我們可以將三種方法分別在polynomial中實現最後合併在toString函數裡面，這種降低耦合度的設計以後可以多考慮一下。

Bug修改、遇到的問題

　　Bug 1：（自測）數組越界問題

　　修複方法：本次作業首次使用了try-catch手段進行異常的檢測、處理、拋出。

　　在編寫Key.class時修改了Key函數的hashCode()和equals()方法。事實上，在比較兩個類相等的時候，機制如下：

　　　　① 先比較兩個類的hashCode()，相等則轉②，不等則二者不等

　　　　② 調用equals()方法，返回bool值。

　　在使用類作為鍵值或者進行比較的時候，一般來說都要重寫這樣兩個方法。第二次作業因為主要沿用了第一次作業的想法和架構，所以感覺難度反而降低了一些，對於機制有了更好理解。但是實際上現在看來SinglePower完全可以作為Term的一個子類，並且可以直接把Polynomial的hashmap改成term的一個set進行存儲。這樣可能會在邏輯上和實現上更為清晰、簡潔一些。

對第三次作業的分析

設計思路

　　根據作業的提示，建立了加減法類、乘法類、嵌套類、三角函數類、冪函數類、常數類，並對他們分別建立了詞法分析函數。

　　合法性檢查：這次作業顯然不能再使用正則表達式去匹配一項了。這次採用了一種類似於詞法分析和語法分析器的功能，自頂向下分析。從加減法類進入，根據各種情況跳轉到相應的類中進行詞法檢查。在匹配的過程中可以利用正則表達式，簡化了匹配過程。

　　多項式信息存儲：合法性檢查過程中，經過每一個類將其直接下層類的信息變為線性結構存儲起來。例如：加減類就要存儲下麵的乘除類的信息，方便之後進行求導操作。這樣建立一棵多項式樹。

　　求導：自頂向下求導過程。同樣是上層類調用下層類的求導以完成自身求導。遵循鏈式法則。

　　本次的優化內容較複雜，我做了有關於去掉括弧和合併常數的優化，事實上並沒有做全，優化效果也比較差，根據分數顯示在強測中基本上都沒有達到最優方案的3倍這個限制，並且還因為優化出了一個強測的bug，影響了程式的正確性，確實是沒做好的一個點。我能想到的剩下一個提高程式優化性能的但是沒有做的點是合併同類項，例如對於 x+x+x+x 這樣的表達式，我的程式最後的輸出為 1+1+1+1 ，不做同類項合併的操作確實效果不好。但是總體來說做了以上兩種優化也是鍛煉了自己的一些能力的。

程式實現

　　本次程式實現使用了介面和繼承特性，將整個表達式從上到下建立了一個樹，架構還算比較清晰。主要問題是對於返回值的考慮並不是很清晰，一開始設計的時候有問題，導致返回的是一個求導後的多項式，這使優化變得比較艱難，只能通過重新讀取求導後的式子來進行優化。並且對於優化要單獨實現，喪失了一定的功能分散的特性。

 複雜度度量

　　由下圖可見，複雜度主要集中在優化函數、詞法分析函數上面，在這兩種方法上面，消耗的複雜度較高。我認為還是方法寫的不夠精煉詳細、功能還是過於複雜。不太符合設計原則。

Bug修改、遇到的問題

　　Bug 1：（強測）數組越界

　　Try-catch運用的還不夠好，不能理解其深層次的原理。並且是優化帶出來的bug，之後應當註重邊界檢查。

　　Bug 2：（自測）三角函數裡面的表達式不加括弧

　　解決方法就是加上括弧，並不引入其他括弧。

Applying Creational Pattern

　　第三次作業中實際上使用了Factory Pattern。使用這種Pattern的好處是使得各個類功能分明，在邏輯上更加清晰。更重要的是，擴展性更強。事實上，因為前兩次作業是第三次作業的子問題，我們當然也可以用工廠模式去套用。但是在問題發佈的當周，感覺沒有寫到這種程度必要，這種想法同樣使得前兩次作業的程式僅僅能夠解決前兩周的問題，可擴展性幾乎為0。這提醒我在設計的時候要有一定的遠見，保證程式的擴展性。同時堅持高內聚低耦合的設計原則。

總結

　　通過這三次的學習，首先是對面向對象程式設計思想有了一個大致的認識。其次對於面向對象語言的各種概念和機制有了大致的瞭解併進行了應用（如類、方法、繼承、介面、try-catch機制等）。通過自己課下練習、與同學討論和在課上通過老師對作業的總結講解，對於面向對象思想有了一個初步的認識，並且能夠明確感受到這樣一種思想與之前接觸的面向過程的一些程式語言的區別。與此同時，通過規範化的訓練，我也瞭解到了代碼風格對於程式設計的重要作用，並重新審視了之前自己寫過的不忍直視的代碼。期待後續的學習能夠更加更深層次的挖掘這門思想的奧秘。