【Python】競程相關模組、函數、方法等整理 - part 2

因為最近又要比賽了，所以趕緊做一篇整理複習一下，然後備註一下：這是個人筆記。

優化技巧

避免全域變數

就跟 C / C++ 的做法一樣，建立一個主函數。另外在 Python 中全域變數會害程式變慢。

格式：

def main():
    print('Hello World')

if __name__ == '__main__':
    main()

列表初始化（生成式與不用生成式）

1 2	[None] * 100 [None for _ in range(100)]

建議用 [None] * 100，速度較快。

二維陣列形式：

1 2	# faster [[None] * N for _ in range(N)]

for 迴圈遍歷優化

# 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()

1	print(*objects, sep=' ', end='\n', file=sys.stdout, flush=False)

objects：複數，表示可以一次輸出多個物件。輸出多個物件時，需要以 , 分隔。

sep：用來間隔多個物件，預設值為一個空格。（當兩物件間以 ',' 分隔時的空格）

end：用來設定以什麼結尾。預設值為 '\n'，可換為其他字串。

file：要寫入的檔案物件。

flush：輸出是否被快取通常決定於 file，但如果 flush 關鍵字參數為 True，串流會被強制刷新。

>>> 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）。

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 的語法：

try:
    # Some Code
except:
    # Executed if error in the
    # try block

try 以內的程式碼會先執行，執行若發現有錯誤，會直接跳到 except。

那有時候不想執行 except 內的程式碼，但又不能不空著，因為空著會發生語法錯誤，所以可以加上 pass，如下：

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	區域變數和全域變數發生重複或錯誤

try:
    print(a)
except TypeError:
    print('型別發生錯誤')
except NameError:
    print('使用沒有被定義的對象')
print('hello')

輸出：

1 2	使用沒有被定義的對象 hello

若不知道錯誤代碼，就在 except 後面加上 Exception。

raise、assert 中斷例外處理

raise：放在 try 裡面，可中斷執行。
assert：assert False, '錯誤訊息'

else、finally

else：若完全沒有錯誤，則執行此區塊的程式碼。

finally：無論程式對錯，都會執行此區塊的程式碼。

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. 東東爬階梯）：

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 的程式碼：

1 2	for line in stdin: pass # some code

這題用 bottom-up DP（先處理最小子問題再推回去大問題）會比較快一點，但 top-down 還是 AC 所以沒差XD。

BFS / DFS

BFS：層次搜索。

collections 中 deque 雙端佇列的應用。

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 的應用。

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

阿前綴和要幹嘛？求任意區間的和。

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	原始資料: [1, 2, 3, 4, 5] 前綴和: [1, 3, 6, 10, 15]

程式碼可進一步簡化：

from itertools import accumulate

def main():
    data = [1, 2, 3, 4, 5]
    print("原始資料:", data)
    print("前綴和:", list(accumulate(data)))

if __name__ == "__main__":
    main()