小殘的程式光廊

說明本文針對一些 JavaScript 效能相關的文章之理論進行實際的測試與驗證，結果有些符合預期，有些則意料之外。測試環境瀏覽器如下： Chrome：18.0.1025.168 m Firefox：12.0 Safari：5.1.5(7534.55.3) Opera：11.62 IE8、IE7 為使用 IE9 切換模式 變數存取JavaScript 變數存取具有以下特性： 使用變數時會透過作用域鏈 (Scope Chain) 自動判斷其所屬範圍，會從目前區域變數查找，逐漸往外圍查找。對變數存取屬性 (點符號.) 會進行查找而消耗時間。 根據以上原則，我們可以推論出一些增加效能的可能方法並實際測試： 使用區域變數，減少變數查找次數，包含作用域鏈與存取屬性，盡可能的使用區域變數。 Chrome Firefox Safari Opera IE9 IE8 IE7 存取區域變數 14.9 15.4 62.8 58.3 30 25 30 存取全域變數 13.8 17 73.9 74.1 43.7 11165.7 11208.6 存取變數屬性 15.3 12.9 80 ...

簡介Iterative Method 中文翻譯作迭代法或疊代法，而在數學領域和電腦程式領域的定義有些不同，數學領域的迭代法指的是無法使用公式一次求解，而須反覆運算求出近似解；而在電腦程式雖然亦有反覆運算的含義，但一般指的是迴圈解。 迭代法透過設定一個初始值開始反覆運算，最後求出答案，是算是一種 Bottom-Up 的模式，通常會和遞迴作比較，實作方式簡易區分如下： 迭代：使用迴圈實作。 遞迴：函式推疊呼叫。 基本上相同的演算法如果能夠直接使用迴圈，因為不透過函式堆疊，效能會比較好。相對於迭代，遞迴就算是一種 Top-Down 的模式。以階乘為範例： 遞迴123456function Factorial(n) if n == 1 return 1 end if return n * Factorial(n - 1)end function 遞迴的思考模式，求 n 階的時候當作 n - 1 階已知，相乘即是答案，n - 1 的如何求在 n 階的時候無須理會，就像上級要交由下屬去處理的 Top-Down 模式。 迭代1234567function Factorial(n) sum = ...

資訊 路徑：Tournament \ 1-16 \ 2 - Inv 2001 Semi A+B \ MatchMaker 分數：250 題目程式介面123456Class Name: MatchMakerMethod Name: getBestMatchesParamaters: String[], String, intReturns: String[]Method signature:String[] getBestMatches(String[] members, String currentUser, int sf); 說明線上交友網站需要透過程式來自動找出條件匹配的對象，會員會先輸入一些資料做為依據，當會員要求配對時，程式會回傳一個符合的對象清單，對象的符合項目必須大於等於設定的相似度 (similarity factor)。現在程式會先輸入會員資料、目前會員和相似度，會員資料如下格式： 1{名稱} {性別} {對象性別} {資料1} {資料2} ... 例如 1BETTY ...

拍攝時間：2012 年 4 月 8 日 今天一早就坐車來到陽明山，從劍潭捷運站坐小 15 的公車，在菁山小鎮這站下車，從旁邊的登山步道開始爬。 很久以前曾經也在裡這下車過，不過才走幾步就開始下大雨，就又下山了… 從步道往擎天崗，路程記得是 2 公里多 山旁邊有流水，上游有絹絲瀑布 這邊的步道相當好走 到了絹絲瀑布，可惜距離很遠，只能遠遠的拍照 這裡河流的石頭都是黃色的，但是可以看到沒碰到水的部分是正常的顏色 不是秋天不是楓，萬綠叢中一點紅 很快的就走到擎天崗了 迎面而來的是一群牛 擎天崗上的草原有很多牛正放出來吃草，同時也有很多遊客 大牛一直舔小牛，是幫他洗澡？ 拍著拍著，意外拍到奇怪的畫面 之後就到了遊客中心附近吃自備的午餐和休息，一堆人在等公車要下山。休息完後，我們用「走」的往冷水坑前進，結果走了好久的路… 不過總算是走到了，這裡雖然叫做冷水坑，但其實是溫泉，這時候有一堆人在泡。另外溫泉的水好像是每隔一段時間會放出來，不是一直流的。 在這裡有個管理員，好像叫劉先生吧？相當的熱情，還現場高歌一曲『小草』，看他笑容多燦爛 原本要往上走七星山，結果似乎開始下雨，就改往下去菁山吊橋 路 ...

簡介最大子序列 (Maximum Subarray 或稱作 Maximum Subsequence) 為在一個具有正負數陣列當中，找出一段連續的元素總和最大，這個問題又分為一定要取值或可不取。實作方法有很多種，這裡說明四種實作方法，分別為暴力法、改良式暴力法、Divide and Conquer 和 Kadane’s 演算法 (Dynamic Programming)，其中 Kadane’s 實作取值和可不取值兩種版本，其他為一定要取值版本。 演算法暴力法最簡單直覺的想就是將所有可能的開始和結束範圍都算過一遍即可，[0] ~ [0]、[0] ~ [1] … [0] ~ [N] … [N] ~ [N] 的總和找出最大。 改良式暴力法然而在上面暴力法計算，[0] ~ [N] 的總和時，其實過程中 [0] ~ [0]、[0] ~ [1] … [0] ~ [N] 的總和也已經同時計算了，所以只需計算 [0] ~ [N]、[1] ~ [N] … [N] ~ [N] 即可。 Divide and Conquer如下圖所示，Divide and Conquer 的基本概念是，將數列分成兩塊，各自回報 ...

拍攝時間：2012 年 4 月 7 日 隔天要去陽明山爬山，今天將要在台北親戚家住一晚，這天下午先來到士林官邸逛逛。 地址：台北市福林路 60 號 電話：0228836340 從捷運士林站二號出口走一段路，過一兩個路口就到了，相當方便。沒來過這裡，聽名稱一直以為是棟房子而已，沒想到是個花園。 今天這裡就是很多的花，一朵盛開的花 除了花之外還有一些園藝造景 季節似乎已經過去，花少了很多 不知道是甚麼花，一串一串的開 粉紅色的玫瑰花 水池造景 夏天到了，落花不是無情物，化作春泥更護花 抓住春天的尾巴 這時候人已經少了很多，稍早時後四處都是陸客 走到這裡的時候正巧噴水池開始噴起來 路旁的樹木樹皮很特別 在教堂對面的中式庭院 螃蟹造景，還是隻煮熟的螃蟹 新蘭亭 這時候這裡正在展覽蘭花 有各式各樣的蘭花 這也是蘭花 這作品似乎較作聖誕樹，有像嗎 園藝展蘭館，結果在裡面沒拍到甚麼 走到了另一邊，有一顆奇特的楓樹，樹幹完全被別的植物包覆住，秋天來的時候也許會更漂亮 這裡還有生態區 很多種類的水生植物 繞了一圈看到官邸了，不過時間太晚已經關閉，無法進入 而且進去還要額外的門票，所以隔著柵欄拍幾 ...

簡介二元搜索法 (Binary Search) 又稱折半搜索，搜索演算法的一種，可使用 Divide and Conquer 或直接使用迴圈 (迭代) 來實作，搜索的目標資料必須是已經排序過的 (以小到大排序為例)。其概念是每次挑選中間位置的資料來比對，若該資料小於目標值，則縮小範圍為左半部，反之亦然；因此使用這個方法每次比對後都可以濾掉一半的資料，以增快搜索速度。過程依以下步驟進行： 取出搜索範圍中點的元素。 與搜索目標比較，若相等則回傳位址。若小於則將左邊邊界改為中點右側，若大於則將右邊邊界改為中點左側。 左邊邊界不超過右邊邊界(還有資料)則重複以上動作，若已無資料則回傳-1(找不到)。 流程範例如圖所示，例如搜索值為4的元素： 分析 最佳時間複雜度：O(1) 平均時間複雜度：O(log n) 最差時間複雜度：O(log n) 空間複雜度：O(1) 虛擬碼迭代12345678910111213141516function search(list, target) var left = 0, right = list.length - 1 while left <= ri ...

拍攝時間：2012 年 4 月 4 日 淡水紅毛城今天來到了淡水，一大早店家都還沒開，街上也都沒有人，不過今天不是來這逛街的，目標是紅毛城。 地址：新北市淡水區中正路28巷1號 電話：02-2623-1001 有人在這裡進行帆船衝浪，今天風很大，船的速度也相當的快速，看到他們快速的來回兩岸 之前通常都走到星巴克就回頭了，不過原來繼續走還可以到別的地方，經過了這條林蔭小徑，樹低垂到快要進水裡，很特別的景色 走了一段路之後，走出到大馬路的對面就看到紅毛城 之前要門票，現在已經不用門票了 雖然叫做紅毛城，不過比較像是官邸之類的建築 進入第一棟建築，裡面有牢房，關著不知名的人物 中庭有位高大的外國人 威廉王子號，大航海時代的船艦 客廳的擺設保有歐式的風格 就像電影的場景一般 書房 高級的餐廳，不過不能點菜 那個時代的家具看起來還真是高級 這是…下午茶？ 在附近吃完飯後，又朝著一滴水紀念館前進，途中經過這裡順手拍了一張，不過後來沒有進去 一滴水紀念館 地址：淡水區中正路1段6巷30號 電話：(02)2626-3350 實際上一滴水紀念館是在和平公園裡面 和平公園紀念碑 公園中的造景 ...

資訊 路徑：Tournament \ 1-16 \ 1 - Inv 2001 R1 \ Prerequisites 分數：1000 題目程式介面12345Class Name: PrerequisitesMathod Name: orderClassesParameters: String[]Returns: String[]Method signature: string[] orderClasses(string[] classSchedule) 說明學生在大學修課時，會遇到複雜的先修課問題，也就是某些課會有要求需先修完另外某些課後才能修，所以我們來寫一支幫助排定修課續順的程式。程式會輸入字串陣列，每一筆資料表示課程與此課程的先修課，格式大致如下： 1{系所代碼}{課號}: {先修課} {先修課} 例如 1CSE111: CSE110 MATH101 請依據以下規則排出修課的順序： 課程的先修課必須全部修過後才能修。 同時有多個課程可以修時，先修課號數字小的。 承上，如果數字相同時，則先修系所 ...

簡介快速排序法是排序演算法的一種，使用 Divide and Conquer 的演算法來實作。其概念是從數列中挑選一個基準點，大於基準的放一邊，小於的放一邊，如此循環最後可完成排序。過程依照以下步驟進行(遞增為例)： 數列中選擇一元素作為基準點 (pivot)。 小於此元素的移至基準的左邊，大於此元素的移至右邊，相等的任意放。 基準點左邊和右邊視為兩個數列，並重複做以上動作直到數列剩下一個或零個元素。 流程範例如圖所示： 實作的方式除了一般使用額外的暫存數列之外，也有使用較少額外空間的 原地 (In-place) 方式，In-place 的方式主要概念是將基準點暫時移到最右邊，小於基準的移至數列一端並記錄遞增索引，最後將基準點換回索引位置，過程依照以下步驟進行 (遞增為例)： 數列中選擇一元素作為基準點 (pivot)，並與最右邊的元素交換位置。 建立一索引指向最左邊元素。 小於基準的元素與索引位置的元素交換位置，每次交換後遞增索引。 完成後將基準點與索引位置的元素交換位置。 基準點左邊和右邊視為兩個數列，並重複做以上動作直到數列剩下一個或零個元素。 流程範例如圖所示： 基準點 ...