---
hackpadID: OSSr7q4z4lq
hackpadWorkspace: tossug
tags: hackpad-import, tossug
---
# DS 讀書會 - 第 10 週

01/27/2015

[« 回首頁](/JwdmDZwMwE3BacBGApgDngFkwYx/NAVjQxlgCZgkdo0AjNIA)

## 討論範圍

* Sorting and Searching
* Objectives - The Selection Sort

## 預定進度

* Sorting and Searching
* The Insertion Sort - Programming Exercises

## 認領狀態

* Insertion Sort, Shell Sort
* [Jonathan Hsieh](https://tossug.hackpad.com/ep/profile/v2IkzygwDuI)
* Merge Sort, Quick Sort
* [Ted Wu](/ep/profile/xo5A62wXl3B)

## 心得筆記

**The Binary Search**


It must be an ordered list.

Time Complexity: O(log n)

**Hashing**

* 一種對應的關係，按圖索驥的概念。
* 對應啥？把資料透過演算法對應到存的位置。
* 簡單的日常生活範例
* 掃二維條碼，馬上可以看到對應的網頁
* 特點
* O(1)

<undefined>* 名詞解釋1</undefined>

* Hash table
* 存放真正資料的表單
* Slot
* Hash table每一筆欄位
* Hash function
* 把資料經過計算後，決定放在hash table的那一個slot

**簡單範例**

我要存放ASCII字串，hash table的slot有15個，那麼我可以定義

* hash function：字串ASCII代碼數字加總後取15的餘數，那麼存放方式範例會是
* "aa" : (141 + 141) % 15 = (282) % 15 = 12
* "bb" : (142 + 142) % 15 = (284) % 15 = **14**
* "aabb" : (282 + 284) % 15 = (566) % 15 = 11
* "@@T": (100 + 100 + 84) % 15 = (284) % 15 = **14**

<undefined>* 名詞解釋2</undefined>

* collision
* "bb"和 "@@T" hash值相同，都會放在同一個slot，顯然會打架
* Perfect hash function
* 所有資料都對應到hash table不會產生collision

由於perfect hash function機會不可能存在，除非幫所有可能的資料都保留slot。但是這是很不切實際的想法，想像身分證字號，把所有可能的身份證字號排列組合都做成slot，會佔用極大的空間，而且使用率可能很低。

<undefined>* **好的hash function目標**</undefined>

* collision 最小化
* 計算hash方式簡單化

<undefined>* 範例2 ，改善使用取餘數的hash function的collision狀態</undefined>

* 情況: 100 % 11 和 23 % 11 hash值都是一
* 方式一
* 將數字分組後加總，取餘數
* 10 + 0 % 11 = 10
* 23 % 11 = 1
* 方式二
* 平方後，取中間執取餘數
* (100 x 100) 中間值 00 
* 0 % 11 = 0
* (23 x 23) 中間值 = 52
* 52 % 11 = 8  

<undefined>* 實際範例</undefined>

* #!/usr/bin/env python3

* def sum_str(in_str):
* if len(in_str) == 1:
* return ord(in_str[0])
* return ord(in_str[0]) + calc_str_hash(in_str[1:])

* def calc_str_hash(in_str):
* return sum_str(in_str) % 11

* if __name__ == "__main__":
* print(str(calc_str_hash("cat"))) 

**Collision reduction**

出現collision怎麼辦?

* **linear probing:** 以鄰為壑
* 找最近沒在用的slot，塞進去
* 缺點
* 佔了別人的地盤，別人要入住也只好佔其他人地盤。
* 同一個hash值，很多collision，就佔掉很多其他附近的slot
* 以分配的想法(請打臉），佔了連續的slot會影響效能。
* 改良版一
* 加offset，固定隔幾個slot找倒楣鬼趁它沒用先搶先贏
* 又是名詞解釋
* hash clustering
* 運氣不好地很多筆資料的hash值相同，以至於該hash slot旁邊的slot都被佔走
* rehash
* 資料hash的slot被佔，要找其他slot的狀況
* 「以鄰為壑」法如果用offset，必須要保證最後可以 traverse所有slot。書本說所以要用質數。
* 不懂質數和traverse所有slot的關係
* 偏 移量是取餘數所以是 offset % size ，先不考慮其他，從 0 開始traverse過程可以看成 0 -> 1*offset %  size) -> 2*offset % size)  -> 3*offset%size) -> ...... ->  size*offset %size) = 0所以又從0開始輪遞。
* 如果offset與size有比一大的公因數，那在size走完途中就會回到0進入循環(因為走到那個公因數會整除)，整個traverse只有(size / gcd(size, offset))在走(不太確定是不是除gcd但就是會走不滿size。
* 有點越寫越亂的感覺  orz
* 對數字，空間感無感的人碰到這些真痛苦。
* 教材是說table size為質數，剛剛被提點才發現。而且真的不管offset是什麼只要比table sze小就一定互質，有點被雷打到的感覺XD

* **quadratic probing:** 以鄰為壑改良版二，不用固定的offset，而是遞增式的選擇沒在用的slot。
* n
* n + 1
* n + 3
* n + 5
* X%Y  -->  (X+1)%Y  -->  (X+3)%Y --> (X+h)%Y
* offset要和slot數量互質
* Chaining: 加外掛
* 發生collection的時候建立一個node，掛在slot後面
* 第二次collection，就掛在第一個node後面
* 變成二維的link list

* **複雜度計算部份完全看不懂**

**The Bubble Sort**

[](http://nbviewer.ipython.org/gist/bcbcarl/8efef7b4019c110fb692)http://nbviewer.ipython.org/gist/bcbcarl/[8efef7b4019c110fb692](http://nbviewer.ipython.org/gist/bcbcarl/4c2f8c2af4318dbc040d)

**The Selection Sort**

* alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
* def selection_sort(alist):
* sorted_list, alist = [], alist[:]
* while len(alist) > 0:
* v = min(alist)
* sorted_list.append(v)
* alist.remove(v)
* return sorted_list

## 活動簽到

[Carl Su](https://tossug.hackpad.com/ep/profile/n5euV0AaWLn)

[FourDollars](https://tossug.hackpad.com/ep/profile/tgNQRpN8EgG)

Jonathan Hsieh

[Manuel Stallman](https://tossug.hackpad.com/ep/profile/GgkcGJEol5r)

[RJ Hsiao](/ep/profile/BzrOLagTOUQ)

[Robert D. Wei](https://tossug.hackpad.com/ep/profile/u8S8v3LRs8U) 

[Scott Yu](https://tossug.hackpad.com/ep/profile/FXMAg851dkz)

StarNight

[Ted Wu](/ep/profile/xo5A62wXl3B)

[violetson](/ep/profile/oJusv72f72w)