---
# System prepended metadata

title: DS 讀書會 - 第 10 週
tags: [' tossug', hackpad-import]

---

---
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**

![](http://interactivepython.org/runestone/static/pythonds/_images/binsearch.png)

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)
