OO第二單元總結(jié)

摘要

第二單元相對于第一單元，在思路構(gòu)建和過程模擬的難度上有了較大的提升，因為多線程本身的不確定性和bug的隨機復現(xiàn)性，所以需要我們構(gòu)建出良好的架構(gòu)以及我們要對自己的代碼運行過程有著極為清晰的認識。然而，相對于第一單元，在面向?qū)ο蟮乃悸飞想y度稍微好了一些，主要原因是隨著課程的深入，對面向?qū)ο蟮睦斫庖哺由羁蹋酥?，電梯相對于表達式，是一個更加貼近生活的對象（我甚至在公寓電梯里一直不出去企圖分析電梯的運行過程），化簡表達式時要對各種結(jié)構(gòu)進行拆分建模，而分析電梯的運行過程時，其在我們腦海中構(gòu)建的時候本來就是以對象的形式存在的，比如說電梯、乘客（請求）、樓座樓層、請求隊列等等，我們在讀題的過程中盡管不一定有非常清晰的敲代碼思路，但是該建什么類，類中該有什么屬性是比較容易想出來的。

第五次作業(yè)（無中生有）

1.架構(gòu)與多線程分析

由0邁到1的這一步是異常艱難的（也正因如此對第五次作業(yè)的分析會多一些），由于之前對多線程根本不了解，看完相關(guān)基礎(chǔ)知識后瀏覽指導書發(fā)現(xiàn)真的很難：既要考慮架構(gòu)，也要考慮可迭代性，又要考慮線程安全問題。當然，分析完第五次作業(yè)指導書后，會發(fā)現(xiàn)本次作業(yè)不太需要考慮線程安全問題，因為5臺電梯本身是互不干擾的，每個請求應(yīng)該去哪個電梯哪個位置等待也都是固定的。換句話說，當輸入線程讀到一個指令的時候，我們可以直接把指令放到確定的位置，不用顧及任何事情，類比到現(xiàn)實的話，那就是你想從新主樓F的2樓到3樓，那你就直接去F的2樓的電梯門口等著就好了，沒有什么需要考慮的。

至于調(diào)度算法，再看完指導書中的ALS基準策略后，感覺ALS好像實現(xiàn)起來有點復雜，過程也沒太弄清楚，而且對于很多情況運行時間都不會太好，再請教了同學和瀏覽了學長的博客后，發(fā)現(xiàn)look算法比較好，而且更好理解、更好實現(xiàn)、性能也很不錯。我在網(wǎng)上并沒有查到特別詳細的look算法，根據(jù)各種各樣的信息，我實現(xiàn)的look算法如下：電梯有一個初始方向（一般定為上），電梯每到一個樓層對電梯內(nèi)部和外部的乘客進行分析，如果到達了內(nèi)部乘客的目的樓層，該乘客出去，如果外部乘客的方向（上樓或下樓）跟電梯一樣，那么電梯就讓他進來（這里省略的開關(guān)門的分析過程以及電梯容量問題）。當電梯內(nèi)部沒有人，并且電梯同方向上的其他樓層也都沒有乘客叫電梯，那么電梯反向。這個算法的一個特點就是，電梯不存在主請求，只是不斷的上下樓，符合條件就讓進出，實現(xiàn)起來比較容易，捎帶策略和轉(zhuǎn)向策略也使得這個算法在性能上比ALS也好了很多，當然在討論課上也發(fā)現(xiàn)了其他同學的一些優(yōu)化方法，例如目的地和起始地距離近的乘客優(yōu)先進入，這樣可以減少電梯來回一次的時間。

綜上，本次作業(yè)我主要采用了輸入線程類InputThread，電梯類Elevator，請求表類RequestTable，策略類Strategy。至于為什么沒有乘客類Person，這其實是我比較矛盾的一個地方，官方給的PersonRequest所包含的全部信息基本上就是我乘客的屬性了，我就沒有再建造一個Person類來去復制PersonRequest的屬性，直接把指令當成人看，這里確實不太符合現(xiàn)實。除此之外，我并沒有構(gòu)建一個調(diào)度器負責安排指令位置，因為正如上面所說，指令具體去哪個電梯直接就能知道，因此我直接在輸入線程內(nèi)將指令傳給了請求表RequestTable，而請求表類本質(zhì)上就是一個三維乘客數(shù)組（這是個抽象說法），根據(jù)樓座和樓層，我就可以直接找到該位置的請求隊列，因此，對于第五次作業(yè)來說，調(diào)度器確實是沒什么用的，不過也得留一個心眼兒，對于以后的迭代肯定是需要調(diào)度器的。

策略類Strategy里面實現(xiàn)了我的look算法，至于策略類的存在意義是什么，我認為是為了以后的迭代考慮，策略類可以為我的電梯提供這種各樣的策略接口，這樣電梯就可以擁有不同的調(diào)度。

至于線程通信，wait-notify機制固然不錯，但是我認為有一個相對不符合現(xiàn)實的地方就是，如果來了乘客，理論上我們只需要喚醒該乘客所乘坐的電梯即可，而不是用notifyAll去喚醒所有電梯再讓剩余的電梯發(fā)現(xiàn)沒乘客然后接著睡。于是我在網(wǎng)上查到了一個LockSupport工具類，其中調(diào)用LockSupport.park()直接就可以在該位置進行暫停（wait），而LockSupport.unpark(Thread)（括號內(nèi)是你要喚醒的線程，也就是某個電梯）可以喚醒該線程。除此之外，這兩個方法不用像wait和notifyAll封裝在sychronized里，也不用考慮先后順序問題，使用起來非常直觀且可靠。wait-notify機制對于我們對多線程的理解更加深入，而LockSupport工具類對于對多線程不熟悉的人來說用起來更加方便，當然只是個人想法。

2.代碼分析

UML類圖如下：

UML協(xié)作圖（三個線程視角）如下：

Statistic分析如下：

Metrics分析如下:

根據(jù)上述分析結(jié)果，我們可以發(fā)現(xiàn)：首先，在架構(gòu)設(shè)計方面，利用輸入線程來獲取指令，將指令送往指定隊列然后喚醒指定電梯，電梯喚醒后調(diào)用自身的策略類，策略類來進行調(diào)整電梯和乘客的狀態(tài)。因此，我將look算法全部在Strategy類中實現(xiàn)的，因此Strategy的復雜度也確實高了一些，其實根據(jù)指導書，策略類理論上只是負責提供主請求，真正的上下樓和開關(guān)門應(yīng)該是電梯自身干的事情，但是由于我在實現(xiàn)look算法的過程中沒有用到主請求這一對象，因此這里的設(shè)計確實復雜了一些，也確實有悖面向?qū)ο蟮乃枷搿?/p>

在線程交互方面，其實只有輸入線程喚醒電梯線程這一個稍微復雜的地方，再一個就是電梯線程的停止條件需要包含輸入線程是否結(jié)束。實際上第五次作業(yè)基本上不存在線程競爭，需要加鎖保證線程同步的地方有兩處，一個是官方提供的輸出類，一個是請求隊列的add和remove，因為我的請求隊列是一個ArrayList，因此需要加鎖保證其add和remove能夠線程同步，其他地方確實不需要考慮。

直觀分析代碼本身，發(fā)現(xiàn)Strategy的look算法實現(xiàn)的非常復雜，我為了能夠保證方法行數(shù)不超過60，強行在一些地方進行了封裝，因此這里的實現(xiàn)相當?shù)牟粌?yōu)雅。

對于該架構(gòu)的優(yōu)點：由于電梯之間比較獨立，大體上整個電梯運行的過程還算是比較清晰，而且策略類的構(gòu)建有利于后面作業(yè)的擴展，因為不同的電梯可能需要考慮不同的策略。

該架構(gòu)的缺點：靈活性還是不夠，無法適應(yīng)其他種類的電梯，由于采用的是靜態(tài)調(diào)度，對后期作業(yè)可能存在的動態(tài)分配請求并沒有良好的適應(yīng)性，而且多個方法的實現(xiàn)都非常的復雜冗長，debug不方便且不優(yōu)雅。

第六次作業(yè)（多多益善）

1.架構(gòu)、調(diào)度器與多線程分析

第六次作業(yè)在第五次作業(yè)的基礎(chǔ)上，架構(gòu)方面有了一定的改動。根據(jù)指導書，我們增加了橫向循環(huán)電梯，原先的樓層變成了橫向電梯的樓座，原先的樓座變成了橫向電梯的樓層，而且沒有最高處和最低處之分，除此之外，對于橫向請求，只有相對方向，沒有絕對方向，因為電梯只要保持一個方向走，總會到達該請求的目的地。經(jīng)過分析，由于橫向電梯和縱向電梯擁有很多相同的屬性，我打算把這兩種電梯解離成縱向電梯（VerElevator）和橫向電梯（HorElevator），同時繼承一個主電梯類（Elevator），除了基本的屬性，兩種電梯的區(qū)別主要在于策略的不同，因此，Strategy里除了包含第一次實現(xiàn)的縱向look算法，又添加了橫向look算法（所以復雜度又增加了......）。除此之外，對于電梯的屬性（樓座，ID，樓層，內(nèi)部乘客等），我又添加了一個二維請求數(shù)組<樓層，請求隊列>。其實根據(jù)實際，乘客/請求可以說是和電梯是分開的，他們更像是樓的屬性，然而之所以我將10層樓的請求隊列放入電梯內(nèi)部，是因為我忽略了樓的這個概念，電梯則是一個架空的對象，每個電梯有10個隊列，進入電梯等同于外部隊列remove，內(nèi)部隊列add，乘客出電梯等同于內(nèi)部隊列remove，而與這五棟樓沒什么關(guān)系了。

此次作業(yè)還增加了添加電梯功能，因此，我這次構(gòu)建了一個調(diào)度類（Schedule），該類的作用是兩個，一個是獲取增加電梯的請求向電梯容器中添加新電梯，另一個是獲取乘客的請求將其分配到指定電梯。因此調(diào)度類里擁有我目前所擁有的所有電梯。而由于我每一部電梯都擁有屬于自己的請求集合，我采用基準策略來將指令送往電梯。由于電梯個數(shù)的增多，其實理論上采用自由競爭的分配策略會更好一些，然而由于我不想對已有的架構(gòu)進行大的調(diào)整，并且我想保證線程的安全性，因此，采用基準策略來平均分攤電梯，不過，依照我的理解，我并沒有按照指導書中說的那樣進行分配，而是選擇目前內(nèi)外乘客數(shù)量最少的電梯優(yōu)先分配。我用了一個比較樸素的思想就是，越忙的電梯盡量就別給他增添請求了，把請求給一些比較閑的電梯能節(jié)省一點時間，盡管沒有理論上驗證是否合理，不過感覺和基準策略差不太多。與此同時，幾臺電梯同時去搶奪一個請求隊列的情況就不存在，換句話說我直接就是多了10臺電梯，然后無論怎么添加，各個電梯之間依然是相互獨立的。

2.代碼分析

UML類圖如下：

UML協(xié)作圖如下：

Statistic分析如下：

Metrics分析如下：

線程角度：由于我本著求穩(wěn)的心態(tài)，在線程通信這方面基本上和第一次作業(yè)一樣，換句話說盡管電梯增加了，每個請求去哪個電梯依然是固定的，該用sychronized封裝的地方和上次也沒什么區(qū)別。

架構(gòu)角度：多了調(diào)度類，電梯也存在了繼承關(guān)系，但是由于我所實現(xiàn)的調(diào)度本身就是一個靜態(tài)的過程，而且兩種電梯除了look算法有差別外在第六次作業(yè)中基本也沒什么區(qū)別，因此主要的工作量依然是Strategy類中對于兩種look算法的實現(xiàn)。這里我也確實是繼承了我第一次作業(yè)的缺點，Strategy類不僅沒有減輕負擔反而還來了個加倍的工作量。其實這里應(yīng)該對策略類和電梯類的交互進行一下重構(gòu)，但是由于本人的懶惰就沒有進行。

該架構(gòu)的優(yōu)點：對橫縱向電梯的分離有利于后期的迭代，每個電梯對應(yīng)各自的請求隊列從而擁有良好的線程安全性。

該架構(gòu)的缺點：完全采用基準策略靜態(tài)分配，導致性能與使用自由競爭/其他優(yōu)化方案的架構(gòu)相比確實差了一些，其他缺點跟第一次一樣。

第七次作業(yè)（動靜結(jié)合）

1.架構(gòu)、調(diào)度器與多線程分析

到了第二單元的最后一次作業(yè)，我的目的也變得很簡單了，因為無需考慮后期的迭代了（可以為所欲為了哈），因此唯一的目的就是正確性（捎帶著性能）。第七次作業(yè)可能都會猜到會有不同樓座不同樓層的請求了，這就涉及到了中轉(zhuǎn)的過程了，我前兩次作業(yè)犧牲了一部分性能就是為了盡量保證線程的安全性，這次無論如何都不能偷懶了，因為電梯線程之間是一定會有交互的。

相對于第六次作業(yè)，第七次作業(yè)主要加入了如下新功能：電梯的屬性增加了，容量和爬樓時間由常數(shù)變成了可以改變的屬性，除此之外，橫向電梯多了一個屬性就是開關(guān)門信息，利用一個1~31的數(shù)字，將其二進制的每一位和A~E樓座對應(yīng)，代表著在某些樓座橫向電梯無法開門。不過這些其實都是可以用正常的方法就可以解決的，最關(guān)鍵的就是這次作業(yè)來了較為隨意的請求，這里就需要對該類請求做出特別的分析。其實，閱讀指導書可以發(fā)現(xiàn)，只要是不同樓座的請求，都可能會發(fā)生中轉(zhuǎn)過程。因此我構(gòu)建了一個SpecialRequest類，繼承官方提供的PersonRequest類，對于讀到的fromBuilding和toBuilding不同的請求，都轉(zhuǎn)化成SpecialRequest類型供調(diào)度器安排，而且SpecialRequest類中還多了一個屬性就是中轉(zhuǎn)樓層。

這樣整體架構(gòu)就出來了，比第六次多了一個SpecialRequest類。至于調(diào)度器的變化，這里確實是第七次作業(yè)最關(guān)鍵的地方：調(diào)度器在讀到PersonRequest的時候，如果發(fā)現(xiàn)這個請求的起始和目的樓座不同，那么就會重新new一個SpecialRequest對象，復制過來PersonRequest的所有屬性，同時計算需要中轉(zhuǎn)的樓層，根據(jù)目前所有樓層的電梯，在既存在橫向電梯且開關(guān)門信息符合該請求的樓層中選擇距離起始樓層和目的樓層之和最小的，找到中轉(zhuǎn)樓層后電梯在分析請求的目的樓層時，對于SpecialRequest的目的樓層就不是toFloor，而是transferFloor了。

對于多種電梯的選擇，我依然采用基準策略，但是在這基礎(chǔ)上根據(jù)自己的理解進行了優(yōu)化：在選擇電梯的時候，速度快容量大的電梯優(yōu)先選擇。采用這樣的策略在請求比較少的時候和自由競爭的性能差不多，但是在請求比較多的時候性能如何確實不太好說了。

如何實現(xiàn)整個中轉(zhuǎn)過程呢？這里我采用了動靜結(jié)合的方式。調(diào)度器本來只是輸入線程的屬性，但是由于從電梯中出來的請求可能是中轉(zhuǎn)的請求，因此該請求還需要重新分配電梯，因此需要給策略類也配備一個調(diào)度器，所以當中轉(zhuǎn)的乘客出電梯時候，策略類里會分析出該乘客目前的起始地和目的地，重新將一個新的PersonRequest扔進調(diào)度器內(nèi)，這樣就做到了靜態(tài)分配電梯，動態(tài)調(diào)度中轉(zhuǎn)請求。

在多線程角度看，調(diào)度器的功能之一就是根據(jù)讀進來的請求分配電梯，由于調(diào)度器封裝進了策略類內(nèi)部，因此策略類的工作并沒有變得特別繁重，而且電梯與電梯之間采用調(diào)度器進行溝通連接，線程安全方面也還算可以。但是由于中轉(zhuǎn)請求的特點，電梯線程的結(jié)束條件需要多考慮一下，前兩次作業(yè)電梯線程的結(jié)束條件是輸入線程結(jié)束且本電梯的所有請求處理完畢，可中轉(zhuǎn)請求的特點就是目前用不上的電梯過一段時間后可能會使用，因此電梯線程結(jié)束條件就改成了輸入線程結(jié)束且全部電梯的所有請求處理完畢。這樣就又導致了一個問題，不能光在輸入線程結(jié)束后喚醒所有空閑的線程，在電梯線程結(jié)束后也要喚醒全部線程，否則輸入線程提前結(jié)束，請求還沒有處理完，會出現(xiàn)先喚醒再沉睡的錯誤（當然這里的問題因代碼而異）。

2.代碼分析

UML類圖如下：

UML協(xié)作圖如下：

Statistics分析如下：

Metrics分析如下：

根據(jù)上圖可以看出，可拓展性幾乎沒有了，因此多個類的復雜度很高，而Strategy和Schedule兩個類正是整個電梯調(diào)度過程的核心類，復雜度過高對debug和bug的修復確實會有很大影響。

該架構(gòu)的好處：線程安全性高，動靜結(jié)合的中轉(zhuǎn)過程使得其既有基準策略的線程安全，又在性能上有了一定的優(yōu)化。

該架構(gòu)的缺點：真的不能再迭代了，再來其他電梯或策略是真的寫不下去了；在性能上不太穩(wěn)定，相比于自由競爭會差一些。

同步塊和鎖的分析

由于本人三次作業(yè)都在盡量避免線程沖突，優(yōu)化方案也都盡量在靜態(tài)過程中進行，因此在同步塊和鎖的這方面確實思考的不夠多。

首先就是輸出類，官方包提供的輸出類是線程不安全的，而且TimableOutput相當于一個全局變量，如果有多個位置同時調(diào)用它的println方法的時候會發(fā)生一些奇怪的事情導致時間戳不遞增。
因此，根據(jù)其他同學的想法，利用synchronized將TimableOutput.println封裝成同步方法。

其次還需要考慮的地方就是ArrayList本身是線程不安全的，所以如果兩個地方同時對ArrayList進行增刪操作的時候可能會發(fā)生異常，因此，前兩次作業(yè)僅僅是用synchronized鎖住了特定的數(shù)組，這樣可以避免該數(shù)組同時remove和add。等到了第七次作業(yè)，我采用了利用Collections.synchronizedList方法使數(shù)組變成線程安全的(代碼如下），因為由于一些優(yōu)化方法，需要對數(shù)組內(nèi)部的元素進行排序，然而同時數(shù)組也可能會增刪元素，因此我直接利用該方法讓ArrayList變成線程安全的可以免除后顧之憂，但是性能可能會略有下降。

        for (int i = 0; i < 10; i++) {
            Elevators[i] = new ArrayList<>();
            Collections.synchronizedList(Elevators[i]);
        }

互測/自測的策略+bug分析

跟第一單元相比，第二單元的輸入如果手動構(gòu)造會很麻煩，但是格式非常固定，由于我還不會什么高級語言，所以拿C隨便生成了一些數(shù)據(jù)。比如說第五次作業(yè)，只要按照指導書限定好每個數(shù)據(jù)（時間，樓層，樓座，ID)的范圍，就能夠生成很多請求；第六、七次作業(yè)只需要添加一些可以生成增加電梯的隨機輸出，再豐富一些細節(jié)就可以了。不過我不會寫評測機來驗證我的代碼的正確性，所以在生成數(shù)據(jù)的時候，一般只生成五六行，然后通過肉眼來觀察過程的正確性。最后生成50-100行的數(shù)據(jù)來觀察代碼是否會出現(xiàn)TLE或者RA等錯誤。如果產(chǎn)生了TLE這樣的錯誤，我一般會刪減一些代碼，盡量將錯誤鎖定在幾個特定輸入上，然后就開始捋自己的代碼執(zhí)行過程，這個過程確實是低效的，但對我來說是不得不做的。至于判斷是CTLE是RTLE，由于本人不會寫評測機，因此確實不容易確定，只能通過IDEA的debug功能和在各個位置進行print來判斷線程是否結(jié)束，哪里陷入死循環(huán)等等。至于bug時而出現(xiàn)時而不出現(xiàn)的問題，我也只能多做嘗試，盡量保存每次出現(xiàn)bug的輸入輸出，沒有什么巧妙的辦法。

互測的時候，我是利用自動生成數(shù)據(jù)+構(gòu)造刁鉆數(shù)據(jù)的方法，自動生成數(shù)據(jù)一般比較隨機，刁鉆數(shù)據(jù)一般是如下幾種：某種相同請求在同一時刻大量出現(xiàn)、同一座（層）樓有各種方向的請求、每層樓都有大量請求等等。由于不像第一單元利用肉眼就能看出對錯，況且本地輸出和評測機輸出很有可能不一致，所以這幾次互測我把每個數(shù)據(jù)都直接交到評測機上了。

對于產(chǎn)生的bug，主要是輸出類線程不安全的問題，也是因為寫完第五次作業(yè)后，清明節(jié)假期期間沒太思考，既沒看討論區(qū)也沒看水群，所以這里的問題給忽略了。

心得體會和反思

兩個單元的學習確實感覺收獲了很多。對于面向?qū)ο蟮睦斫飧由钊耄嫦驅(qū)ο蟮挠⑽氖荗bject-Oriented，根據(jù)我的理解，Object其實說白了就是東西，對于程序員來說，在用代碼描繪某件抽象的過程時，我們需要從中構(gòu)建出實體出來，換句話說要對代碼的功能和變量進行分類，對于一個需求，在學C語言程序設(shè)計的時候我們可能更加關(guān)注的是數(shù)據(jù)結(jié)構(gòu)和運行過程，而對于面向?qū)ο?，我們還要關(guān)注的有在實現(xiàn)需求的過程中，整個流程是由哪幾個東西來干，每個東西有什么特點、能干什么事情，東西與東西之間有什么聯(lián)系。當然，我的理解可能還很膚淺甚至是錯誤的，但是，我在學習OO課的過程中，確確實實能夠感受到自己的編程思想在發(fā)生一些轉(zhuǎn)變。

不過，需要提升的地方還有很多，比如說架構(gòu)設(shè)計和代碼實現(xiàn)上，盡管現(xiàn)在拿來題先開始設(shè)計架構(gòu)而不是直接敲鍵盤了，但是設(shè)計到實現(xiàn)的過程還很艱難，感覺設(shè)計的時候考慮的東西還不夠周到，導致實現(xiàn)的時候很多地方都得重新構(gòu)思。其次，關(guān)于每個功能的代碼實現(xiàn)，代碼總是超過限制的行數(shù)，覺得自己可能在框架上是面向?qū)ο蟮?/strong>，但是在具體敲鍵盤的時候依然是面向過程的，希望在以后的學習過程中能夠提升自己面向?qū)ο蟮哪芰?，能夠更好的利用面向?qū)ο蟮乃枷肜斫馐澜纭?/p>

除此之外，對于實驗課我也有一些反思。每次實驗課助教們都在對我們的作業(yè)架構(gòu)進行一定的提示，所以實驗課代碼確實是我們應(yīng)該借鑒和學習的，但是這兩個單元我都忽視了實驗代碼的重要性，導致一直在堆自己的*山。但是，不得不說，我經(jīng)?？床惶畬嶒灤a，盡管實驗代碼的架構(gòu)很清晰巧妙，但是我還需要很多時間去理解。所以很多時候自己的爛代碼就像是自己的孩子，而實驗代碼就像是別人家的孩子，不管別人家的孩子多么優(yōu)秀，我只愿意呵護關(guān)心自己的孩子。我這個比喻并不恰當，但是確實希望以后能夠多理解理解實驗代碼，畢竟實驗代碼的架構(gòu)和實現(xiàn)方式確實是教科書式的，如果能熟練應(yīng)用在自己的作業(yè)中會更好。