程式語言學就像是程式設計這門學問的總綱,它描述了各門各派程式語言的歷史演進,並且加以分門別類,也介紹了各種程式語言的特性及優缺點,還有程式語言之間的血統關係等。

雖然它不介紹特定程式語言的撰寫技巧,卻講述了各類程式語言最主要的精神,了解這些事情,能夠加快程式人在學習特定程式語言時的速度。

演算法加資料結構等於電腦程式
程式語言的作用,是讓程式人得以透過程式語法來描述解決問題的方法,但終究程式人還是必須知道如何解決問題。Pascal語言的發明者Niklaus Wirth說過:「演算法加資料結構等於電腦程式。」

所謂的演算法,基本上就是解決問題的一系列步驟,而在解決問題的過程中,需要搭配一些以特定方式記錄、操作資料的結構,它們就是所謂資料結構。從這樣子的描述,不難判斷資料結構及演算法在電腦科學裡的重要性,以及它們與程式設計的高度相關性。

對大多數的程式人而言,學習演算法及資料結構的目的,往往不在於設計出新的、更有效率的演算法及資料結構,而是在於了解既有演算法及資料結構,將它們應用在日常的程式設計工作中。

資料結構這門學問中,探討各種常用的資料結構,例如陣列、鏈結串列、雜湊表(Hash Table)、二元樹……等。每種資料結構都有適合運用的地方,也有不適合運用的地方。做為程式人,必須對常用資料結構的特性有一定的了解,並且知道應用它們的正確時機。

舉個例子來說,倘若你是一名Java程式人,碰上一個需求,需要判斷系統給定的一連串元素,是否重複出現。在檢視別人程式碼的經驗中,我看到一些程式人,利用了java.util.ArrayList這個類別,逐一地將每個元素加入ArrayList中。在加入前,利用indexOf()函式判斷是否已加入ArrayList中,倘若已在其中,便是重複的元素。

從功能性角度來說,不能說這樣的寫法有問題,因為它的確可以達到目的。但是,當要處理的元素一旦多起來的時候,這樣子的寫法就會引發效能的問題。

倘若對資料結構這門學問有基本的了解,就會明白,ArrayList的indexOf()是逐一的比對陣列中的元素,想要找到特定的元素,它的時間複雜度是O(n),也就是說,當元素個數為n時,最多要花n次才能完成比對動作。

針對同樣的需求,如果你懂得運用雜湊表,就會知道同樣的需求,轉而使用java.util.HashSet,因為HashSet所提供的contains()函式,能夠在常數時間內完成檢查是否存在的動作。當要處理的元素個數一旦變多時,ArrayList的方案執行效率顯然就緩慢許多。這便是程式人高下判定的分野所在。

選用資料結構時,必須檢視各種操作使用到的頻率
透過資料結構這門學問,我們可以明白常用的資料結構、應用的時機、應用時的效率特性……等,這些多半也就能滿足開發的需求。對大多數的程式人來說,並不會使用到太多複雜的資料結構,我們會需要培養的,是那種對於各種資料結構的一般性認識,使得我們在處理資料時,能夠具備依據應用情境挑選資料結構的意識。

同時,我們也藉此建立處理資料時的成本概念,我們會明白,同一種操作(例如判斷資料是否為重複的元素),透過不同的資料結構都能達成,但是會付出不同的時間或空間代價。

當你在應用程式中選用資料結構時,必須綜合性地檢視各種操作被使用到的頻率,以決定究竟要使用那種資料結構。假設某種資料結構新增元素速度慢、搜尋元素速度快,在你的應用中,卻是大多數時候都在新增元素,少數時間才會需要搜尋元素,那麼此種資料結構便不適合你的應用。假如,選擇另一種新增元素速度快,即使搜尋速度慢的資料結構,反而會更適用。

演算法像是一本「型錄」,記錄了先人的智慧結晶
許多程式語言都搭配所謂的容器庫(Container Library),提供時常會運用到的資料結構,對於程式人而言,並不需要重新造輪,但這並不意謂著程式人就沒事可做了,程式人真正的責任,在於選擇適合的容器處理資料。
在我的經驗中,很常見到程式人從頭到尾使用像Vector(C++中的STL)或ArrayList(Java/C#)處理所有的資料,如此一視同仁地只求達成功能,而不細究實際執行效率的程式碼,說實在的,還真是可怕!

演算法對程式設計的影響,和資料結構十分相像,它能告訴我們許多已經被發展出來解決問題的方法,從這個角度來說,它也像是一本「型錄」,記錄了先人的智慧結晶。

既然它是一本型錄,那麼也就不要求將所有演算法的細節、步驟記錄於腦中,只需要了解各種需要被解決的問題類型,例如搜尋、排序、最短路徑、字串比對……等,同時對相應的演算法特性及時間複雜度,有一般性的認識。

這能夠讓你在撰寫程式而面臨到問題時,可以很容易地意識到這是一個常見的演算法問題,同時知道如何到書本上查閱,找出相對應而且適合使用的演算法,再加以實作來解決你的問題。

善用演算法,也等於培養了程式人解決問題的成本意識
同樣的,我也認為演算法這門學問,對程式人而言,還有一個重要的影響,便是培養解決問題時的成本意識。

貫穿演算法的兩大支柱,便是「時間複雜度」和「空間複雜度」。它們代表著解決問題時,隨著待解問題之資料的規模變大,所需執行時間及空間變化的趨勢。

培養成本意識對程式人來說,是很重要的一件事。這代表程式人在設計程式時,會無時無刻地考慮到自己所做的設計、所寫下的程式碼,究竟需要付出多少代價。具有時間複雜度和空間複雜度觀念的程式人,就等於擁有兩種評估工具,得以從這兩個角度評估自己的設計,進而持續地改善設計。

即便你只是個總是和資料庫打交道的程式人,你的資料不會使用什麼特定的結構來儲存,而你也總是直接利用SQL語法打撈和計算需要的資料。但是,具備成本觀念的程式人,會設計出儲存空間較少、運算處理速度快的資料庫表格及SQL述句。這是成本觀念之所以重要的原因。

搭配理論基礎,讓程式技巧更臻上乘
行文至此,大略介紹完一般電腦科學的基礎課程和程式設計的關聯性。透過本系列的介紹,希望分享身為一名電腦科學本科的程式人,在實際的軟體開發工作中,究竟怎麼運用電腦科學的基礎學問。

這代表基礎學問並不是不食人間煙火、只唱高調的理論,而是實際上可以對程式設計工作產生助益的理論基礎。如果讀者也是電腦科學本科的程式人,那麼這些經驗可供參考;倘若並非電腦科學本科的程式人,而且有意自行研讀電腦科學的相關背景課程,那麼希望透過本文提供一個大略的導覽。

有了高超的程式設計技巧,再搭配適當的理論觀念,無異於如虎添翼。

專欄作者

熱門新聞

Advertisement