<!--introduction-->
# 12/20 第十四堂社課
## 今日講師：R緯
#### (Python班)
# 今日課程流程：
- 介紹-標準函式庫 (Standard Library)
- 資料結構
- 與演算法相關
- 歡樂題目time (如果有)
# 標準函式庫 (Standard Library)
[python官方](https://docs.python.org/zh-tw/3.10/library/index.html?highlight=standard%20library)
## 資料結構 (複習)
### 內建資料結構 ([第12堂社課講義](https://hackmd.io/@hihi-ihih/rJulQalX1l))
### 1. 列表∨串列 (List)
```python=
my_list = [1, 2, 3, 4, 5]
# list是可變的，可以隨時添加或刪除元素
my_list.append(6) # 添加元素到list末尾
my_list.remove(2) # 刪除元素 2
print(my_list) # 輸出: [1, 3, 4, 5, 6]
# list支持切片操作
print(my_list[1:3]) # 輸出: [3, 4]
```
**特性**：
- 有序：元素的順序是固定的。
- 可變：可以隨時修改、添加或刪除元素。
- 支持重複元素。
### 2. 元組 (Tuple)
```python=
my_tuple = (1, 2, 3, 4, 5)
# 元組是不可變的，無法修改其內容
# my_tuple[0] = 10 # 這會引發錯誤
print(my_tuple) # 輸出: (1, 2, 3, 4, 5)
# 可以進行切片操作
print(my_tuple[1:3]) # 輸出: (2, 3)
```
**特性**：
- 有序：元素的順序是固定的。
- 不可變：一旦創建，無法修改。
- 支持重複元素。
### 3. 集合 (Set)
```python=
my_set = {1, 2, 3, 4, 5}
# 集合不允許重複元素
my_set.add(3) # 不會添加重複的 3
my_set.add(6) # 添加新元素 6
print(my_set) # 輸出: {1, 2, 3, 4, 5, 6}
# 可以進行集合運算
another_set = {4, 5, 6, 7}
print(my_set.intersection(another_set)) # 輸出: {4, 5, 6}
```
**特性**：
- 無序：元素的順序不固定。
- 可變：可以添加或刪除元素。
- 不支持重複元素。
### 4. 字典 (Dictionary)
```python=
my_dict = {'name': 'Alice', 'age': 25}
# 字典以鍵值對存儲資料，可以快速查找
print(my_dict['name']) # 輸出: Alice
my_dict['age'] = 26 # 更新值
my_dict['city'] = 'New York' # 添加新鍵值對
print(my_dict) # 輸出: {'name': 'Alice', 'age': 26, 'city': 'New York'}
```
**特性**：
- 可變：可以添加、刪除或更新鍵值對。
- 鍵(key)必須是唯一的。
### 5. 字串 (String)
```python=
print("我相信大家都會")
```
**特性**：
- 有序：字符的順序固定。
- 不可變：一旦創建，無法修改。
- 支持切片和拼接操作。
### 其他資料結構
### 6. [數組 (Array)](https://hackmd.io/s_e8khb1T1awp9lMG9C-iA#3-%E6%95%B8%E7%B5%84-array-%E8%88%87-NumPy)：
- 通常用 `array` 模組或 NumPy 庫來處理數值計算。
- 定義方式（用 `array` 模組）
```python=
from array import array
my_array = array('i', [1, 2, 3, 4, 5]) # 'i' 表示整數型別
# 數組的元素類型是固定的
my_array.append(6) # 添加元素
print(my_array) # 輸出: array('i', [1, 2, 3, 4, 5, 6])
```
**特性**：
- 有序：元素的順序是固定的。
- 可變：可以添加或刪除元素。
- 所有元素必須是相同類型。
### 7. 堆疊 (Stack)：
- 可以用list來實現，後進先出 (LIFO) 原則。
```python=
stack = []
# 堆疊遵循後進先出 (LIFO) 原則
stack.append(1) # 添加元素
stack.append(2)
stack.append(3)
print(stack.pop()) # 輸出: 3 (最後添加的元素)
print(stack) # 輸出: [1, 2]
```
特性：
- 僅能在一端進行插入和刪除操作。
- 用於回溯演算法、函數調用等場景。
### 8. 佇列∨隊列 (Queue)
- 可以用 `collections.deque` 來實現，先進先出 (FIFO) 原則。
```python=
from collections import deque
queue = deque()
# 佇列遵循先進先出 (FIFO) 原則
queue.append(1) # 添加元素
queue.append(2)
queue.append(3)
print(queue.popleft()) # 輸出: 1 (最早添加的元素)
print(queue) # 輸出: deque([2, 3])
```
**特性**：
- 在一端插入元素，在另一端刪除元素。
- 用於排隊系統、廣度優先搜尋等場景。
### 9. [優先佇列 (Priority Queue)](https://hackmd.io/s_e8khb1T1awp9lMG9C-iA?both#2-%E5%A0%86%E7%A9%8D%E4%BD%87%E5%88%97%E6%BC%94%E7%AE%97%E6%B3%95-heap-queue-algorithm-%E7%B0%A1%E7%A8%B1heapq)
- 可以用 `heapq` 模組來實現。
- 例如：`import heapq; heap = []; heapq.heappush(heap, (priority, item))`
```python=
import heapq
heap = []
# 優先佇列根據優先級進行排序
heapq.heappush(heap, (1, 'task1')) # 優先級 1
heapq.heappush(heap, (3, 'task3')) # 優先級 3
heapq.heappush(heap, (2, 'task2')) # 優先級 2
print(heapq.heappop(heap)) # 輸出: (1, 'task1') (優先級最高的任務)
```
**特性**：
- 元素根據優先級進行排序，優先級高的元素會先被處理。
- 常用於任務調度、事件驅動系統等場景。
## 演算法 (Algorithm)
### 1. 容器資料型態 (collections)
### `Counter`
`Counter` 是 Python 的 `collections` 模組中的一個類，計算hashable對象的頻率。是一種字典子類，計算元素的出現次數。`Counter` 對象的key是hashable的元素，值是這些元素出現次數。
1. **導入**:
```python=
from collections import Counter
```
2. **創建 Counter 對象**:
- 可迭代對象：
```python=
c = Counter(['a', 'b', 'c', 'a', 'b', 'a'])
print(c) # Output: Counter({'a': 3, 'b': 2, 'c': 1})
```
- 字典：
```python=
c = Counter({'a': 3, 'b': 2, 'c': 1})
print(c) # Output: Counter({'a': 3, 'b': 2, 'c': 1})
```
- 關鍵字參數：
```python=
c = Counter(a=3, b=2, c=1)
print(c) # Output: Counter({'a': 3, 'b': 2, 'c': 1})
```
3. **訪問元素的計數**:
```python=
print(c['a']) # Output: 3
print(c['b']) # Output: 2
print(c['d']) # Output: 0 (如果元素不存在，返回 0)
```
4. **更新計數**:
用 `.update()` 更新計數：
```python=
c.update(['a', 'd', 'd'])
print(c) # Output: Counter({'a': 4, 'b': 2, 'd': 2, 'c': 1})
```
5. **最常見的元素**:
用 `.most_common()` 獲取最常見的元素及其計數：
```python=
print(c.most_common(2)) # Output: [('a', 4), ('b', 2)]
```
※如果多個元素計數相同，則順序是根據它們在原始數據中出現順序來決定。
6. **減少計數**:
用 `.subtract()` 減少計數：
```python=
c.subtract(['a', 'b'])
print(c) # Output: Counter({'a': 3, 'b': 1, 'd': 2, 'c': 1})
```
7. **數學運算**:
例如加法、減法、交集和聯集：
```python=
c1 = Counter(a=3, b=2)
c2 = Counter(a=1, b=2, c=1)
print(c1 + c2) # Output: Counter({'a': 4, 'b': 4, 'c': 1})
print(c1 - c2) # Output: Counter({'a': 2, 'b': 0})
print(c1 & c2) # Output: Counter({'a': 1, 'b': 2}) # 取最小值
print(c1 | c2) # Output: Counter({'a': 3, 'b': 2, 'c': 1}) # 取最大值
```
### `defaultdict`
`defaultdict` 也是 Python 的 `collections` 模組中的一個類。主要特點是能夠自動為不存在的key提供默認值，訪問這些key時就不會 `KeyError`。
1. **導入**:
```python=
from collections import defaultdict
```
2. **創建 defaultdict 對象**:
創建 `defaultdict` 需要提供一個工廠函數，用來生成默認值。常見的工廠函數包括 `int`、`list`、`set` 等。
- 用 `int` （默認值為 0）：
```python=
dd = defaultdict(int)
print(dd['a']) # Output: 0
```
- 用 `list` （默認值為空list）：
```python=
dd = defaultdict(list)
dd['a'].append(1)
dd['a'].append(1)
dd['a'].append(2)
print(dd) # Output: defaultdict(<class 'list'>, {'a': [1, 1, 2]})
```
- 用 `set` （默認值為空集合）：
```python=
dd = defaultdict(set)
dd['a'].add(1)
dd['a'].add(1)
dd['a'].add(2)
print(dd) # Output: defaultdict(<class 'set'>, {'a': {1, 2}})
```
3. **訪問元素**:
訪問一個不存在的key時，`defaultdict` 會自動創建一個默認值，不會引發 `KeyError`：
```python=
dd = defaultdict(int)
print(dd['b']) # Output: 0 (自動創建)
```
4. **更新元素**:
可以像普通字典一樣更新 `defaultdict` 的元素：
```python=
dd['a'] += 1
print(dd) # Output: defaultdict(<class 'int'>, {'a': 1})
```
5. **遍歷 `defaultdict`**:
可以用 `for` 循環遍歷 `defaultdict` ：
```python=
dd = defaultdict(int, {'a': 1, 'b': 2})
for key, value in dd.items():
print(key, value)
```
### 應用
`defaultdict` 非常有用，特別是在計數、分組的情況下。
例如：計算字母出現的頻率：
```python=
from collections import defaultdict
string = "hello world"
dd = defaultdict(int)
for char in string:
dd[char] += 1
print(dd)
```
### `deque`
`deque` 也$^2$是 Python 的 `collections` 模組中的一個類，代表雙端 佇列∨隊列 （double-ended queue）。與 列表∨串列（`list`）相比，`deque` 在兩端的插入和刪除操作的效率更高。
1. **導入**:
```python=
from collections import deque
```
2. **創建 deque 對象**:
傳遞一個可迭代對象創建 `deque`：
```python=
d = deque([1, 2, 3])
print(d) # Output: deque([1, 2, 3])
```
3. **添加元素**:
- 在右端添加元素：
```python=
d.append(4)
print(d) # Output: deque([1, 2, 3, 4])
```
- 在左端添加元素：
```python=
d.appendleft(0)
print(d) # Output: deque([0, 1, 2, 3, 4])
```
4. **刪除元素**:
- 從右端刪除元素：
```python=
d.pop()
print(d) # Output: deque([0, 1, 2, 3])
```
- 從左端刪除元素：
```python=
d.popleft()
print(d) # Output: deque([1, 2, 3])
```
5. **訪問元素**:
一樣可以通過索引訪問 `deque` 中的元素：
```python=
print(d[0]) # Output: 1
```
6. **旋轉 deque**:
`deque` 提供了 `.rotate()`，將元素旋轉指定的步數：
```python=
d.rotate(1) # 向右旋轉
print(d) # Output: deque([3, 1, 2])
d.rotate(-1) # 向左旋轉
print(d) # Output: deque([1, 2, 3])
```
**語法**:
```python=
deque.rotate(n)
```
- 其中 `n` 是一個整數，表示旋轉的步數：
- 如果 `n` 是正數，表示向右旋轉。
- 如果 `n` 是負數，表示向左旋轉。
- 左、右旋轉
- 向右旋轉時，`deque` 最後一個元素會移到第一個位置，其他向後移動。
- 向左旋轉時，`deque` 的第一個元素會移到最後一個位置，其他向前移動。
7. **限制大小**:
`deque` 可設置最大大小，超過這個大小時，最舊元素會被自動刪除：
```python=
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
print(d) # Output: deque([1, 2, 3])
d.append(4) # 超過最大大小，最舊的元素 1 被刪除
print(d) # Output: deque([2, 3, 4])
```
### `namedtuple`
`namedtuple` 是 Python 的 `collections` 模組中的一個工廠函數，創建有命名字段的元組子類。使得代碼更具可讀性和可維護性。
1. **導入 `namedtuple`**:
```python=
from collections import namedtuple
```
2. **創建 `namedtuple`**:
用 `namedtuple` 函數定義一個新的元組。需要提供類型名稱和字段的名稱（以空格分隔的字符串或list）。
```python=
Point = namedtuple('Point', 'x y')
```
3. **創建實例**:
用定義的 `namedtuple` 類型來創建實例。
```python=
p = Point(10, 20)
print(p) # Output: Point(x=10, y=20)
```
4. **訪問字段**:
通過字段名稱來訪問 `namedtuple` 的字段，比用索引更可讀。
```python=
print(p.x) # Output: 10
print(p.y) # Output: 20
```
5. **支持索引和unpacking**:
```python=
print(p[0]) # Output: 10
print(p[1]) # Output: 20
x, y = p # unpack
print(x, y) # Output: 10 20
```
6. **不可變性**:
`namedtuple` 和元組一樣是不可變的。
```python=
# p.x = 30 # 這會引發 AttributeError
```
### 2. 堆積佇列演算法 (heap queue algorithm, 簡稱heapq)
`heapq` 是 Python 的一個內建模組，提供操作堆（heap）數據結構的函數。
0. **heap 基本觀念**
- **堆** 是一種特殊樹形數據結構，常用於優先隊列。
- **最小堆** 的特性是每個父節點的值 $\leq$ 其子節點的值。
#### 1. 用list表示堆
- 堆可以用list來表示，並可用 `heapq` 模組操作。
- 用 `heapq.heapify()` 將list轉換為堆，list會被重新排列以滿足最小堆的特性。
#### 2. 索引計算
對於節點，索引為 `i`，找到其父節點和子節點的索引：
- **父節點的索引**：`(i - 1) // 2`
- **左子節點的索引**：`2 * i + 1`
- **右子節點的索引**：`2 * i + 2`
#### 3. 子節點有效性
- 當子節點索引$=$list的最大索引（list的長度$-1$）時，之後的索引不會有子節點。
#### 4. example
以堆 `heap = [1, 1, 2, 3, 5, 9, 4]` 為例，索引$0\sim6$：
- **索引 0**（值 1）：有左子節點（索引 1）和右子節點（索引 2）。
- **索引 1**（值 1）：有左子節點（索引 3）和右子節點（索引 4）。
- **索引 2**（值 2）：有左子節點（索引 5）和右子節點（索引 6）。
- **索引 3**（值 3）：左子節點（索引 7）和右子節點（索引 8）超出範圍，沒有子節點。
- **索引 4**（值 5）：左子節點（索引 9）和右子節點（索引 10）超出範圍，沒有子節點。
- **索引 5**（值 9）：左子節點（索引 11）和右子節點（索引 12）超出範圍，沒有子節點。
- **索引 6**（值 4）：左子節點（索引 13）和右子節點（索引 14）超出範圍，沒有子節點。
#### ※索引2就有子節點是索引6，在他之後的索引都不會有子節點，但機算機依然會確認其之後的索引是否符合最小堆（索引$3\sim6$）
1. **導入**:
```python=
import heapq
```
2. **創建堆**:
```python=
nums = [3, 1, 4, 1, 5, 9, 2]
heapq.heapify(nums) # 將list轉換為堆
print(nums) # Output: [1, 1, 2, 3, 5, 9, 4]（最小堆）
```
3. **插入元素**:
用 `heappush` 函數可以將新元素插入堆中，並保持堆的性質。
```python=
heapq.heappush(nums, 0)
print(nums) # Output: [0, 1, 2, 3, 5, 9, 4, 1]
```
4. **刪除最小元素**:
用 `heappop` 可以刪除並返回堆中的最小元素。
```python=
min_elem = heapq.heappop(nums)
print(min_elem) # Output: 0
print(nums) # Output: [1, 1, 2, 3, 5, 9, 4]
```
5. **查詢最小元素**:
用 `nums[0]` 可以訪問堆中最小元素，不會刪除它。
```python=
print(nums[0]) # Output: 1
```
6. **合併多個堆**:
用 `heapq.merge` 可以合併多個已排序∧可迭代對象，返回一個合併的迭代器。
```python=
sorted1 = [1, 3, 5]
sorted2 = [2, 4, 6]
merged = list(heapq.merge(sorted1, sorted2))
print(merged) # Output: [1, 2, 3, 4, 5, 6]
```
7. **獲取前 N 個最小元素**:
用 `heapq.nsmallest` 獲取堆中前 N 個最小元素。
```python=
smallest = heapq.nsmallest(3, nums)
print(smallest) # Output: [1, 1, 2]
```
8. **獲取前 N 個最大元素**:
用 `heapq.nlargest` 獲取堆中前 N 個最大元素。
```python=
largest = heapq.nlargest(3, nums)
print(largest) # Output: [9, 5, 4]
```
### 3. 數組 (array) 與 `NumPy`:
Python 標準庫中有一個 `array` 模組，但更常用的是 NumPy 庫，它提供更強大的數組功能。
### Python 標準庫中的 `array` 模組
主要用於存儲同類型的數據。數組的優勢在於它們比list更節省內存。
#### 基本用法
```python=
import array
# 創建一個整數數組
arr = array.array('i', [1, 2, 3, 4, 5])
print(arr) # Output: array('i', [1, 2, 3, 4, 5])
# 訪問元素
print(arr[0]) # Output: 1
# 修改元素
arr[0] = 10
print(arr) # Output: array('i', [10, 2, 3, 4, 5])
# 添加元素
arr.append(6)
print(arr) # Output: array('i', [10, 2, 3, 4, 5, 6])
# 刪除元素
arr.remove(3)
print(arr) # Output: array('i', [10, 2, 4, 5, 6])
```
1. **數組類型碼**
創建數組時，要指定數據類型，通過類型碼來實現。常見的類型碼包括：
- `'i'`: 整數 (integer)
- `'f'`: 浮點數 (float)
- `'d'`: 雙精度浮點數 (double)
- `'u'`: Unicode 字符串 (unicode)
### `NumPy` 數組 (補充)
NumPy 是強大的數值計算庫，提供多維數組 `ndarray`，及許多數學函數操作數組。NumPy 數組比 Python 的內建list和 `array` 模組更高效，特別是大型數據集。
1. **安裝 NumPy**
如果尚未安裝 NumPy
進行安裝：
```bash
pip install numpy
```
#### 基本用法
```python=
import numpy as np
# 創建一維數組
arr1 = np.array([1, 2, 3, 4, 5])
print(arr1) # Output: [1 2 3 4 5]
# 創建二維數組
arr2 = np.array([[1, 2, 3], [4, 5, 6]])
print(arr2)
# Output:
# [[1 2 3]
# [4 5 6]]
# 數組的形狀
print(arr2.shape) # Output: (2, 3) 表示 2 行 3 列
# 訪問元素
print(arr2[0, 1]) # Output: 2
# 修改元素
arr2[0, 1] = 10
print(arr2)
# Output:
# [[ 1 10 3]
# [ 4 5 6]]
# 添加元素
arr1 = np.append(arr1, 6)
print(arr1) # Output: [1 2 3 4 5 6]
# 刪除元素
arr1 = np.delete(arr1, 2) # 刪除索引 2 的元素
print(arr1) # Output: [1 2 4 5 6]
```
### NumPy 的功能
NumPy 提供了許多強大的功能，包括：
1. **數學運算**：支持向量化運算，能對整個數組進行操作∧不需要用循環。
```python=
arr = np.array([1, 2, 3])
print(arr + 1) # Output: [2 3 4]
print(arr * 2) # Output: [2 4 6]
```
2. **統計函數**：計算均值、標準差、方差等統計量函數。
```python=
arr = np.array([1, 2, 3, 4, 5])
print(np.mean(arr)) # 計算均值，Output: 3.0
print(np.median(arr)) # 計算中位數，Output: 3.0
print(np.std(arr)) # 計算標準差，Output: 1.4142135623730951
print(np.var(arr)) # 計算方差，Output: 2.0
```
3. **數組操作**：重塑、轉置、合併和分割等。
```python=
# 重塑數組
arr = np.array([[1, 2, 3], [4, 5, 6]])
reshaped_arr = arr.reshape(3, 2) # 變為 3 行 2 列
print(reshaped_arr)
# Output:
# [[1 2]
# [3 4]
# [5 6]]
# 轉置數組
transposed_arr = arr.T
print(transposed_arr)
# Output:
# [[1 4]
# [2 5]
# [3 6]]
# 合併數組
arr1 = np.array([1, 2, 3])
arr2 = np.array([4, 5, 6])
combined_arr = np.concatenate((arr1, arr2))
print(combined_arr) # Output: [1 2 3 4 5 6]
# 分割數組
split_arr = np.split(combined_arr, 2) # 將數組分為 2 部分
print(split_arr) # Output: [array([1, 2, 3]), array([4, 5, 6])]
```
4. **bool索引**：可以用bool條件來篩選數組中的元素。
```python=
arr = np.array([1, 2, 3, 4, 5])
filtered_arr = arr[arr > 2] # 篩選大於 2 的元素
print(filtered_arr) # Output: [3 4 5]
```
5. **廣播**：NumPy 支持廣播機制，允許不同形狀的數組進行運算。
```python=
arr1 = np.array([[1, 2, 3], [4, 5, 6]])
arr2 = np.array([10, 20, 30]) # 一維數組
result = arr1 + arr2 # 自動擴展 arr2 的形狀
print(result)
# Output:
# [[11 22 33]
# [14 25 36]]
```
### 4. 陣列二分演算法 (Array bisection algorithm, 簡稱bisect)
**※此為下週社課內容**
### 5. 排序演算法
有很多種，例如：
- 冒泡排序 (Bubble Sort)
- 選擇排序 (Selection Sort)
- 插入排序 (Insertion Sort)
- 快速排序 (Quick Sort)
- 合併排序 (Merge Sort)
- $\dots$
**※此為下下週社課內容**
Sign in with Wallet
Connect another wallet