投影片 1

Size: px

Start display at page:

Download "投影片 1"

附纪
6 years ago
Views:

1 演算法課程 (Algorithms) Course 4 搜尋 Search 國立聯合大學資訊管理學系陳士杰老師

2 2 Outlines 本章重點 Search 分類觀點 Linear Search Binary Search Interpolation Search Hashing

3 3 Search 分類觀點 Internal Search v.s. External Search. Static Search v.s. Dynamic Search. Partial Partial Key v.s.. Whole Key Actual Actual Key v.s.. Transformation Key

4 4 Internal Search v.s. External Search 觀點 : 資料量的多寡 Internal Search: Def: 資料量少, 可以一次全部置於 Memory 中進行 search 之工作 External Search: Def: 資料量大, 無法一次全置於 Memory 中, 須藉助輔助儲存體 (E.g. Disk), 進行分段 search 之工作 B-tree M-way Search tree

5 5 Static Search v.s. Dynamic Search 被搜尋的資料集合資料的搜尋範圍或資料所存在的表格, 其內容是否經常異動 ( 如 : 是否常做資料的插入刪除或更新 )? 否 : Static 紙本的字典電話簿是 : Dynamic 日常交易資料電腦字典

6 6 Linear Search ( 線性搜尋 ) Def: 又稱 Sequential Search 自左到右 ( 或右到左 ), 逐一比較各個記錄的鍵值與搜尋鍵值是否相同若有找到, 則 Found ( 成功搜尋 ); 若 Search 完整個資料範圍仍未特質 : 找到, 謂之失敗 (Not found) 檔案記錄不須事先排序可由 Random Access (e.g., Array) 或 Sequential Access (e.g., Link List) 機制支援 Time Complexity: O(n),n 為資料個數 ( 線性 )

7 7 Linear Search 的演算法可分成兩種 : Non-Sential ( 無崗哨 ) Linear Search Sential Linear Search

8 8 Non-Sential Linear Search // 記錄個數 //Array of records (file of records) // 欲搜尋的鍵值 // 輸出的結果 Found: location 指出記錄的所在位置 Not Found: location 重設為 S n location

9 9 分析平均比較次數 ( 針對成功的搜尋 ): ( n)/n = n(n+1)/2 1/n = (n+1)/2 Time: O(n)

10 10 Sential Linear Search 觀念 : 多一個 S[0] 記錄, 其鍵值設定為 x n S x location 1 // 記錄個數 //Array of records (file of records) // 欲搜尋的鍵值 // 輸出的結果 Found: location 表示出記錄的所在位置 Not Found: location 為 0

11 11 以實際的執行時間實際的執行時間而言 : 分析由於少了測試 Search 範圍是否結束之比較 ( 即 : location <= n), n 所以當 n 極大時, 大約可以省下 ½ 的比較時間以 Time Complexity 分析而言 : 由於仍然是線性搜尋, 所以時間複雜度還是 O(n)

12 12 Binary Search ( 二分搜尋 ) 實施前提 : 檔案中記錄須事先由小到大由小到大排序過須由 Random ( 或 Direct) access 之機制支援 (e.g., Array) 觀念 : 每次皆與 Search 範圍的中間記錄中間記錄進行比較!! S l 小 m u middle l m u 大 middle = l + 2 u while ( l u ) m = l + 2 比較 (k, S[m]) case = : found, i = m, return i; case < : u = m-1; case > : l = m+1; recurn 0; u // 找到了 // 要找的資料在左半部 // 要找的資料在右半部

13 13 Algorithm Recursion Version:

14 14 Iteration Version:

15 15 分析利用 Time function T(n) = T(n/2) + O(1) = T(n/2) + c = (T(n/4 + c)) + c = T(n/4) + 2c = (T(n/8) + c) + 2c = T(n/8) +3c = = T(n/n) + log 2 n c = T(1) + c log 2 n (T(1) = 1, c 為大於 0 的常數 ) = 1 + c log 2 n T(n) = O(log 2 n)

16 16 Interpolation Search ( 插補搜尋 ) 比較符合人類 Search 之行為實施前提 : 檔案中記錄須事先由小到大由小到大排序過須由 Random ( 或 Direct) access 之機制支援 (e.g., Array) 作法 : 小 while ( l u && i == 0) ( m 是一個比較的距離 ) l m l + m S x S[ l] mid = l + ( u l + 1) S[ u] S[ l] 比較 (x, S[mid]) case 1 = : found, i = mid, return i; case 2 < : u = mid-1; case 3 > : l = mid+1; recurn 0; u 大 // 找到了 // 要找的資料在左半部 // 要找的資料在右半部 x S[ l] m = ( u l + 1) S[ u] S[ l]

17 17 Algorithm // 若 S 數列中只有一個數字時, 防止分母為 0 Case 1 Case 2 Case 3

18 18 分析其時間分析的效能是與鍵值分佈有關一般而言, Uniform Distribution 有 Best effect. Time Complexity: O(log 2 n) ~ O(n) 最佳情況 : 同 Binary Search O(log 2 n) 每一次都切一半最差情況 : 同線性 Search O(n) 第一次切割後, 會剩下 (n-1); 第二次切割後, 會剩下 (n-2) 筆 ; 依此類推即每一次切割後, 只有一筆資料被摒除於下一次的搜尋資料之外

19 19 Hashing ( 雜湊 ) Def: 為一種資料貯存與搜尋的技術若要存取某筆資料 x, 則先將 x 經過 Hashing Function 計算, 得出 Hashing Address, 再到 Hash Table 對應的 Bucket 中進行存取 x 的動作 Hash Table 的結構由一組 Buckets 所組成, 每個 Buckets 由一組 Slot 所組成, 每個 Slot 可存一筆記錄圖示 : Hash Table Size = b s Hash Table Bucket ( 桶子 ) x Hashing Function 存 / 取 H(x) (Hash Address) b 個 Slot ( 槽 ) s 個

20 20 優點 : 資料搜尋時, 記錄不需要事先排序在沒有 collision 及 overflow 情況下, 資料搜尋的 Time 為 O(1) 與資料量 n 無關保密性高若不知 Hashing function, 則無法存取資料可作資料壓縮之用

21 21 相關術語 Identifier Density 與 Loading Density Def: 令 T 為 identifier 總數,n 為目前使用者的 identifier 個數,b 為 Hash Table 之 Bucket 數目,S 為 Bucket 中之 Slot 數目, 則 : Collision Identifier Density = n/t Loading Density = n/(b S) = α α 愈大, 則表示 Hash Table Utilization 高, 但相對地 Collision / Overflow 機率也變高 Def: 不同的資料 (e.g., x 與 y) 在經由 Hashing Function 計算, 竟得出相同的 Hashing Address ( 即 H(x) = H(y)) 稱之

22 22 Overflow Def: 當 Collision 產生, 且 Bucket 中無多餘的 Slot 可存資料稱之 w H(w) x H(x) y H(y) w x y z: Overflow z H(z) 有 Collision 並不一定有 Overflow, 但有 Overflow, 則必有 Collision 發生若 Bucket 只有一個 Slot, 則 Collision = Overflow

23 23 Hashing Function 設計一個良好的 Hashing Function 須滿足下列三個準則 : 計算簡單 Collision 宜盡量少 Ex: x mod 2 就是不好的 Hashing Function!! ( 不是 0 就是 1, 會經常發生 Collision) 不要造成 Hashing Table 局部儲存 ( 局部偏重 ) 的情況會引發空間利用度差與 Collision 上升的缺失上述準則導引出兩個名詞 : Perfect Hashing Function ( 完美的雜湊函數 ) Def: 此 Hashing Function 絕對不會有 Collision 發生前提 : 須先知道所有資料 (for Static Search) Uniform Hashing Function ( 均勻的雜湊函數 ) Def: 此種 Hashing Function 計算所得出的 Hashing Address, 對應到每個 Bucket No. 的機率皆相等 ( 不會有局部偏重的情況 )

24 24 4 種常見的 Hashing Function Middle Square ( 平方值取中間位數 ) Mod ( 餘數, 或 Division) Folding Addition ( 折疊相加 ) Digits Analysis ( 位數值分析 )

25 25 Def: 將 Key 值取平方, 依 Hashing Table Bucket 數目, 選取適當的中間位數值適當的中間位數值作為 Hash Address e.g., 假設有 1000 個 Bucket, 範圍編號為 000~999, 若有一數值 x = 8125, 試利用 Middle Square 求其適當之 Hash Address Sol: ( 取平方 ) x = Middle Square ( 平方值取中間位數 ) 取中間三位 156 = Hash Address ( 取 015 亦可 )

26 26 Mod ( 餘數, 或 Division) Def: H(x) = x mod m m 的選擇之注意事項 : m 不宜為 2 求得的位址僅有 0 或 1,collision 的機會很大 m 的選擇最好是質數 ( 除盡 1 和除盡自已 )

27 27 Def: 將資料鍵值切成幾個相同大小的片段, 然後將這些片段相加, 其總和即為 Hashing Address 相加方式有兩種 : Shift ( 移位 ) Boundary ( 邊界 ) Folding Addition ( 折疊相加 ) 若有一資料 x = , 請利用兩種不同的 Folding Addition 方法求 Hashing Address ( 假設片段長度為 3)

28 28 Sol: x= are partitioned into three decimal digits long. P1 = 123, P2 = 203, P3 = 241, P4 = 112, P5 = 20. Shift folding: h( x) = i= 1 = Folding at the boundaries: 5 P i = h(x) = =

29 29 Digits Analysis ( 位數值分析 ) Def: 當資料事先已知, 則可以選定基底 r, 然後分析每個資料之同一位數值同一位數值 Ex: 若很集中, 則捨棄捨棄該位 ; 若很分散, 則挑選挑選該位, 而挑選的位數值集合成 Hashing Address

30 30 4 種常見的 Overflow 處理方式 Linear Probing ( 線性探測 ) Quadratic Probing ( 二次方探測 ) Rehashing ( 再雜湊 ) Link List ( 鏈結串列, 或稱 Chain)

31 31 Linear Probing ( 線性探測 ) Def: 又稱 Linear Open Addressing 當 H(x) 發生 overflow, 則循著 H(x)+1, H(x)+2,, H(x)-1 順序, 逐步搜尋, 直到 : 遇見有空的 Bucket 已搜尋完一圈為止 ( 表示 Hash Table Full, 無法 store) 圖示 : x

32 32 Hash Table 有 11 個 buckets ( 編號 : 0~10), 每個 bucket 只有一個 slot, 假設 Hashing Function = x mod 11, 並採取 Linear Probing 處理 overflow 試依照下列資料次序存入 Hash Table, 會得到什麼結果? Sol: 屬於 5 的部落原本應該屬於位置 6 的資料 17, 被擠到很遠的地方, 要翻山越嶺才能找到它!! Search Time 增加!! , 16, 33, 21, 22, 27, 38, 17 H(33) H(22) H(5) H(16) H(27) H(38) H(17) H(21) 缺點 : 易形成資料群聚 (Clustering) 現象, 增加 Searching Time

33 33 Quadratic Probing ( 二次方探測 ) Def: 為改善 Clustering 現象而提出當 H(x) 發生 overflow 時, 則探測 (H(x) ± i 2 ) mod b,b 為 bucket 數,1 i (b- 1)/2 圖示 : 空位的探測次序 : H(x)

34 34 承接上題, 並改採 Quadratic Probing 處理 overflow 則 Hash Table 內容為何? Sol: 5, 16, 33, 21, 22, 27, 38, H(33) H(22) H(5) H(16) H(27) H(38) H(17) H(21)

35 35 承接上題,44? Sol: H(44) = 0 (0+1 2 ) mod 11 = 1 負值需先加上 11 的適當倍數, 再取 mod!! (0-1 2 ) mod 11 = 10 (0+2 2 ) mod 11 = 4 (0-2 2 ) mod 11 = 7 (0+3 2 ) mod 11 = 9 (0-3 2 ) mod 11 =

36 36 Rehashing ( 再雜湊 ) Def: 提供一系列的 Hashing Functions: f 1, f 2, f 3, f n 若使用 f 1 發生 overflow, 則改用 f 2 ; 以此類推, 直到 : 沒有 overflow 發生全部 function 用完

37 37 將具有相同 Hashing Address 的資料, 以 Link list 方式串連在同一 Bucket 中承接上題, 並改採 Quadratic Probing 處理 overflow 則 Hash Table 內容為何? Sol: Link List ( 鏈結串列, 或稱 Chain) 5, 16, 33, 21, 22, 27, 38, 17 H(38) H(27) H(22) H(33) H(16) H(5) H(17) H(21)

38 38 補充

39 39 補 1: Decision Tree for Binary Search 目的 : 用以描述與了解 Binary Search 的比較行為一定是二元樹給出 n = 31 筆記錄之 Binary Search 的決策樹 Sol: l m u l [16] [8] [24] [4] [12] [20] [28] [2] [6] [10] [14] [18] [22] [26] [30] [1] [3] [5] [7] [9] [11] [13] [15] [17] [19] [21] [23] [25] [27] [29] [31] 欲搜尋記錄在第 18 筆, 則比較 4 次才能找到最多之比較次數為何 ( 比較幾次後, 即知失敗 )? 5 次 n 筆記錄, 最多的比較次數 = log 2 (n+1) = 高度 u

40 40 範例練習繪出 n=12 筆記錄, 執行 Binary Search 之 Decision Tree 有下列資料,26, 55, 77, 19, 13, 2, 5, 49 以 Binary Search 找 55 須比較幾次?

演算法導入、ソート、データ構造、ハッシュ

演算法導入、ソート、データ構造、ハッシュ培訓 - 1 演算法導入ソートデータ構造ハッシュ演算法導入ソートデータ構造ハッシュ momohuang c2251393 chiangyo September 23, 2013 1 Schedule of the Year 1.1 Major Competition 9 12 11 10 12 10 TOI 的最 3 TOI 3 TOI 100 20 4 TOI 30 12 5 TOI