電腦科學 ^ IT人生 ^ 公益課程

#48 老鼠走迷宮 (mouse maze)

在大學的資料結構的課程裡,大約在教過 Stack, Queue 和 List 這些基本的資料結構之後會有一個老鼠走迷宮的作業.這份作業說難不難,說簡單也沒那麼簡單,對一個正在學習資料結構的學生來說,花個一兩個晚上來寫這份作業是很正常的.如果寫程式正是你的工作,而且你以前沒念過資料結構的話,不妨試著做做看這份作業.

老鼠走迷宮的內容是,要隨機產生一個矩陣,矩陣的大小最好由使用者輸入設定的.然後在矩陣裡的每個位置也會隨機產生三種不同的地形,例如平地,河流與高山.你可以再設計其他不同的地形,老鼠在每一個地形上走動時會花費不同的體力,例如平地是 1 ,河流是 2,而老鼠是無法穿越高山.老鼠的出發點是矩陣的左上角,也就是 (0,0) 的位置, 然後終點在右下角,也就是 (n,m) 的位置,n,m 代表的是矩陣的兩個邊長.

你所要寫的程式是讓使用者輸入矩陣的大小,然後為矩陣的每一個格子隨機產生地形,接著老鼠從出發點開始移動,看看老鼠是否可以走到終點.因為地形中會有高山,所以老鼠不一定都會有一條路可以走到終點.然而,老鼠能走的路也可能不只一條能到終點,你可以試著找出一條就行了.

整個題目的重點在於兩個地方.第一,移動的方向要定出一套規則,第二,要能夠記錄走過的路跡.移動方向的規則可以用最簡單的方式來實行,除了在邊邊與角落以外的格子,每個格子都可以有八種移動方向,上,下,左,右,左上,左下,右上,右下.每到達一個格子時,就可以依照固定的順序來移動到下一個格子,如果在下一個格子都沒有路走或是每個方向都試過了,那就回到上一個格子.因此,路跡的記錄是很重要的,因為需要回到上一個格子.

以下我提供十多年前寫的版本



如果你順利寫完之後,還有一個延伸題目給你繼續挑戰,那就是如果有多條可以走的路跡時,列出最省力的路跡.這延伸題目就不是那麼簡單了,未來再來寫篇文章來討論.


Share:

#47 資料庫基礎 - 以 Hash 為基礎的 Index

前面的文章介紹了資料庫的 Index 是以 tree 為基礎的方式,一般來說大部份資料庫產品都用 B-tree 來建立 Index.然而,除了用 tree 以外,還可以用 Hash 的方式來建立.


可以用上圖來說明 hash index 的運作方式.首先,輸入值會先經過 hash function 的運算後而得到一個 hashed value,這個運作如以前的文章講的是一個 constant time 的運算.輸入值就是使用者要過濾的條件,也就是 SQL statement 中 where 的內容的欄位值.例如,學生證號碼,病歷編號等等.然而,這種輸入值若不是 key 的話,便會發生多筆同樣資料會得到一樣的 hashed value,例如我們是用學生的姓來做 hash index 的話,則同樣的姓就會得到一樣的 hashed value.因此,一個 hashed value 可能會對應到一個或多個在 Data page 上的資料.,以上圖來看,每個 hashed index 的資料可以對應到一筆或多筆在 data page 上的資料,這樣的做法其實並不太好,因為每個 hashed index 的資料大小是無法確定的,就因為我們無法預測每個 hashed index 會對應到多少筆 data page 的資料.因此,可以再改一下如下圖,


我們規定每個 hashed index 的資料只能對應到一筆 data page 上的資料,這樣就可以固定住每個 hashed index 的資料大小.因此,當輸入值經由 hash function 運算之後到達第一個 hashed index 上的位置,便可以得到一筆 data page 的位置而取得資料,然後還要往下一個 hashed index 移動,如果 hashed value 也是一樣的話,就要再取得它所對應在 data page 上的資料,一直到 hashed index 上的值不同了或是沒有下一個了.

以 hashed index 的運作方式來看,其效率比以 tree 為基礎的 index 還要來的好,那為什麼一般的資料庫產品不採用它呢 ? 我想主要的原因就在於 hashed index 無法支援有範圍的尋找.例如,如果用學生證編號做 index,當你下 SQL statement where ID > 10 and ID < 100 時,這在 tree-based index 上可以有很好的尋找效果,只要找到 10 之後就再延著 tree node 一直往下或往旁邊找到 100 就可以停住了.但 hashed index 來說並不是這樣,因為在 hashed index 裡, 10 旁邊的很可能就是 100,要看 hash function 如何設計.所以在 hashed index 上我們找不到一直可以連續讀取資料的方式.如果我們把編號從 10 開始代入一直到 100,這聽起來好像可行,但如果 index 的資料不是數字而是文字,難道要把筆畫漸大的字都帶進去運算嗎 ? 顯然不可能.

雖然 hashed index 不適合用在有範圍的尋找,所以就不適合被一些商業資料庫產品所採用,但還是透過這篇文章介紹 hashed index 讓讀者們可以了解 index 的做法不見得只有 tree 的方式,不同的方式有好有壞,有長處也有短處.



Share: