【Python】競程相關模組、函數、方法等整理 - part 1
===
因為最近又要比賽了，所以趕緊做一篇整理複習一下，然後備註一下：這是個人筆記。
目錄（Table of Contents）：
[TOC]
IO優化
---
### 輸入優化
---
使用前引入模組：`import sys`
或 `from sys import stdin`，這樣方法就不用多打 sys。
```python=
from sys import stdin
line = stdin.readline()
```
若讀到 EOF 會回傳空字串。
建議搭配 strip() 函數使用：
```python=
from sys import stdin
line = stdin.readline().strip()
```
* `stdin.readline()`：每次讀取一行資料，直到 `\n` 為止。由於回傳的字串通常包含 `\n`，若不需要，用 strip() 去除。
* `stdin.readlines()`：一次讀完 stdin，會回傳 list。
* `stdin.read()`：讀取整個輸入流的所有資料，直到 EOF。適合一次性讀取大量資料。
以下使用迭代的方式處理 stdin 檔：
```python=
from sys import stdin
for line in stdin:
pass
```
不用特地處理 EOF，迭代完即退出迴圈。
### 輸出優化
---
使用前引入模組：`from sys import stdout`
`stdout.write()`：
* 將字串輸出至標準輸出流。
* 不會自動幫你加 `\n`，要加記得加。
* 除回傳字串外，也會回傳所寫的字元總數。
```python=
from sys import stdout
stdout.write("Hello, World!\n")
```
output:
```
Hello, World!
14
```
---
`stdout.writelines()`：
* 參數必為 iterable 物件。
* 迭代這個物件的每一個元素並寫入 stdout 檔。
* 無回傳值（None）。
* 若傳入的參數是字串，則 `stdout.writelines()` 的速度遠慢於 `stdout.write()`。
### 相關應用
---
有個 list a，然後遍歷他所有的元素。
```python=
from sys import stdout
a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
stdout.write(" ".join(map(str, a)))
```
output:
```
1 2 3 4 5 6 7 8 9 10
```
使用 `str.join()` 方法，搭配 `map()` 函數可減少輸出時間。
如果使用 for 迭代方式：
```python=
from sys import stdout
a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for i in a:
stdout.write(str(i), " ")
```
會慢很多且無效率。
### 多個變數輸入處理
---
```python=
from sys import stdin
a, b, c, d = list(map(int, stdin.readline().split()))
print(a, b, c, d)
```
math 模組
---
須引入模組 `import math`。
引入特定方法：`from math import <要用的方法>`
* `math.gcd(*integers)` , Python 3.5
回傳指定整數引數的最大公因數。若存在任一非零引數（Arguments），回傳值為所有引數共有因數中最大的正整數。若所有引數皆為零，則回傳值為 0。`gcd()` 若未傳入任何引數也將回傳 0。
```python=
from math import gcd
gcd(12, 20)
```
output:
```
4
```
---
* `math.lcm(*integers)` , Python 3.9
回傳指定整數引數的最小公倍數。若所有引數值皆非零，回傳值為所有引數共有倍數中最小的正整數。若存在任一引數值為零，則回傳值為 0。`lcm()` 若未傳入任何引數將回傳 1。
```python=
from math import lcm
lcm(12, 20)
```
output:
```
60
```
若因為 Python 版本問題，可使用公式 `GCD (a, b) = (a × b)/ LCM (a, b)`，直接求 `lcm()`。
---
* `math.factorial(n)`
以整數回傳 n 的階乘。若 n 非整數型別或其值為負會引發 ValueError。
```python=
from math import factorial
factorial(5)
```
output:
```
120
```
5! = 1 * 2 * 3 * 4 * 5 = 120
---
* math.ceil(x)：向上取整
* math.floor(x)：向下取整
`floor(x)` 實則為高斯函數 `f(x) = [x]` （參見高三上數甲）。
```python=
from math import ceil
ceil(2.3)
```
output:
```
3
```
```python=
from math import floor
floor(2.3)
```
output:
```
2
```
eval()
---
註：這是神兵利器，但比賽有可能會 ban 這個函數。
eval() 函數可用來執行一個字串運算式，並回傳運算式的值。
```python
eval(expression[, globals[, locals]])
```
expression：運算式
globals：變數作用域，若提供，則為 dictionary 物件。
locals：變數作用域，若提供，可為任何被 mapping 的物件。
以下範例在 Python Shell 裡執行：
```python=
>>> x = 7
>>> eval( '3 * x' )
21
>>> eval('pow(2,2)')
4
>>> eval('2 + 2')
4
>>> n=81
>>> eval("n + 4")
85
```
ord()
---
```python
ord(c)
```
c：character 字元。
將字元轉成十進位 Unicode 字元。
```python=
>>>ord('a')
97
>>> ord('b')
98
>>> ord('c')
99
```
註：與其相反的就是 chr() 函數，用法相同，chr() 將 Unicode 字元輸出為字母。
sum()
---
```python
sum(iterable[, start])
```
iterable：可迭代物件，如：list、tuple、set 等。
start：指定相加的參數，如果沒有設定這個值，預設為 0。
功能：求和用。
```python=
>>>sum([0,1,2])
3
>>> sum((2, 3, 4), 1)
10
>>> sum([0,1,2,3,4], 2)
12
```
進制轉換
---
### bin()：轉二進位函數
---
```python
bin(x)
```
x：int 或 long int 數字
該函數會回傳字串。
```python=
>>>
>>> bin(10)
'0b1010'
>>> bin(20)
'0b10100'
```
要去掉 0b，可做以下動作：
```python=
>>> bin(10)[2:]
'1010'
```
`[2:]` 將字串做切片擷取，從 2 開始擷取至結束。（因為這是字串所以可以這樣做）
### oct()：轉八進位函數
---
```python
oct(x)
```
x：整數。
回傳 8 進位字串。
```python=
>>> oct(10)
'0o12'
>>> oct(20)
'0o24'
>>> oct(15)
'0o17'
```
要去掉 '0o' 的話就跟上面作法一樣。
### hex()：轉十六進位函數
---
```python
hex(x)
```
x：整數。
回傳 16 進位字串。
```python=
>>>hex(255)
'0xff'
>>> hex(-42)
'-0x2a'
>>> hex(12)
'0xc'
>>> type(hex(12))
<class 'str'> # 字串
```
排序方法
---
結論：用 sort() 比較快。
### sorted()
---
```python
sorted(iterable, cmp=None, key=None, reverse=False)
```
iterable：可迭代物件。
cmp：比較函數，具有兩參數，參數的值從可迭代物件中取出，此函數必須遵守的規則為：大於則傳回 1，小於則傳回 -1，等於則傳回 0。
key：主要用來比較的元素，只有一個參數，具體的函數的參數就是取自於可迭代物件中，指定可迭代物件中的一個元素來進行排序。
reverse：排序規則，reverse = True 降序，reverse = False 升序（預設）。
不過建議用 key，cmp 太慢。
回傳 list。
```python=
>>> a = [5,7,6,3,4,1,2]
>>> b = sorted(a)
>>> a
[5, 7, 6, 3, 4, 1, 2]
>>> b
[1, 2, 3, 4, 5, 6, 7]
```
```python=
a = [('b',1),('a',2),('c',4),('d',3)]
sorted(a, key = lambda x:x[0]) // 依照字母排序
[('a', 2), ('b', 1), ('c', 4), ('d', 3)]
sorted(a, key = lambda x:x[1]) // 依照數字排序
[('b', 1), ('a', 2), ('d', 3), ('c', 4)]
```
### sort()
---
```python
list.sort(cmp=None, key=None, reverse=False)
```
參數說明同上。
此方法沒有回傳值，但會對列表的物件進行排序。
```python=
>>> a = [5,4,2,7,1,3,466,77,0]
>>> a.sort()
>>> print(a)
[0, 1, 2, 3, 4, 5, 7, 77, 466]
```
### sorted() v.s sort()
---
兩者差在哪？
sort() 專門用在 list 資料型態。
sorted() 則是所有可迭代物件皆可用。
zip()
---
```python
zip([iterable, ...])
```
可將可迭代物件之對應的元素打包成一個元組。
回傳值：list 包著 tuple（元組列表）
```python=
>>> a = [1,2,3]
>>> b = [4,5,6]
>>> c = [4,5,6,7,8]
>>> zipped = zip(a,b) # 打包為元組的列表
[(1, 4), (2, 5), (3, 6)]
>>> zip(a,c) # 元素個數與最短的列表一致
[(1, 4), (2, 5), (3, 6)]
>>> zip(*zipped) # 與 zip 相反，*zipped 可理解為解壓，回傳二維矩陣形式
[(1, 2, 3), (4, 5, 6)]
```
Tip：看列表直行，就是要打包的元組，像是 a、b 的 a[0]、b[0] 會被一起打包 -> (1,4)。
enumerate()
---
```python
enumerate(sequence, [start=0])
```
sequence：序列。迭代器或可迭代物件。
start：index 從何處開始列舉。
回傳值為：enumerate（列舉）物件。
反正這東西可列舉序列中的元素位置（index），如下：
```python=
>>> seasons = ['Spring', 'Summer', 'Fall', 'Winter']
>>> list(enumerate(seasons))
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
>>> list(enumerate(seasons, start=1)) # 從 1 開始列舉
[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]
```
以下展示了使用 `for` 迴圈跟結合 `enumerate()` 函數的區別：
```python=
>>> # 一般用法
>>> i = 0
>>> seq = ['one', 'two', 'three']
>>> for element in seq:
... print i, seq[i]
... i += 1
...
0 one
1 two
2 three
```
```python=
>>> # 使用 enumerate()
>>> seq = ['one', 'two', 'three']
>>> for i, element in enumerate(seq):
... print i, element
...
0 one
1 two
2 three
```
生成式（Comprehension）
---
參見：https://hackmd.io/@LukeTseng/SJ36tHV1A
deque（雙端佇列）
---
使用前引入模組：`from collections import deque`。
初始化一個 deque 可：`a = deque()`
deque 物件有以下方法：
* `append(x)`：將 x 丟到 deque 的末端。
* `appendleft(x)`：將 x 丟到 deque 的左端。
* `clear()`：清除所有 deque 元素且長度為 0。
* `copy()`：建立一個 deque 的淺複製。
* `count(x)`：計算 deque 內元素為 x 的個數
* `extend(iterable)`：將可迭代物件（如 list 等）擴展在 deque 末端。
* `extendleft(iterable)`：將可迭代物件（如 list 等）擴展在 deque 左端。
* `index(x[, start[, stop]])`：回傳 deque 中 x 的位置（或在索引 start 之後、索引 stop 之前的位置）。回傳第一個匹配的位置，如果沒找到就引發 ValueError。
* `insert(i, x)`：在 deque 位置 i 中插入 x。
* `pop()`：移除並回傳 deque 的末尾元素。
* `popleft()`：移除並回傳 deque 的最左端元素。
* `remove(value)`：移除第一個出現的 value，如果沒找到的話就引發一個 ValueError。
* `reverse()`：將 deque 中的元素原地 (in-place) 倒序排列並回傳 None。
那這可以幹嘛？用在 BFS、DFS。
bisect（二分搜）
---
使用前引入模組：`import bisect`
二分搜前置條件是要已排序的序列才可以二分搜。
函數如下：
* `bisect.bisect_left(a, x, lo=0, hi=len(a), key=None)`：回傳序列 a 中 x 出現的第一個位置（輸出 index 值）。
* `bisect.bisect_right(a, x, lo=0, hi=len(a))`：與上相反，回傳 x 出現的最後一個位置的索引再 + 1。
* `bisect.bisect(a, x, lo=0, hi=len(a))`：等同於 `bisect.bisect_right`。
```python=
import bisect
a = [1, 3, 3, 3, 5, 7, 9]
x = 3
# bisect_left 回傳 x 第一次出現的位置
index_left = bisect.bisect_left(a, x)
print("bisect_left:", index_left) # 1
# bisect_right 回傳 x 最後一個相同元素之後的位置
index_right = bisect.bisect_right(a, x)
print("bisect_right:", index_right) # 4
```
二分搜時間複雜度：$$O(nlogn)$$
排列組合好幫手：itertools
---
使用前引入模組：`import itertools`
* itertools.permutations(iterable, r=None)：排列，回傳 iterable 中連續且長度為 r 的元素排列。r 若無設定則預設為序列長度。
這東西就是：$$P^{n}_{m} = \frac{n!}{(n-m)!}$$
m = r + 1，假設 n = 5，r = 2 就會是以下數學式：$$P^{5}_{3} = 5\cdot4\cdot3=60$$
```python=
import itertools
print(list(itertools.permutations("ABCD", 2)))
```
以上的意思就等同：$$P^{4}_{3} = 4\cdot3 = 12$$
然後會列出 12 種排列可能性。
```
[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'A'), ('B', 'C'), ('B', 'D'), ('C', 'A'), ('C', 'B'), ('C', 'D'), ('D', 'A'), ('D', 'B'), ('D', 'C')]
```
* itertools.combinations(iterable, r)：組合，從輸入 iterable 中回傳長度為 r 的元素的子序列。
公式：$$C^{n}_{m} = \frac{P^{n}_{m}}{m!} = \frac{n!}{m!(n - m)!}$$
```python=
import itertools
print(list(itertools.combinations("ABCD", 2)))
```
```
[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]
```
寫成數學式就是：$$C^{4}_{2} = \frac{4!}{2!\cdot2!} = 6$$
跟輸出一樣，具有六種可能性。
lambda應用：三大常用函數
---
### map()
---
語法：
```python
map(function, iterable, ...)
```
function：函數。
iterable：可迭代物件。
回傳一個迭代器物件。
map 就是映射的意思，把 function 映射到 iterable 上面去，如下：
```python=
a = ['1', '2', '3', '4']
print(list(map(int, a)))
```
輸出：
```
[1, 2, 3, 4]
```
以上範例為將 `int()` 函數全部套用在 a 列表內的所有元素內。
### filter()
---
```python=
filter(function, iterable)
```
function：函數。
iterable：可迭代物件。
回傳一個迭代器物件。
這東西就是用 function 去過濾 iterable 的一些元素，把它篩選掉，如下範例：
```python=
>>> list(filter(lambda x: x%2==0, [1,2,3,4,5,6,7,8,9,10]))
[2, 4, 6, 8, 10]
```
把不是偶數的都篩掉了，這個意思就是把列表所有元素丟進去函數裡面運算，如果 x % 2 == 0 運算出來是 true 的話就留著，不是就把它丟掉。
然後這程式碼可以更簡化寫成：
```python=
>>> list(filter(lambda x: x%2==0, range(1,11)))
[2, 4, 6, 8, 10]
```
range(1, 11) 自動生成 1 ~ 10 的 list。
### reduce()
---
Python 3.x 已移到 functools，請引入：`from functools import reduce`
語法：
```python
reduce(function, iterable[, initializer])
```
function：帶有兩個參數。
該函數 reduce() 回傳函數計算結果。
reduce() 的運算原理：先將序列中兩個元素當作 function 的參數，運算完之後，function 的結果再跟下一個元素繼續丟 function 運算，算到不能再算為止。
```python=
>>> from functools import reduce
>>> reduce(lambda x, y: x + y, range(1,6))
15
```
以上這個輸出結果其實就是列表元素的和：$$1+2+3+4+5 = 15$$
但要用這個去做求和，不如用：`sum(range(1,6))`。
然後如果我們用 reduce() 去解釋，就像：
先將 1, 2 拉出來當參數，然後 1 + 2 = 3 結果出來後，3, 3 再當參數，依此類推，因此最後可以得到 15。
參考資料
---
[collections — Container datatypes — Python 3.13.2 documentation](https://docs.python.org/3/library/collections.html)
[Built-in Functions — Python 3.13.2 documentation](https://docs.python.org/3.13/library/functions.html)
[bisect — Array bisection algorithm — Python 3.13.2 documentation](https://docs.python.org/3.13/library/bisect.html)
[itertools — Functions creating iterators for efficient looping — Python 3.13.2 documentation](https://docs.python.org/3/library/itertools.html)
[math --- 數學函式 — Python 3.13.2 說明文件](https://docs.python.org/zh-tw/3.13/library/math.html#math.lcm)
[【筆記】Python I/O 優化 – Yui Huang 演算法學習筆記](https://yuihuang.com/python-io-optimize/)
[[I/O 優化] PYTHON 篇](https://happylearningcoding.blogspot.com/2020/07/io-python.html)
Sign in with Wallet
Connect another wallet