iT邦幫忙

2024 iThome 鐵人賽

DAY 11
0
Software Development

六邊形戰士程式設計系列 第 11

D11 - 樹狀搜尋問題 複雜度分析篇

  • 分享至 

  • xImage
  •  

請搭配 D10 - 樹狀搜尋問題 實作篇 閱讀。

衡量程式寫法好不好,複雜度是很重要的一環,然而該如何分析複雜度呢? 複雜度有時候是很主觀的,舉例來說,昨天我們在結構化程式設計的實作中使用了「queue」,在函數式程式設計的實作中使用了「recursive」。對於不熟悉這兩種寫法的讀者而言,也許讀起來會有點障礙,覺得好複雜,但對於熟悉的讀者來說,在這兩方面就不會造成困擾。

然而在這個凡事講究真憑實據的時代,有沒有更客觀的方式能可以作為衡量程式碼複雜度的參考呢? 剛好我前陣子在看的《Refactoring at Scale》一書中就有提到兩種方法來分析程式碼複雜度。

Halstead Metrics

複雜度 = ( 運算子有幾種 / 2 ) * ( 運算元有幾個 / 運算元有幾種 )

我自己粗略估計兩種寫法的比較如下

結構化 函數式 函數包含型別
運算子有幾種 17 14 16
運算元有幾種 17 11 12
運算元有幾個 33 20 31
複雜度分數 16.5 12.72 20.6

從 Halstead Metrics 的角度上來看,我們可以只要遵守 DRY 原則,避免重複的程式碼片段,就可以降低複雜度。比較兩種設計範式,如果隨著程式規模增加,型別能被重複利用,函數式就會比較有優勢,反之則使用結構化即可。

Cylomatic Complexity

Cylomatic Complexity 翻譯成中文的話是循環複雜度
但其實它不是單單計算循環的數量,而是參考以下公式

分支的數量(迴圈開始、if else、switch) - 結束點的數量 + 2

參考上面公式則可以算出

結構化 函數式
迴圈 2 -
if 1 -
三元判斷式 - 1
結束點 2 1
複雜度 3 2

從 Cylomatic Complexity 的角度上來看,我們可以藉由以下做法降低複雜度

  • 盡量減少不必要的迴圈與 if else
  • early return

比較兩種設計範式,多少可以看出在能善用 early return 解決問題的場合,結構化程式設計會佔據優勢,然而無奈的是剛好這個問題函數式可以用遞迴的方式巧妙地取代迴圈,使程式碼更簡潔,因此函數式的複雜度相對較低。

總結來說在解決這個問題上,我個人會更偏好用函數式一些。


上一篇
D10 - 樹狀搜尋問題 實作篇
下一篇
D12 - 樹狀搜尋問題 效能分析篇
系列文
六邊形戰士程式設計30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言