捷運轉乘

前陣子花了點時間寫了一個簡單的免費 iOS App,叫「捷運轉乘」,現在可以直接在 App Store 下載,也可以在 Github 上取得程式碼

這個 App 做的事情很簡單,就是幫你計算兩個台北捷運站之間經過車站最少、或是轉乘次數最少的路徑。由於裡頭包含了松山線的資料,在捷運松山線通車、台北捷運路網變得複雜之後,如果你也開始有不知道應該怎麼轉搭捷運的困擾,希望這個 App 可以有些幫助。

故事是這樣:今年年初訓練公司新人寫程式的時候,由於 Etag 開始營運時有不少糾紛,於是安排了一個簡單的練習—如何計算兩個收費站之間的費用。你也知道一個 iOS 工程師大部分的工作都在做些什麼接 API 啦、刻 UI 之類的工作,看老闆的喜好把 UI 改過來又改過去,做一些需要演算法的練習,知道有些應用還是得了解演算法,還頂重要的。

這樣的程式很簡單:把每個收費站都當做一個 node,收費站之間透過高速公路連接起來,整個路網就是一個 graph,資料建立好,就用遞迴一路去找從起點出發可以連結到哪些地方,如果走到終點,就是一條可行的路線,如果發現走到曾經走過的地方,就代表開始繞圈,我們就放棄這條路線;接下來,就把找到的可行路線排個序。

不過程式寫完,就發現以手上的資料,要真的能用的高速公路路線規劃的 App,還有別的困難。

一來,我們雖然可以取得通行費率,知道兩個交流道之間最便宜的路線是那條,但是我們沒有這條路線會花上多少油錢的資料,由於東西向國道免通行費,所以我們很有可能推薦一條經過東西向國道的路線,雖然通行費便宜,但可能更花油。

再來,有些交流道只能上不能下,或反之,如果沒有考慮這點,那麼程式就會算出一條實際上根本不可能走的路線。而由於國一與國一高架路線是重疊的,走國一的時候,可以在很多地方上下國一高架,這樣也會產生很多不同版本的路線,每條路線大概也只差個一兩毛錢,但出現很多條在不同地方上下國一高架的路線,也讓 App 看起來很難用。

順道一提,在寫 Etag 的練習時,我們還發現高公局網站上計算長途優惠的方式,與說明不太一樣。高公局說,每天的長途里程優惠,是在里程超過兩百公里之後,兩百公里之內是每公里 1.2 元、兩百公里外每公里 0.9 元,但如果你是按照通行費率表上的里程數(通行費率表上有牌價與里程兩項資料),套用這個公式,就會跟計程通行費試算網站算出來的不一樣。因為這個網站實際上是用牌價,而不是用里程數計算長途優惠,公式是:(牌價 – 240) * 0.75 + 240。

把這個程式直接換上台北捷運的資料,就可以計算捷運路線了。由於今年蘋果推出 Swift 語言,要掌握一門程式語言,總要寫點練習,所以把原本的 Objective-C 程式用 Swift 改寫。寫下去才發現,如果你用 Swift 寫程式,寫到 Array 的相關操作的時候,怎麼設定 Optmization Level,對程式速度的影響還差真多呵。

像上面提到的,我們在走到某個點的時候,就需要檢查這個點是否已經走過了,我們會把走過的點放進一個 Array 中,然後檢查現在所在的點是否在這個 Array 裡。在 Objective-C 裡頭,我們會呼叫 NSArray 的 -containsObject: 這個 method,Swift runtime 則提供了 contains 這個 function 可以呼叫。我們來寫一段小程式:檢查 1 是不是在 [1,2,3,4,5] 裡頭,執行一萬次,在我的 MacBook Pro 上結果如下:

現在專案設定是 Xcode 的 Debug build 預設的設定,Optmization Level 設成 None, -containsObject: 需要 0.03 秒,而 contains 要 0.442 秒,兩者差了 15 倍。

Screen Shot 2014-11-30 at 4.02.54 AM

我們現在改一下設定,把 Optmization Level 改成 Fastest。

Screen Shot 2014-11-30 at 4.04.32 AM

改了設定之後,-containsObject: 加快了一倍,只需要 0.012 秒,而 contains 只需要 0.007 秒。相較修改 Optmization Level 的前後結果,contains 的速度快了 63 倍。

Screen Shot 2014-11-30 at 4.03.29 AM

感覺起來,如果不想讓生命花費在等候上,在寫 Swift 的時候,似乎就算是 Debug build,也該把 Optmization Level 設高一點哩。

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.