【Python】競程相關模組、函數、方法等整理 - part 2
===
因為最近又要比賽了，所以趕緊做一篇整理複習一下，然後備註一下：這是個人筆記。
目錄（Table of Contents）：
[TOC]
優化技巧
---
### 避免全域變數
---
就跟 C / C++ 的做法一樣，建立一個主函數。另外在 Python 中全域變數會害程式變慢。
格式：
```python=
def main():
print('Hello World')
if __name__ == '__main__':
main()
```
### 列表初始化（生成式與不用生成式）
---
```python=
[None] * 100
[None for _ in range(100)]
```
建議用 `[None] * 100`，速度較快。
二維陣列形式：
```python
# faster
[[None] * N for _ in range(N)]
```
### for 迴圈遍歷優化
---
```python=
# for i in range(len(A)) -> slower
for i in range(len(A)):
A[i]
# for a in A -> faster
for a in A:
a
```
用下面的比較快一點。
print()
---
```python
print(*objects, sep=' ', end='\n', file=sys.stdout, flush=False)
```
objects：複數，表示可以一次輸出多個物件。輸出多個物件時，需要以 `,` 分隔。
sep：用來間隔多個物件，預設值為一個空格。（當兩物件間以 `','` 分隔時的空格）
end：用來設定以什麼結尾。預設值為 `'\n'`，可換為其他字串。
file：要寫入的檔案物件。
flush：輸出是否被快取通常決定於 file，但如果 flush 關鍵字參數為 True，串流會被強制刷新。
```python
>>> print("abc","123",sep=" ")
abc 123
>>> print("abc", end=' | By LukeTseng')
abc | By LukeTseng
```
statistics 模組
---
數學統計函式。實際上只要使用平均數、中位數、眾數方法就行。
使用前引入模組：`import statistics`
方法：
| 方法 | 說明 |
| -------- | -------- |
| statistics.mean(data) | 資料的算術平均數（平均值）。 |
| statistics.fmean(data, weights=None) | 快速浮點數算數平均數，可調整權重。 |
| statistics.geometric_mean(data) | 資料的幾何平均數。 |
| statistics.median(data) | 資料的中位數（中間值）。 |
| statistics.median_low(data) | 資料中較小的中位數。 |
| statistics.median_high(data) | 資料中較大的中位數。 |
| statistics.median_grouped(data, interval=1.0) | 分組資料的中位數（第 50 百分位數）。 |
| statistics.mode(data) | 離散 (discrete) 或名目 (nomial) 資料中的眾數（出現次數最多次的值），只回傳一個。 |
| statistics.multimode(data) | 離散或名目資料中的眾數（出現次數最多次的值）組成的 list。 |
| statistics.pstdev(data, mu=None) | 資料的母體標準差。 |
| statistics.pvariance(data, mu=None) | 資料的母體變異數。 |
| statistics.stdev(data, xbar=None) | 資料的樣本標準差。 |
| statistics.variance(data, xbar=None) | 資料的樣本變異數。 |
算術平均數：$\bar{x}=\frac{\Sigma^{n}_{i=1}x_{i}}{n}=\frac{x_{1}+x_{2}+\cdots+x_{n}}{n}$
幾何平均數：$GM = \sqrt[n]{x_{1} \cdot x_{2} \cdots x_{n}}$
中位數：若資料量奇數，則 (資料量+1)/2 即可，若偶數，則中間兩位的平均值就是中位數。
標準差：$\sigma=\sqrt{\frac{1}{N}\cdot\sum_{i=1}^N(x_{i}-\mu)^{2}}$
變異數：$Var(X)=\sigma^{2}=\frac{1}{N}\cdot\sum_{i=1}^N(x_{i}-\mu)^{2}$
> 母體標準差：母體標準差（Population Standard Deviation）是用來衡量整個母體資料分佈的離散程度的指標。在統計學中，母體是指您試圖瞭解和得出一些結論的整個資料集。由於母體規模龐大，不可能收集母體中每個元素的資料，因此母體標準差衡量的是理論母體分佈，並且幾乎總是未知的。
> 樣本標準差（Sample Standard Deviation）則是從母體中抽取樣本後，衡量該樣本資料分佈離散程度的指標。由於樣本只是母體的一部分，為了使樣本標準差成為母體標準差的無偏估計，計算樣本標準差時，分母採用 $n-1$ 而非 $n$，這被稱為貝塞爾校正（Bessel's correction）。
```python=
import statistics
data = [1, 2, 3, 4, 4, 5]
data_even = [1, 2, 3, 4]
data_multimode = [1, 1, 2, 2, 3]
# 1. statistics.mean(data) - 算術平均數
mean_value = statistics.mean(data)
print("算術平均數:", mean_value)
# 2. statistics.fmean(data, weights=None) - 快速浮點數算術平均數
fmean_value = statistics.fmean(data)
print("快速浮點數平均數:", fmean_value)
# 帶權重的 fmean
weights = [1, 1, 1, 1, 2, 1] # 給第四個和第五個元素更高權重
fmean_weighted = statistics.fmean(data, weights)
print("帶權重的快速平均數:", fmean_weighted) # 輸出: 3.4285...
# 3. statistics.geometric_mean(data) - 幾何平均數
geo_mean = statistics.geometric_mean(data)
print("幾何平均數:", geo_mean) # 輸出: ≈ 2.9938
# 4. statistics.median(data) - 中位數
median_value = statistics.median(data)
print("中位數:", median_value) # 輸出: 3.5
# 5. statistics.median_low(data) - 較小的中位數
median_low_value = statistics.median_low(data_even)
print("較小的中位數 (偶數資料):", median_low_value) # 輸出: 2
# 6. statistics.median_high(data) - 較大的中位數
median_high_value = statistics.median_high(data_even)
print("較大的中位數 (偶數資料):", median_high_value) # 輸出: 3
# 7. statistics.median_grouped(data, interval=1.0) - 分組資料的中位數
median_grouped_value = statistics.median_grouped(data, interval=1)
print("分組資料的中位數:", median_grouped_value) # 輸出: 3.5
# 8. statistics.mode(data) - 眾數（只回傳一個）
mode_value = statistics.mode(data)
print("眾數:", mode_value) # 輸出: 4
# 9. statistics.multimode(data) - 眾數列表
multimode_values = statistics.multimode(data_multimode)
print("眾數列表:", multimode_values) # 輸出: [1, 2]
# 10. statistics.pstdev(data, mu=None) - 母體標準差
pstdev_value = statistics.pstdev(data)
print("母體標準差:", pstdev_value) # 輸出: ≈ 1.3437
# 11. statistics.pvariance(data, mu=None) - 母體變異數
pvariance_value = statistics.pvariance(data)
print("母體變異數:", pvariance_value) # 輸出: 25/14 ≈ 1.8056
# 12. statistics.stdev(data, xbar=None) - 樣本標準差
stdev_value = statistics.stdev(data)
print("樣本標準差:", stdev_value) # 輸出: ≈ 1.4719
# 13. statistics.variance(data, xbar=None) - 樣本變異數
variance_value = statistics.variance(data)
print("樣本變異數:", variance_value) # 輸出: 13/6 ≈ 2.1667
```
例外處理（Try、Except）
---
範例及相關資訊參考自：https://steam.oxxostudio.tw/category/python/basic/try-except.html
語法錯誤（Syntax Error）：像是使用不存在的變數、型態輸出錯誤等能夠直接讓編譯器或直譯器發現的錯誤皆是語法錯誤。
語意錯誤（Semantic error）：雖然程式能夠順利執行，但輸出的結果不如人意，就是語意錯誤。
例外處理主要針對語法錯誤去做處理，也就是就算語法錯誤，也能繼續執行程式碼。
Try, Except 的語法：
```python=
try:
# Some Code
except:
# Executed if error in the
# try block
```
try 以內的程式碼會先執行，執行若發現有錯誤，會直接跳到 except。
那有時候不想執行 except 內的程式碼，但又不能不空著，因為空著會發生語法錯誤，所以可以加上 `pass`，如下：
```python=
try:
a = "1"
print(a + 1)
except:
pass
print("GG")
```
### except 可加上錯誤代碼
---
在 except 後面可加上錯誤代碼，意思就是當出現此錯誤就執行 except 以內的程式碼。
| 錯誤代碼 | 說明 |
| -------- | -------- |
| NameError | 使用沒有被定義的對象 |
| IndexError | 索引值超過了序列的大小 |
| TypeError | 數據類型（type）錯誤 |
| SyntaxError | Python 語法規則錯誤 |
| ValueError | 傳入值錯誤 |
| KeyboardInterrupt | 當程式被手動強制中止（Windows：ctrl + C） |
| AssertionError | 程式 asset 後面的條件不成立 |
| KeyError | 鍵發生錯誤 |
| ZeroDivisionError | 除以 0 |
| AttributeError | 使用不存在的屬性 |
| IndentationError | Python 語法錯誤（沒有對齊） |
| IOError | Input/output異常 |
| UnboundLocalError | 區域變數和全域變數發生重複或錯誤 |
```python=
try:
print(a)
except TypeError:
print('型別發生錯誤')
except NameError:
print('使用沒有被定義的對象')
print('hello')
```
輸出：
```
使用沒有被定義的對象
hello
```
若不知道錯誤代碼，就在 except 後面加上 Exception。
### raise、assert 中斷例外處理
---
* raise：放在 try 裡面，可中斷執行。
* assert：`assert False, '錯誤訊息'`
### else、finally
---
else：若完全沒有錯誤，則執行此區塊的程式碼。
finally：無論程式對錯，都會執行此區塊的程式碼。
```python=
try:
a = int(input('輸入 0～9：'))
if a>10:
raise
print(a)
except :
print('有錯誤喔～')
else:
print('沒有錯！繼續執行！') # 完全沒錯才會執行這行
finally:
print('管他有沒有錯，繼續啦！') # 不論有沒有錯都會執行這行
```
functools.lru_cache
---
使用前引入模組：`from functools import lru_cache`。
這是一個裝飾器，使用方式：`@lru_cache(maxsize=128)`。
maxsize：設定快取可儲存的最大結果數量，預設 128。若設為 None，則表示快取大小無限制（可能導致記憶體使用過多）。
那這可應用在哪？top-down 的 DP 演算法。（memoization，抓出重複計算的子問題）
然後詳細原理就不解釋了，有興趣可自行爬文，總之這是利用快取去優化遞迴（不只遞迴，基本函數也可）。
如下範例（[d212. 東東爬階梯](https://zerojudge.tw/ShowProblem?problemid=d212)）：
```python=
from functools import lru_cache
from sys import stdin
def main():
@lru_cache(maxsize=128)
def fib(n):
if n == 1:
return 1
if n == 2:
return 2
return fib(n-1) + fib(n-2)
for n in stdin:
print(fib(int(n)))
if __name__ == '__main__':
main()
```
因為輸入要 EOF，所以我們用到 part 1 的程式碼：
```python=
for line in stdin:
pass # some code
```
這題用 bottom-up DP（先處理最小子問題再推回去大問題） 會比較快一點，但 top-down 還是 AC 所以沒差XD。
BFS / DFS
---
BFS：層次搜索。
collections 中 deque 雙端佇列的應用。
```python=
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')
```
輸出：
```
A
B
C
D
E
F
```
以上範例從 A 開始搜索，發現 A 下一層是 B、C，所以全部丟進去已拜訪序列裡面，接下來拜訪 B，發現 A 已經拜訪過了，所以跳過 A，而 D、E 尚未拜訪過，丟進去已拜訪的序列裡面，依此類推。
DFS：深入到底，再深入回去最頂端，到了最頂端再深入下一個節點，依此類推。
DFS 是堆疊 stack 的應用。
```python=
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs(graph, 'A')
```
輸出結果：
```
A
C
F
E
B
D
```
以上範例程式碼中，因為用到 list.pop() 方法，所以預設會從最後一個元素移除並回傳該元素，因此就會看到 C 會先被 print 出來。
前綴和（Prefix-Sum）
---
Image Source：https://osgoodgunawan.medium.com/prefix-sum-80d531154b95
阿前綴和要幹嘛？求任意區間的和。
```python=
from itertools import accumulate
def prefix_sum(arr):
return list(accumulate(arr))
if __name__ == "__main__":
data = [1, 2, 3, 4, 5]
result = prefix_sum(data)
print("原始資料:", data)
print("前綴和:", result)
```
輸出：
```
原始資料: [1, 2, 3, 4, 5]
前綴和: [1, 3, 6, 10, 15]
```
程式碼可進一步簡化：
```python=
from itertools import accumulate
def main():
data = [1, 2, 3, 4, 5]
print("原始資料:", data)
print("前綴和:", list(accumulate(data)))
if __name__ == "__main__":
main()
```
若要求區間 $data[0],data[3]$ 的總和，則 $prefixsum[3]$ 即為區間內的和（$10$）。
若 $data[1],data[3]$ 的總和，就是 $prefixsum[3]-prefixsum[0]$，等於 $9$。
接下來依此類推。
參考資料
---
[statistics — Mathematical statistics functions — Python 3.13.2 documentation](https://docs.python.org/3/library/statistics.html)
[functools — Higher-order functions and operations on callable objects — Python 3.13.2 documentation](https://docs.python.org/3.13/library/functools.html)
[Python-LeetCode 581 第四招 前綴和 Prefix Sum - HackMD](https://hackmd.io/@bangyewu/rJRpH9dhh)
[例外處理 ( try、except ) - Python 教學 | STEAM 教育學習網](https://steam.oxxostudio.tw/category/python/basic/try-except.html)
[8 speed differences you need to know in Python | by xkumiyu | Medium](https://medium.com/@xkumiyu/8-speed-differences-you-need-to-know-in-python-db7266c3b177)
Sign in with Wallet
Connect another wallet