---
# System prepended metadata

title: 【Python】競程相關模組、函數、方法等整理 - part 1
tags: [程式設計, 競程, 演算法, Python, CP]

---

【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)