原文題目 https://leetcode.com/problems/add-two-numbers/
這題是個基本的 Linked List 考題，如果題到這類型的 List 題目，若題目沒特別說的話，就一律想成是 Single Linked List 了．其實，我個人不是很喜歡 List 考題，原因是大部份的問題都蠻無聊的，可能就在 List 上把元素搬來搬去，而且不一定會有一個很好的邏輯來搬這些元素，所以就會造成一個 function 寫的長長的．像這一題就是這樣．
題目給了兩個 input list，要把每個元素加在一起後，然後輸出一個最後的 list．其實也蠻簡單的，你只要在這兩個 input list 上一個一個元素去拜訪，然後把加起來的答案寫到新的位置上，同時再注意進位的事情．並且你也要考慮到兩個...
#37 資料庫基礎 - Clustered Index 與 Non-clustered Index
在編號 #33 的文章中介紹了什麼是 Index．這可以說是資料庫對資料能快速尋找的主要方法，基本上也是一個用空間換取時間的方法，也就是為了更快速地找到資料，於是犧牲了更多的硬碟儲存空間來達成這件事．也因為如此，所以資料庫引擎也需要有相對應的功能來妥善管理這些特別的儲存空間．然而，儲存空間的內容不同也會影響不同的管理方法，所以這一篇文章將來介紹不同的儲存空間 - Clustered Index 和 Non-clustered Index．
如果你曾撰寫過資料庫應用的相關程式或是你本身是資料庫管理員，相信你一定聽過 Clustered...
#36 Code Review - 檢視你的程式碼
不論是寫好一個新的功能或是修改 bug，在程式碼都能正確執行並且在 check-in 到 source control server 之前，一定都會有一個 code review 的動作．這件事情通常是由比較資深的人員或對整體程式較為熟悉的人員來執行．Code review 帶來的好處很多，在這裡不一一描述，這對比較資淺的人員或新進的人員來說是一件好事．透過 code review，新進或資淺的人員可以比較快進入情況．有時我們進入了一個龐大程式碼專案，短時間之內蠻難完全了解所有細節和該團隊寫程式碼的文化，所以透過 code review 來了解程式碼，也是一種學習．
如果你工作的地方有執行 code reivew 的動作，真的恭喜你，畢竟教學相長，透過檢視彼此的程式碼是一種良好的學習方式．因為這跟團隊文化與團隊技術能力與要求上有很大的關係，所以...
#35 Coding面試 - LeetCode #94 Binary Tree Inorder Traversal
這題目出現在這 https://leetcode.com/problems/binary-tree-inorder-traversal/
如果要考 Tree 相關的題目，這一題算是相當經典的考試題目了．我想經典的原因就是 Tree inorder traversal 是資料結構課本裡面一定會教到的內容．大部份的課本裡面都會提供 recursive 的方式來做 inorder traversal，其程式如下
public List<int> InorderTraversal(TreeNode root)
{
...
#34 資料結構 - 非電腦科系的工程師們，你們體會多少了呢 ?
我第一次念資料結構時是因為準備台灣的資工研究所考試而念的，當時為了考試再加上時間也不夠多，所以念的很匆忙，沒有太多的時間思考著這門課程的精華．後來，念了研究所之後，研讀了一些學術論文，才慢慢了解到資料結構的精華．在許多學術論文裡都是討論著許多真實世界上的問題，通常這些問題會用一個數學公式或模型來表示，所以接下來的內容討論就可以直接在這數學公式或模型上直接去模擬．而這類的數學公式或模型若要用電腦程式來表達時，通常會發展出適合的演算法與資料結構．所以，這類的論文看多了之後，反而有幫助自己漸漸了解資料結構的精華．
基本上，電腦有二個基本的東西，一個運算器，一個是儲存空間．運算器就是大家所知的 CPU，而儲存空間就是記憶體和硬碟，其中記憶體是速度快但記憶時間較短，而硬碟是速度慢但記憶時間較長．這兩個東西你可以想成他們是長長的紙條，運算器可以在這長長的紙條上寫下資料，也可以讀取資料．
資料結構基本上就包含了兩件內容，一個是你需要用的資料是要寫在紙條上的何處，另一個就是如何在這些資料之間進行讀取或寫入．舉個例子，之前的文章提到...
#33 資料庫基礎 - 什麼是 Index
Index 在資料庫的領域裡算是很基本且極為重要的項目，因為它幫助我們可以在龐大的資料裡快速地找到資料．這一篇文章就來說明 Index 運作的原理．
Index 也是一種典型的用空間換取時間的做法．這感覺就像是書籍裡最後面會有一些專有名詞在那一個頁數中可以找到，透過書籍的 Index，你可以很快找到你要找的專有名詞．同樣的，在資料庫裡也是類似像這樣的做法．資料庫引擎可以將你感興趣的資料製做成 Index，如此一來，資料庫引擎只要在 Index 上尋找目標，就可以很快速地得知該筆資料的位置是在資料庫檔案裡的什麼地方．這些就是 Index 概念．舉個例子，在資料庫裡有一個學生資料的表格，表格的...
#32 資料庫基礎 - 資料讀取的成本評估
在前面的文章裡曾提供當資料庫引擎要儲存資料時可能有三種方式可以選擇，分別是 heap file, sorted file, 和 hashed file.
Heap file基本上就是沒依照任何的規則來儲存資料，也就是說你先把資料A寫進去，然後再寫資料B，則自然而然地 A 的位置就會在 B 的前面．正常情況下，我們似乎不太希望用這種方式來儲存資料，因為它對資料搜找的速度上並沒有什麼幫助．
所以，假設資料一共分佈在 p 個 pages，然後每個 page 的讀取或寫入的平均時間為 d，那麼在尋找資料時所花費的成本便是 p*d，這是以最壞的情況來看的，因為我們無法知道我們要找的資料是在前面的 page 還是後面的 page，所以在成本評估時就用最壞的情況來看．
如果做 insert 動作，heap...
#31 程式該怎麼分辨好壞呢 ?
上個星期看到一篇短文，文章網址如下
http://buzzorange.com/techorange/2015/10/08/the-six-most-common-species-of-code/
這文章很有趣，它列出不同的人會如何寫出同一個 function．
看到學生寫的就是很標準的學生該有的答案．儘管 recursive 的寫法會有 call stack overflow 的問題，但對一個學生來說，重點是練習 recursive 的思考，所以這樣寫蠻好的．
看到由 Hackathon 寫出來的答案，哈哈，老實說，我真的是打從心裡笑了出來．這個笑可不是嘲笑的笑，而是一種打從心裡佩服的笑，尤其是看到那一句註解 // good enough for the demo
再來看看新創公司寫出來的，其實看不出來這和學生寫的有什麼大差別．也許作者在暗示些什麼?
再來看看大公司．還真的是有大公司寫法的樣子．你是否曾想過大公司的寫法為何是這樣子呢...
#30 Coding面試 - LeetCode #125 Valid Palindrome
題目的網址: https://leetcode.com/problems/valid-palindrome/
這一種題目算是蠻基本的，以前在台灣找工作時曾遇過有個公司的考卷出這一題，而在美國找工作時，目前還沒遇過有人考這一題或是相似的題目．
基本上，這題就是要寫一個 function 來驗證輸入的字串參數是不是 palindrome．所謂的 palindrome 就是字串中第一個位置和最後一個位置的值是一樣，第二個位置和倒數第二個位置的值是一樣，以此類推．所以一個很簡單的想法就是只要一個 for loop 就可以做完這樣的工作，而且不需要線性成長的空間，因此時間上是 O(n)，空間上是O(1)，這是對答案的要求了．
但 LeetCode 出的這一題有一點點小小的變化，因為輸入字串中可能會有其他的符號，而這些符號是不列入規則的，所以題目上寫 "A...
#29 測試，該如何開始 ?
對一個好品質的軟體而言，測試的確是件很重要的事情．你寫的程式是否能在你假設的情況下做出正確的反應，這也是許多軟體工程師們的挑戰．一般較年輕的軟體工程師們往往過於著重在寫程式的技巧，所以常常忽略了花時間在學習如何測試你的程式．其實，軟體測試的學問完全不亞於一般的軟體開發所需的知識，而很多人可能會有一個先入為主的想法，那就是程式如何都寫不出來了，那學如何測試有什麼用呢 ? 聽起來好像還有幾分道理，至少在十多年前我是這樣想的．後來接觸多了之後也漸漸發現，如何不知道如何測試的話，那你怎麼能知道你寫出來的程式一定能用呢 ?
一般來說 (至少在我的工作環境下是如此)，軟體工程師自己寫出來的 function 一定要自己寫好 unit test．這是蠻重要的事情，因為除了你，應該沒有人比你更了解你寫的...
#28 資料庫基礎 - 存取 Page (Hashed File)
前面兩篇文章提到了存取 page 的兩種方式，在這一篇文章裡要介紹的是另一種方式，我們稱它為 hashed file．聽到這個名字，你可能已經猜到這是和 hash function 有關係的儲存方式．沒錯，它就是利用 hash function 來決定儲存位置，也是就說透過 hash function 的計算來決定要儲存到那一個 page 上．
前面的文章曾提到過基本的 hash function，也介紹了它最簡單的運算方式．所以，假設一開始有十個 page，然後有五筆資料，我們可以將每筆資料傳給 hash function，計算出來的結果是...
#27 Coding 面試 Leetcode #98 Validate Binary Search Tree
我記得這一題我被問過兩次，是兩個不同的團隊，而且都是跟資料庫有關的工作．所以，若你也要尋找資料庫相關的開發工作，看來 Tree 的題目是很難避免的．
這題的題目很單純，就是要寫一個 function 用來驗證題目的 Tree 是不是 Binary Search Tree (BST).
根據 BST 的定義，左邊的節點值必需小於父節點值，而右邊的節點值必需大於父節點值.
但這題有一點要小心的是，別只是檢查父節點值而己，應該要檢查所有上層的父節點值都要小於或是大於．
如果題目只給你 tree root，那麼你可以寫出像下面的 function 來檢查這個 tree 是不是 BST.
public bool IsValidBST(TreeNode...
#26 資料庫基礎 - 存取 Page (Sorted File)
上一篇文章談的內容是針對資料之間是沒有順序的情況，因此在尋找資料時就是採用依照資料的排列順序來尋找．因此整個尋找過程的時間複雜度是 O(n) ．通常來說，資料庫設計者不會讓這樣的事情發生，除非資料本身是一個相當小的參考資料而己，否則資料一旦多了， O(n) 實在不是一個好現象．
在真實世界中的應用，我們常常可以為資料找到至少一種排列方法，例如，在學校的資料庫中，基本上可以用學生證的號碼來排序學生的資料，因為在同一個學校裡不會有相同的學生證號碼．我們在前面的文章中也提過，一旦資料排序過了之後，時間複雜度就會從 O(n) 下降成 O(log...
#25 資料庫基礎 - 存取 Page (Heap File)
在前面的幾篇文章中提到了資料庫引擎讀取與寫入資料時在面對固定長度與非固定長度時所可以採用的儲存方式，其中提供了 Page 為一個儲存空間的管理單位，透過 Page 的機制，讓資料庫引擎能以 Page 為單位做資料讀取與寫入的動作．搭配上 Page 裡的 manifest 資料，資料庫引擎就可以很清楚地知道這個 Page 裡面有多少筆資料以及有多少剩餘空間可用．這時候我們把層次往上拉高一點來看，那 Page 跟 Page 之間的關係是如何定義呢 ? 舉例來說，當某一個表格裡的資料繼續變多時，這些資料很可能會需要很多的...
#24 我的 IT 人生 - 簡短篇
這一篇內容我不談資料結構，也不談資料庫，更不談寫程式，我來簡單地談一談自己的 IT 人生．
在我還是高中生時，當時有接觸一些電腦課，學會了操作 MS-DOS 系統，也會寫一些簡單的 BASIC 程式，對電腦的確是有相當興趣，但還沒想過要把它當成一生的工作方向．後來，念了大學之後，我念的是機械工程，原本我的打算是想要念電機工程，因為自認為在物理課本中，電學念的比力學好很多，不過也奇怪，我當時還是把機械工程填入到志願卡裡，若我印象沒錯的話，我記得我的志願卡裡還有土木工程電子工程等等相關的工程科系．大學四年就這樣念到畢業了，說實在，到現在我還是覺得大學那 4 年似乎是浪費的，因為我現在沒需要用到任何機械工程的知識．不過，人生就是這樣，現在回過頭來看，就當做是用人生的時間換來了一些人生經驗．
接著，學校畢業後就直接去當兵了．我想這是我整個...
#23 Coding 面試 Leetcode #73 Set Matrix Zeroes
我打算把以前遇到的一些在面試時遇到的一些特別經驗或感想記錄在這電腦科學筆記裡，一方面，在面試時會遇到的問題大部份都是基礎的電腦科學題目，二方面也把這些過程記錄下來，當做是一種紀念吧!
在美國的軟體行業裡，要做 coding 面試算是很正常的事情，而這些 coding 面試大部份都是資料結構和演算法的內容，所以都是大學的必修課．但其實有許多題目還真的不是光念過課本就能想的到，那些題目還真的需要多練習．在市面上有許多網站會列出一些常見的面試考題，而我之前最常去的網站就是 Leetcode. 這網站不僅記載了許多考題，而且還有 online judge 可以直接測驗你的程式碼是否正確.
今天來聊聊這一題，在 Leetcode 網站上的第 73 題．我被問過一模一樣的題目，面試者連改都沒有改，而這一題也讓我體會到另一種空間複雜度的境界．...
#22 資料庫的資料實體儲存單位 Page - 3
在來延續上一篇文章 (#21 資料庫的資料實體儲存單位 Page - 2) 的內容．在上一篇的文章中看到了如果沒有 page 的概念時，資料庫引擎有那些可行的方法來在硬碟上管理資料，從上一篇文章中，你看感受到空白空間的處理與以及資料的定位並不是很方便．於是在階層管理的方便性上多加了一層 Page．
在一般市面上常見的資料庫產品中，Page 的大小都大約在幾Kb之間，類似於作業系統的儲存單位大小．所以，一個資料庫可能會包含一個或多個資料庫檔案，而每一個資料庫檔案都會包含多個 Page．
我們再看看如何用 Page 來管理資料．如上一篇文章的情況，資料有可變長度與固定長度兩種．固定長度的情況是比較單純好處理，可以參考下圖:
上圖是某一個...
#21 資料庫的資料實體儲存單位 Page - 2
延續上一篇文章 (#19 資料庫的資料實體儲存單位 Page) 的內容，在這篇文章裡，我們來談談有關資料庫的實體儲存結構．所謂的實體儲存結構是指資料放在硬碟中的情況．
首先，我們先來看看一個很簡單的結構，資料長度是固定的．這種情況在前面的文章有提過．因為長度都是固定的，所以每筆資料的長度便可以固定，這樣好處是在於方便計算也方便存取．
另一種情況是資料長度不是固定的，這種情況在前面文章也有提過．因為長度不是固定的，因此必須要想一個方法把不同欄位的資料做一個區隔，這樣在讀取資料時才知道什麼情況下是資料欄位的終點．在實體資料儲存時，有兩個方式可以來達成這種目的．第一，在每個資料欄位之間都用一個特殊符號隔開來，長相如下:
上圖是用一個...
#20 The Power of Ten - 撰寫可靠軟體的思維
標題為 The Power of Ten - Rules for Developing Safety Critical Code 的文章刊登在 IEEE Computer 2006 年 6 月的月刊中，作者是位在 NASA JPL 實驗室的研究科學家，同時也是位學者和工程師．這篇文章可以在 http://spinroot.com/gerard/pdf/P10.pdf 看到．
若以武功修練來比喻的話，這篇文章就像是一個得道高人所寫下來的內功心法，他把自己在 JPL 實驗室工作的多年 C 語言工作心得濃縮成十項重點，作者也為每一個重點留下說明．雖然這一篇文章是將近十年前的文章了，但它的參考價值極高，而且我相信許多資深的軟體工程師幾乎都會同意作者所寫的內容．
其中有幾點並非在所有的程式語言中都會碰的到，尤其是跟記憶體管理有關的工作．以現在一般商業應用裡最常見的...
#19 資料庫的資料實體儲存單位 Page
在上一篇文章中提到了有關資料庫 Storage manager 一點點的資訊．因此，這一篇文章就來談談更基礎的東西，叫 Page．它是什麼呢 ? 它就是 Storage manager 在處理儲存資料上的一種邏輯格式，也就是每個邏輯儲存空間的大小．這樣說可能還不好了解，讓我來直接舉個例子．資料庫引擎中有一個管理員叫 storage manager，它是負責資料儲存和讀取用，也就是說，今天使用者發出一個請求如 select * from table123，那麼這個命令就會經由資料庫引擎裡各式各樣的管理員來做語法確認解析，來做語法最佳化，然後可能還會經由其他管理員的檢查，最後才會到...
#18 資料庫的表格裡有關 nchar 和 nvarchar 的選擇
今天正在思考要來寫個不學術的事情，也就是希望能寫個跟產品相關程度較高的主題，想著想著，突然有個回憶就突然閃過腦子．
大約在十年前，當時還在台灣念碩士班，有位在台灣 IBM 工作的朋友剛好介紹了一個很短期的工作，因為他們急著做一個專案，但臨時抽不出過多的人手來完成這些功能，所以就經由朋友的介紹去參與這項專案的開發，賺一點零用錢，只需要做 5 個 tasks 就行了．當時，我記得是用 Javva 開發，然後資料庫產品是 DB2．不過，當時我做的短暫工作跟資料庫並沒有直接關係．
有一天，我到專案辦公室時，剛好看到 PM 正在輸入一些新的 database schema，我好奇在他旁邊看著那些 schema 資料，然後我就發現了一件頗為特別的事情，所以字串相關的資料欄位都是設計為 nchar，比如...
#17 客戶說程式碼不能有 recursive function，該怎麼辦 ?
不知大家有沒有被客戶這樣要求過，寫程式一律不準出現 recursive 的寫法．這也是十年前左右的故事了，並不是我個人遇到的狀況，是我朋友們遇過的情況．當時對這樣的要求沒太多的頭緒，不過心裡還是把這問題放著，也許有一天我會知道為什麼．
後來，有一次因為一個考試，突然讓我想到這個問題可能的答案，從技術角度來看的話，我想這應該是客戶的顧慮．情況是這樣的，在作業系統中，每個工作被執行的單位是 Process．一個作業系統裡會有許多的 Process 在執行，分別負責不同的功能，例如，有 Process 是專門負責處理 DNS 封包，有 Process 專門負責與印表機的通訊．所以，我們若自己寫一個程式在作業系統裡執行，這個程式也將是一個 Process，作業系統也就會負責他所需要做的工作內容．
在每個...
#16 我是非電腦科系的，真的需要懂這些嗎 ?
這問題其實一個很好的問題．
我假設你是個非電腦科系畢業出身的軟體工程師，回想一下，你當初憑著自己的邏輯能力學習如何寫程式，也學習如何善用大家所熟知的 framework，便可以應付自己工作上所遇到的問題．我想那是因為你的工作以及所面臨到的專案都是屬於商業型導向的應用程式．我所謂商業型導向的應用程式就像是你在金融界中工作，每個需要處理的就是把資料讀出來做報表，或把資料新增進去到資料庫，或是把這資料用某一種格式包裝起來，然後傳到其他的系統再做更多的資料處理．又比如說你在不同領域裡做該領域的工作，例如在航空公司做訂票系統，在電信公司做帳務系統，在電子商務公司做庫存系統．這些軟體工作其實在台灣是佔大多數的．所以，在這些工作中，若你沒有懂這些資料結構或演算法，你照樣也可以把程式寫出來，系統照樣地可以上線，公司照樣可以營運賺錢．因為我自己也曾有過這一段路，所以我知道是可能的．
不知你是否曾問過自己，我怎麼知道我寫的程式是不是好的，我該怎麼評估，或是別人又會怎麼看待我的寫程式能力．我相信非電腦科系畢業的人在做軟體工程師時一定會有這樣的問題．如果你有這樣的問題，很恭喜你，因為你的內心對知識有了渴望，因為你想知道自己的能力或寫程式的技巧是在什麼程度．所以，最好的方法就是回到事情的本質去找答案．因此，資料結構是需要懂的，演算法也是需要懂的，但我們並不用像...
#15 資料結構 Tree
Tree 應該是我們所需要介紹的最後一個基礎的資料結構了．在資料庫的領域中，你可以看到 Tree 在那裡發揮的淋灕盡致．以我個人來說，我喜歡把 Tree 看成是一種 List 的變形金鋼．前面在談論到 List 時，你可以發現 List 的元素後面只會接著一個元素，就這樣一個一個串接下去，這種情況就可以用在作業系統的檔案儲存．你可以把一個檔案想成是一個 List，而檔案的內容就會依照固定的大小分割成很多個元素，然後依照順序排好串在一起，這些元素就會散落在硬碟空間中，他們不需要排列在一起，所以同一個檔案的內容在放置時，可能是最後的元素放在硬碟空間前面的位置，因為元素之間都有一個...
#14 資料結構 Queue
在基礎的資料結構裡，Stack有一個好兄弟，長的跟它有一點像，但是提供的行為結果卻剛好相反，它的名字叫 Queue．在 Stack 中有一個可以把資料放入的行為叫 push，而把資料讀出來的行為叫 pop，並且最重要的重點是最先放進去的資料將會後最後被讀取的，所以這是一種先進後出或後進先出的情況．
類似於 Stack，Queue 也提供了方法可以將資料寫進去和讀出來，習慣稱為 Enqeueue 和 Dequeue．而跟 Stack 最大的不同就是 Queue 先寫進去的資料將會是先被讀出來，是一種先進先出或後進後出的情況．
你可以在資料結構的課本看到以上的內容，也可以找到 Queue 是如何被實做的，通常來說用 Array 來實做 Queue 會比較單純一點，只要一個 Array...
#13 利用 Hash Table 來增加你的資料處理速度
還記得十多年前參加一個專案時，自己做了一件不好的資料處理方式，當時的我還不知道什麼是 hash function．在那時候專案部份的工作需要快速地處理大量的資料，透過資料庫連線讀取資料，然後再讀取相關的參考資料，再經過運算，最後把結果再寫回資料庫，如果你的方法是讀一筆寫一筆的話，那肯定會造成大量的資料庫 I/O，所以比較適合的方法是做批次的處理，也就是一次讀取某個足夠數量的資料筆數，處理完成之後再一次寫回去，這樣可以減少資料庫的 I/O，也可以讓程式運行起來速度可以快些．
以上的想法是可行的，但當時有一個小小的挑戰是有關參考資料，因為資料在運算的過程中必需依靠其他的數據才能計算，而這些數據多達 8 萬多筆資料，簡單的說，它是三個欄位構成，第一個是分行 ID，第二個是一個會計科目 ID，第三個資料值．
...
#12 利用 Hash Table 來改進 FindSum4()
在 #2 的文章裡曾寫到 FindSum4() 的 Optimization 寫法，其程式碼再重新呈現如下：
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more...
#11 如何快速搜尋資料 - 利用 Hash function/Hash table
前面文章講了 binary search，這篇文章來介紹另一個好用而且非常常見的分類方法，它叫做 Hash．談到 Hash 時，通常包含兩個部份，一個是 Hash function，另一個是 Hash table．在業界的產品上，如 .Net/Java 等，都有提供業界標準的 hash function 以上一些 Hash table 的應用，如 .Net 的 HashSet, Dictionary 等就是 Hash table 的應用．首先，我們先談 Hash function．
Hash function 有一個很重要的特點是運算快速，那要多快呢?...
#10 資料結構 List
List 一般稱為 Linked List，這樣稱呼是因為在 List 裡面的每個元素都是一個連結連到下一個元素，這也稱為單向的 Linked List，如下圖所示：
這種單向的 List 應用在許多的情況下，例如作業系統的檔案寫入到硬碟時所採用的方式就是這樣單向 List 的概念．每個 List 都是由一個或多個元素所組成，而每個元素都有相同的資料結構，以上圖為例，元素裡包含了一個 decimal 和一個 pointer，這個指標所代表的是下一個元素的記憶體位址．所以，如果你要找 List 裡一共有多少元素時，就必須要從第一個元素一直移動到最後一個元素才能得知這個...
#9 Binary search 的 Big O ?
這是一個相當有趣的題目，前面講了 Binary search，因為它利用資料已排序好的特性，所以每次在尋找時可以中候選資料的中間切入來尋找，所以它的 Big O 該如何評估呢 ?
我們之前講到，如果現在找資料的方法是一個一個找，也就是說有十個資料時，最多要找十次，有十萬個資料時，最多要找十萬次，因此我們知道這方法和輸入的資料量成正比，所以是 O(n)．
Binary search 的 Big O 顯然一定比 O(n) 要快，那到底有多快呢 ? 我們可以來觀察一下．每次 binary search 在進行尋找時會從候選資料的中間尋找，然後依照目標值的大小來決定下一次尋找的候選資料是在前面一半還是後面一半，所以每次尋找後都可以將一半的資料給排除，比如說一開始有 100 個資料，經過第一次尋找後，下一回的候選資料就變成...
#8 如何快速搜尋資料 - Binary Search
在以前還沒念電腦科學之前，對於快速搜尋這件事情完全沒什麼概念，唯一知道就是在一堆資料裡面一個一個找了，對於沒念過電腦科學的人來說，一個一個找是最直覺也是最簡單的方法．想像一個情況，一個 Array 裡面有一百個整數，假設每一個整數的值都不一樣，那麼我們想要知道這個 Array 裡面有沒有 77 這個數字，最直接的方法就是從 Array 的第一個元素找到最後一個元素，最好的情況是 77 這數字剛好在 Array 的第一個位置，那麼很快就可以找到了，若最壞的情況是 77 落在 Array 的最後一個位置或是 77 根本不在這裡面，那麼我們就必須從第一個元素找到最後一個元素．從我們之前講的...
#7 系統上線了，我需要拿掉資料庫裡 foreign key 嗎?
前面講了一些基礎的內容，這篇文章來談談一些較實務面的經驗．
還記得許多年前在台北工作的時候，曾經在工作上發生一個經驗，當時我負責幫一個公司做一個小系統．這是一個簡單的小型商業系統，是一個 web application，在前端的部份分成兩項專案，其中一個專案是供給客戶登入各式各樣的資料，另一個專案是供管理者登入做資料的驗證與管理，而後端的部份是一個資料庫．在這個小專案裡，我負責前端客戶登入資料以及資料庫的設計，而管理者資料管理的部份是由該公司的工程師負責．
當整個專案在進行到後期的階段時，工程師們便開始為各項功能做驗證．在當時我並不清楚他們工程師負責的部份寫的如何，但是有件事情我倒是記得很清楚．某一天下午，該公司的工程師不知遇上了什麼技術上的問題，結果他們的主管就跑來找我，一付倚老賣老的姿態來跟我說話．這位主管說，我們過去做案子的情況都是這樣，當系統準備上線時都會把...
#6 資料結構 - Stack - part 2
承接上一篇的內容，我們要用什麼方式來做 Stack 的 "容器" 呢? 我們前面提過 Array 和 List，你覺得那一個用來做為 Stack 的容器比較適當?
我們在前面談過 Array 和 List，兩者最大的差異在於物件位於記憶體上的位置是緊連在一起還是允許分散的．如果緊連在一起，則讀取速度快，如果是分散的，則讀取速度慢．光是這一點，我想 Array 就足夠成為我們做為 Stack 容器的人選了．接下來我們用一個簡單的模型來談如何用 Array 做 Stack 的容器．
上圖是一個 Array，這裡頭一開始宣告了 5 個空間，所以可以放...
#5 資料結構 - Stack - part 1
還記得以前工作時曾有個一個經驗．有一天，我到同事的辦公室閒聊，聊著聊著他就跟我說他正在做一個新功能，當時我們正在做 Windows desktop應用程式，在這個程式裡面有一個編輯功能的頁面，讓使用者可以輸入產品的許多資料，而我同事正在做的就是為每個編輯動作留下記錄，好讓他可以做出 "undo" 的功能，而且要能一直 "undo" 下去．接著，他展現給我看他的成果，一切都運作的蠻好．接著，我就很好奇問他程式碼是怎麼寫的，接著他就展示相關的程式碼給我，他用了一個 .Net 的 DataTable，然後在這個 DataTable 裡建立了相關的欄位，如動作的序號，資料名稱，資料內容．因此，只要使用者一變動了某一個資料後，這個 DataTable 裡就會多了一筆資料，當使用者執行 "undo" 時，就會從這個...
#4 自己設計的 database schema 是不是好的呢 ?
前面的幾篇文章都講了些較基礎也較偏向課本的內容，在這篇裡面我們來談談比較實務的題目，那就是你怎麼知道你設計的 database schema 是不是好的?
如果你的工作是軟體專案的成員，這題目一定早就會在你心裡了．市面上的軟體專案有很大的部份都需要資料庫，用來儲存企業內所需的資料，而幾乎大部份市面上的專案所需要的資料庫都是關聯式資料模型 (Relational Database)，因此 database schema 的設計便是整個專案內容的設計中其中一個項目，也就是你要了解什麼是 ERM (Entity Relationship Model)．也許你之前念過一些課本的內容或是上過一些課，但若沒有真正自己參與設計的話，有時你心裡一定會覺得我這樣的設計是不是好的呢?
這篇文章的內容不是要教你如何設計...
#3 我需要懂資料結構嗎 ?
如果你的工作是系統管理或是網路工程領域，那麼資料結構可能對你不會有太大的影響，如果你的工作是程式設計或資料庫方面的領域，那麼資料結構對你將會是很重要的主題．若你的工作是程式設計類或資料庫類，即便你沒念過書本上的內容，我相信你對資料結構也有基本的認識．資料結構可以說是整個電腦科學裡相當基礎的知識，如果你把電腦科學用國中國小數學來比喻的話，則資料結構就像小學的四則運算一樣的基礎，必須要了解它才能通往更高級的方程式．
以目前的電腦架構來看，你可以把CPU視為一個做運算的單位，比如做加法運算或除法運算等等，而記憶體和硬碟的空間就像是一條有限長度的磁帶，你可以將資料寫在這條磁帶上，而記憶體這條磁帶比較短，但它讀取寫入速度較快，硬碟這條磁帶比較長，它讀取寫入速度較慢，所以當 CPU 運算時所需要的資料都是在記憶體和硬碟這兩條磁碟裡．接下來，當...
#2 BIG O - 有關程式執行的快慢 - Optimization
從上一次寫的文章中可以看到如何辦別一個程式執行的好壞，那些都是相當基本而簡單的例子，但在工作中時，我們需要利用這技巧嗎? 答案當然是 YES，但在一般業界中 BIG O 的評估，有時並不是那麼單純，因為我們都習慣用了其他公司寫好的 framework 來進行我們的程式撰寫，比如用 Java platform 或 .Net platform ，所以一個 API 內部會如何執行，我們看不到原始碼就不太能準確知道，所以這一部份只能靠著多使用這些 framework 所得的經驗來知道那一個 API 比較好．
比如，前一篇文章曾講到 string1.Contains(string2)，要寫 Contains() 可以很簡單，你可以把 string 看成是一個 array，在這個 array 裡的元素就是字串裡的每個字母，而今天你要在這字串裡面尋找是否包含另一個子字串時，最簡單的方法就是寫...
#1 BIG O - 有關程式執行的快慢
如果前面的文章所提，在十多年前時我還沒有電腦科學的基礎知識，在當時很難辦別自己寫的程式是不是好的，後來念書了之後才知道原來在課本裡有一些理論的方法來讓你做評估，而這篇文章的主題就是要來談這項評估. 評估的方法不只一種，而且還有一些數學推論，不過我將會儘量跳過數學推論的部份，而且只談論業界中最流行的一種評估方法，它叫做 O (我們將它念成 big O).
O 的數學基礎是你的程式所需執行的時間會因為輸入參數的不同而有所變化，比如你有一個程式要算1+2+3+4+5的答案，若你懂基本的程式，你就知道輸入參數是5，然後寫一個 loop 來做 5 次的加法就可以得到最後的答案. 一旦你的輸入參數是 10，那麼你寫的那個 loop 的內容就會執行十次.
int answer=0;
for...
#0 寫在最前面 - 網誌的內容與目的
我還記得很多年前在台北工作的時候，台灣的資訊業界和電子產業比起來算是較小的，但儘管如此，仍是會有許多機會遇到許多非電腦科系畢業的朋友在資訊業界中工作，比如，我曾遇過財經科系畢業的朋友從事網路工程的工作，或是其他理工科系的朋友從事程式撰寫的工作，甚至包括我自己也是. 我大學是念機械系，但進入社會後卻從沒有做過機械業的工作，而我所從事的全部都是資訊業中的工作.
因為有著不同的背景，後來才又跑回學校重拾課本，把許多該有的基本知識學了起來，能像我這樣做的朋友畢竟算是少數，所以這個網誌的目的就是把我過往的經驗寫下來，專門寫給非電腦科系畢業而在資訊業界中工作的朋友們. 電腦領域裡有許多的科目，我也不是全部都懂，所以往後的內容只著重在資訊業界中比較常會遇到情況，而這些情況的確是需要有念過課本裡所提供的知識才能清楚明白的....