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

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

IO優化

輸入優化

使用前引入模組：import sys

或 from sys import stdin，這樣方法就不用多打 sys。

1 2	from sys import stdin line = stdin.readline()

若讀到 EOF 會回傳空字串。

建議搭配 strip() 函數使用：

1 2	from sys import stdin line = stdin.readline().strip()

stdin.readline()：每次讀取一行資料，直到 \n 為止。由於回傳的字串通常包含 \n，若不需要，用 strip() 去除。
stdin.readlines()：一次讀完 stdin，會回傳 list。
stdin.read()：讀取整個輸入流的所有資料，直到 EOF。適合一次性讀取大量資料。

以下使用迭代的方式處理 stdin 檔：

1
2
3

from sys import stdin
for line in stdin:
    pass

不用特地處理 EOF，迭代完即退出迴圈。

輸出優化

使用前引入模組：from sys import stdout

stdout.write()：

將字串輸出至標準輸出流。
不會自動幫你加 \n，要加記得加。
除回傳字串外，也會回傳所寫的字元總數。

1 2	from sys import stdout stdout.write("Hello, World!\n")

output:

1 2	Hello, World! 14

stdout.writelines()：

參數必為 iterable 物件。
迭代這個物件的每一個元素並寫入 stdout 檔。
無回傳值（None）。
若傳入的參數是字串，則 stdout.writelines() 的速度遠慢於 stdout.write()。

多個變數輸入處理

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。

1 2	from math import gcd gcd(12, 20)

output:

math.lcm(*integers) , Python 3.9

回傳指定整數引數的最小公倍數。若所有引數值皆非零，回傳值為所有引數共有倍數中最小的正整數。若存在任一引數值為零，則回傳值為 0。lcm() 若未傳入任何引數將回傳 1。

1 2	from math import lcm lcm(12, 20)

output:

若因為 Python 版本問題，可使用公式 GCD (a, b) = (a × b)/ LCM (a, b)，直接求 lcm()。

math.factorial(n)

以整數回傳 n 的階乘。若 n 非整數型別或其值為負會引發 ValueError。

1 2	from math import factorial factorial(5)

output:

5! = 1 2 3 4 5 = 120

math.ceil(x)：向上取整
math.floor(x)：向下取整

floor(x) 實則為高斯函數 f(x) = [x] （參見高三上數甲）。

1 2	from math import ceil ceil(2.3)

output:

1 2	from math import floor floor(2.3)

output:

eval()

註：這是神兵利器，但比賽有可能會 ban 這個函數。

eval() 函數可用來執行一個字串運算式，並回傳運算式的值。

1	eval(expression[, globals[, locals]])

expression：運算式

globals：變數作用域，若提供，則為 dictionary 物件。

locals：變數作用域，若提供，可為任何被 mapping 的物件。

以下範例在 Python Shell 裡執行：

>>> x = 7
>>> eval( '3 * x' )
21
>>> eval('pow(2,2)')
4
>>> eval('2 + 2')
4
>>> n=81
>>> eval("n + 4")
85

ord()

ord(c)

c：character 字元。

將字元轉成十進位 Unicode 字元。

>>>ord('a')
97
>>> ord('b')
98
>>> ord('c')
99

註：與其相反的就是 chr() 函數，用法相同，chr() 將 Unicode 字元輸出為字母。

sum()

1	sum(iterable[, start])

iterable：可迭代物件，如：list、tuple、set 等。

start：指定相加的參數，如果沒有設定這個值，預設為 0。

功能：求和用。

>>>sum([0,1,2])  
3  
>>> sum((2, 3, 4), 1)
10
>>> sum([0,1,2,3,4], 2)
12

進制轉換

bin()：轉二進位函數

bin(x)

x：int 或 long int 數字

該函數會回傳字串。

>>>
>>> bin(10)
'0b1010'
>>> bin(20)
'0b10100'

要去掉 0b，可做以下動作：

1 2	>>> bin(10)[2:] '1010'

[2:] 將字串做切片擷取，從 2 開始擷取至結束。（因為這是字串所以可以這樣做）

oct()：轉八進位函數

oct(x)

x：整數。

回傳 8 進位字串。

>>> oct(10)
'0o12'
>>> oct(20)
'0o24'
>>> oct(15)
'0o17'

要去掉 ‘0o’ 的話就跟上面作法一樣。

hex()：轉十六進位函數

hex(x)

x：整數。

回傳 16 進位字串。

>>>hex(255)
'0xff'
>>> hex(-42)
'-0x2a'
>>> hex(12)
'0xc'
>>> type(hex(12))
<class 'str'>      # 字串

排序方法

結論：用 sort() 比較快。

sorted()

1	sorted(iterable, cmp=None, key=None, reverse=False)

iterable：可迭代物件。

cmp：比較函數，具有兩參數，參數的值從可迭代物件中取出，此函數必須遵守的規則為：大於則傳回 1，小於則傳回 -1，等於則傳回 0。

key：主要用來比較的元素，只有一個參數，具體的函數的參數就是取自於可迭代物件中，指定可迭代物件中的一個元素來進行排序。

reverse：排序規則，reverse = True 降序，reverse = False 升序（預設）。

不過建議用 key，cmp 太慢。

回傳 list。

>>> 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]

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

1	list.sort(cmp=None, key=None, reverse=False)

參數說明同上。

此方法沒有回傳值，但會對列表的物件進行排序。

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

1	zip([iterable, ...])

可將可迭代物件之對應的元素打包成一個元組。

回傳值：list 包著 tuple（元組列表）

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

1	enumerate(sequence, [start=0])

sequence：序列。迭代器或可迭代物件。

start：index 從何處開始列舉。

回傳值為：enumerate（列舉）物件。

反正這東西可列舉序列中的元素位置（index），如下：

>>> 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() 函數的區別：

>>> # 一般用法
>>> i = 0
>>> seq = ['one', 'two', 'three']
>>> for element in seq:
...     print i, seq[i]
...     i += 1
...
0 one
1 two
2 three

>>> # 使用 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。

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$

1
2
3

import itertools

print(list(itertools.permutations("ABCD", 2)))

以上的意思就等同： $P^{4}_{3} = 4\cdot3 = 12$

然後會列出 12 種排列可能性。

1	[('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)!}$

1
2
3

import itertools

print(list(itertools.combinations("ABCD", 2)))

1	[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

寫成數學式就是： $C^{4}_{2} = \frac{4!}{2!\cdot2!} = 6$

跟輸出一樣，具有六種可能性。

lambda應用：三大常用函數

map()

語法：

1	map(function, iterable, ...)

function：函數。

iterable：可迭代物件。

回傳一個迭代器物件。

map 就是映射的意思，把 function 映射到 iterable 上面去，如下：

1 2	a = ['1', '2', '3', '4'] print(list(map(int, a)))

輸出：

1	[1, 2, 3, 4]

以上範例為將 int() 函數全部套用在 a 列表內的所有元素內。

filter()

1	filter(function, iterable)

function：函數。

iterable：可迭代物件。

回傳一個迭代器物件。

這東西就是用 function 去過濾 iterable 的一些元素，把它篩選掉，如下範例：

1 2	>>> 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 的話就留著，不是就把它丟掉。

然後這程式碼可以更簡化寫成：

1 2	>>> 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

語法：

1	reduce(function, iterable[, initializer])

function：帶有兩個參數。

該函數 reduce() 回傳函數計算結果。

reduce() 的運算原理：先將序列中兩個元素當作 function 的參數，運算完之後，function 的結果再跟下一個元素繼續丟 function 運算，算到不能再算為止。

1
2
3

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

Built-in Functions — Python 3.13.2 documentation

bisect — Array bisection algorithm — Python 3.13.2 documentation

itertools — Functions creating iterators for efficient looping — Python 3.13.2 documentation

math —- 數學函式 — Python 3.13.2 說明文件

【筆記】Python I/O 優化 – Yui Huang 演算法學習筆記

[I/O 優化] PYTHON 篇

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

IO優化

輸入優化

輸出優化

相關應用

多個變數輸入處理

math 模組

eval()

ord()

sum()

進制轉換

bin()：轉二進位函數

oct()：轉八進位函數

hex()：轉十六進位函數

排序方法

sorted()

sort()

sorted() v.s sort()

zip()

enumerate()

生成式（Comprehension）

deque（雙端佇列）

bisect（二分搜）

排列組合好幫手：itertools

lambda應用：三大常用函數

map()

filter()

reduce()

參考資料