知識社群登入
位置: 艾鍗學院 Blog > 專業論壇 > 討論
訂位系統 v2.0 Builder 110320 效能提升版 ( C程式設計作業--for 就業班同學)
(naruto, naruto@hotmail.com, 2011-03-21 00:34)  1  人
1樓
seatingReservation.h

seatingReservation.c

main.c

實習課和大家一起討論這個系統的架構和功能時，發現我原先採用的架構有個重大的毛病！
我把排序的步驟實作在訂位這個極為重要的功能裡。
換句話說，我在每一次加入訂位資料於串列中時，順便進行排序。
也因此每個訂位步驟需要O(n)，如果已經訂位的人越多，則花費時間越多。
然而依商業考量，這是極不明智的。
什麼動作都可以慢，就是訂位時不能慢!
基於此，所以我把大家討論的結果加以實作，誕生了這個效能改良版。

排序的部分採用Quick sort，以大黑狗老師的源代碼為藍本修改成串列版。
Linked List部份為了排序的實作方便，採用雙向鏈結。
(如果採用單向鏈結，在SWAP節點的部分會花費多餘的時間於尋找 previous node，
其效能將大打折扣，甚至會比Bubble sort還要慢！)
另外，為了節省動態配置記憶體與釋放記憶體的時間，所以採用另一個鏈結來接收不要的記憶體空間。
如果訂位時需要記憶體空間，就可以直接從這個鏈結中取得，而不用去動派配置，除非沒有空的空間可用。
這樣一來便可節省malloc()函數與free()函數的呼叫。

效能比較：
原先版本在訂位時需要花費：
(顯示空位)+訂位
O(n^2)+O(n)

改良版在訂位時需要花費:
(顯示空位)+訂位
(O(nlogn)+O(n))+O(1)

在時間複雜度上提升了不少效能。

這個版本的程式我已經在Ubuntu上用GUN C compiler編譯執行測試過了，
加上 -Wall -Werror參數也沒有error產生，功能如預期中的想像進行，
沒有跑出奇怪的結果，應該是沒有太大的問題。

目前已知問題：
1.由於採用雙項鏈結，再加上Quick sort在排序時所需要的額外空間，所以空間複雜度並沒有辦法比原先的版本優良。
換句話說就是利用空間來換取時間。

2.離開程式前，並沒有去釋放動態配置的記憶體空間。

3.寫檔動作是實作於離開程式前，這並不理想。萬一程式當掉，之前的輸入全部都會泡湯。