はじめに
競技プログラミングサイトのAtCoderにおいて、コンテストジャッジ環境のアップデートが行われました。
それに伴って、ジャッジ環境で動くPythonのバージョンが変更になっています。
本記事では、便利そうなものをピックアップして整理したいと思います。
2023/10/21 追記
基本的に便利になっているのですが、アップデート前ではACできるコードがアップデート後にはできなくなるものがあるので追記します。
対象
Python勢はPyPyを利用している人が多いと思います。従い、
- 旧:PyPy 7.3.0 (Python 3.6.9相当)
- 新:PyPy 7.3.12 (Python 3.10.12相当)
この間で追加された標準ライブラリ等の変化点をまとめます。
なお、外部ライブラリも追加されていますが、本記事では対象外としています。
ただ、atcoderライブラリのPython移植版や、sortedcontainers、networkxなど、
便利なライブラリがPyPyで使えるようになったので、かなりアリです。
(networkxは速度ちょっと厳しいですが…）
調査のアプローチ
CPythonのDocから正規表現で検索し、競プロの観点で関係しそうなものを列挙します。
version.*:: 3.[7-9]
version.*:: 3.1[01]
内容
項末尾が追加されたバージョンです。
使えそうなの
powにおける負の指数 (3.8)
modにおける積の逆元を求める時に有用です。
以前だとMOD-2でやっていましたが、それだとMODが素数である必要がありました。その点が解消。
Python 3.10.12 (af44d0b8114cb82c40a07bb9ee9c1ca8a1b3688c, Jun 15 2023, 12:39:27)
[PyPy 7.3.12 with GCC 10.2.1 20210130 (Red Hat 10.2.1-11)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>> pow(3,-1,7)
5
>>>> pow(3,7-2,7)
5
>>>> pow(3,-1,8)
3
>>>> pow(3,8-2,8)
1
sumの開始位置指定 (3.8)
そのまま。
Python 3.10.12 (af44d0b8114cb82c40a07bb9ee9c1ca8a1b3688c, Jun 15 2023, 12:39:27)
[PyPy 7.3.12 with GCC 10.2.1 20210130 (Red Hat 10.2.1-11)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>> X=list(range(10))
>>>> sum(X,start=3)
48
ただ、きっちりリスト長に依存した時間はかかりそう。
Python 3.10.12 (af44d0b8114cb82c40a07bb9ee9c1ca8a1b3688c, Jun 15 2023, 12:39:27)
[PyPy 7.3.12 with GCC 10.2.1 20210130 (Red Hat 10.2.1-11)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>> from time import time
>>>> def measure():
.... N=10**8
.... target=list(range(N))
.... s=time()
.... total=sum(target,start=N-1)
.... e=time()
.... print(f"{e-s:.3f}s")
....
>>>>
>>>> measure()
0.088s
accumerateの初期値の指定 (3.8)
累積和を取るのに重宝するaccumulateでしたが、初期値の設定ができるようになりました。
>>>> from itertools import accumulate
>>>> list(accumulate(range(5),initial=10))
[10, 10, 11, 13, 16, 20]
cache() == lru_cache(maxsize=None) (3.9)
以前からメモ化再帰を手軽にできたのがさらに短く記述できます。
https://docs.python.org/ja/3/library/functools.html?highlight=lru_cache#functools.cache
https://docs.python.org/ja/3/library/functools.html?highlight=lru_cache#functools.lru_cache
トポロジカルソート (3.9)
トポロジカルソートができる。サイクル検知で例外。
標準ライブラリでできるのに驚きました。
Python 3.10.12 (af44d0b8114cb82c40a07bb9ee9c1ca8a1b3688c, Jun 15 2023, 12:39:27)
[PyPy 7.3.12 with GCC 10.2.1 20210130 (Red Hat 10.2.1-11)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>> from graphlib import TopologicalSorter
>>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>>> ts=TopologicalSorter(graph)
>>>> list(ts.static_order())
['A', 'C', 'B', 'D']
>>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}, "A": {"D"}}
>>>> ts=TopologicalSorter(graph)
>>>> list(ts.static_order())
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/home/mo124121/.pyenv/versions/pypy3.10-7.3.12/lib/pypy3.10/graphlib.py", line 242, in static_order
self.prepare()
File "/home/mo124121/.pyenv/versions/pypy3.10-7.3.12/lib/pypy3.10/graphlib.py", line 104, in prepare
raise CycleError(f"nodes are in a cycle", cycle)
graphlib.CycleError: ('nodes are in a cycle', ['D', 'A', 'C', 'D'])
順列の総数 (3.8)
そのまま。速度は未検証。
ただmodを取る感じでもないので、競プロ文脈だと微妙かもしれない。
>>>> from math import perm
>>>> perm(5,2)
20
二項係数 (3.8)
同上。
>>>> from math import comb
>>>> comb(5,2)
10
gcdが任意の引数の数に対応 (3.9)
今まで2つの数字しか取れなかったのが複数とれるようになりました。for文やreduceの利用が不要に。
なんなら空っぽでもいい、がバグらせそう…
>>>> from math import gcd
>>>> gcd(2,6)
2
>>>> gcd(2,6,8)
2
>>>> gcd(*list(range(2,100,2)))
2
>>>> gcd()
0
整数の平方根 (3.8)
そのままではあるが切り捨てのイメージ。
切り上げしたい場合は1+sqrt(x-1)でやれとのこと。これはたまに使いそうです。
>>>> from math import isqrt
>>>> isqrt(5)
2
>>>> 1+isqrt(5-1)
3
最小公倍数 (3.9)
今まで最大公約数を用いて算出していたものが直接算出できるようになりました。
3つ以上もできます。
>>>> from math import lcm
>>>> lcm(3,5)
15
>>>> lcm(3,5,9)
45
総積 (3.8)
そのまま。どうせならmodとってほしいです。（わがまま）
>>>> from math import prod
>>>> prod([3,8,4])
96
ユークリッド距離 (3.8)
多次元も含めていい感じにとってくれます。
まあ、競プロ文脈だと誤差回避のためにsqrtとらないまま管理したかったりするし、
多次元対応のために速度が犠牲になっていないかは気になるところです。
>>>> from math import dist
>>>> dist([2,5],[4,1])
4.47213595499958
>>>> dist([0,0],[3,4])
5.0
>>>> dist([0,0,5],[3,4,2])
5.830951894845301
ユークリッドノルムの多次元対応 (3.8)
3個以上の要素を持つベクトル（配列）のノルム計算ができるようになりました。さらに3.10以降は誤差が減っているらしいです。
ただやっぱりこの手の奴は整数で管理したい気持ちが強いです。
>>>> hypot(*[1,2,3,4])
5.477225575051661
最頻値 (3.8)
配列の中から最頻値を出力できます。一つの時はmode、複数出したい時はmultmode。
modeは3.7以前からありましたが、複数の最頻値があった時は例外を出す仕様から変更になった模様です。
>>>> from statistics import multimode,mode
>>>> S="aaabbbccddeee"
>>>> mode(S)
'a'
>>>> multimode(S)
['a', 'b', 'e']
これ以外にもstatisticsは統計計算用の関数が様々用意されています。
二分探索でキーを指定できるように (3.10)
二分探索は内部的に要素の比較を行いますが、その比較を行う対象の値の算出方法を記述できます。
他のbisect_left等も同様です。
>>>> from bisect import bisect
>>>> A=[(8,2),(1,5),(2,12)]
>>>> bisect(A,7,key=lambda x:x[1])
2
連続する2つの要素のイテレータ (3.10)
連続するペアをいい感じに出してくれます。個人的おすすめ。
以前はzip(A,A[1:])みたいな感じなのがより直観的に読みやすくなりました。
>>>> from itertools import pairwise
>>>> list(pairwise(range(5)))
[(0, 1), (1, 2), (2, 3), (3, 4)]
f文字列で変数名の表示が可能に (3.8)
手軽に変数も含めてprintができるようになりました。
自分はデバッガ使うのであまり使わないのですが、printデバッグ勢は楽かもしれない。
>>>> x=5
>>>> print(f"{x=}")
x=5
bit_countの追加 (3.10)
立っているbit数を数えることができるやつです。
bitDPとかですでに使った要素数を調べたい時とか。
>>>> x=124
>>>> bin(x)
'0b1111100'
>>>> x.bit_count()
5
match文の追加 (3.10)
クエリ問題なので、if/elseif/elseとか書くことが多かったですが、下記みたいな感じでかけるようになりました。
query = [1, 2]
candidates = set()
match query[0]:
case 1:
candidates.add(query[1])
case 2:
candidates.discard(query[1])
case 3:
print(candidates)
なお、match文はもっといろいろできることがあるので、
単なるif文の代替と捉えずに使いこなすと強そうです。（が、ハマりどころもある認識なので注意）
参考:https://qiita.com/ksato9700/items/3ce4c68c0d713874b693
他に気になったもの
datetime
古い問題とかでたまーにでてくるやつ。
うるう年とかの扱いが楽。
Python 3.11.4 (main, Jul 28 2023, 08:34:53) [GCC 11.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from datetime import date
>>> date.fromisoformat("20220501") # 3.11から
datetime.date(2022, 5, 1)
>>> date.fromisoformat("2022-05-01") # 3.7から
datetime.date(2022, 5, 1)
>>> date.fromisoformat("2022/05/01") # なんかの問題で出てくる、がそのままでは無理、残念
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: Invalid isoformat string: '2022/05/01'
有理数
as_integer_ratioの追加。
（そもそも有理数クラスがあったの知らなかった…使ってるのみたことないけど遅いのかな…？要検証）
Python 3.10.12 (af44d0b8114cb82c40a07bb9ee9c1ca8a1b3688c, Jun 15 2023, 12:39:27)
[PyPy 7.3.12 with GCC 10.2.1 20210130 (Red Hat 10.2.1-11)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>> fractions.Fraction(5,10)
Fraction(1, 2)
>>>> fractions.Fraction(5,10).as_integer_ratio()
(1, 2)
>>>> type(fractions.Fraction(5,10).as_integer_ratio())
<class 'tuple'>
型アノテーション
Listとかのimportが不要に。
前
Python 3.6.9 (1608da62bfc7, Dec 23 2019, 10:50:04)
[PyPy 7.3.0 with GCC 7.3.1 20180303 (Red Hat 7.3.1-5)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>> X:list[int]=[3,4]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
>>>> from typing import List
>>>> X:List[int]=[3,4]
後
Python 3.10.12 (af44d0b8114cb82c40a07bb9ee9c1ca8a1b3688c, Jun 15 2023, 12:39:27)
[PyPy 7.3.12 with GCC 10.2.1 20210130 (Red Hat 10.2.1-11)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>> X:list[int]=[3,4]
breakpoint
3.7で追加。
コード上でブレークポイントを仕込めるらしい。
浮動小数点ちょいずらし(雑) (3.9)
何に使うかはよくわからない。（なら書くな）
>>>> from math import nextafter
>>>> nextafter(-1,0.0)
-0.9999999999999999
cache_property (3.9)
クラス変数を1度だけ計算して使いませる？ なんかテクい感じで使えそうです。
今は思い浮かばないし、そもそも競プロか？
罠
str->int変換において最大桁数の上限が新規追加
int変換を行う際の桁数上限が新たに追加され、上限を超える場合は例外が出ます。
Pythonは多倍長整数を手軽に扱える点が強みの一つでしたが、注意する点が増えてしまっています。
この制約はコード内で変更可能です。（下記参照）
Python 3.10.12 (af44d0b8114cb82c40a07bb9ee9c1ca8a1b3688c, Jun 15 2023, 12:39:27)
[PyPy 7.3.12 with GCC 10.2.1 20210130 (Red Hat 10.2.1-11)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>> v=int("1"*5000)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: Exceeds the limit (4300) for integer string conversion: value has 5000 digits
>>>> import sys
>>>> sys.set_int_max_str_digits(0)
>>>> v=int("1"*5000)
>>>>
必要メモリ量の増加
必要なメモリ量が増えています。
数十MB程度なので2023年現在の一般的な制約である1GB制限においてはコンテスト中は問題ないでしょう。
ただ、過去問で制約が256MBである問題において、制約ギリギリの実装になっている場合は、MLEになって過去ジャッジのACコードが通らない可能性があります。
おわりに
Pythonはpipによる手軽な外部ライブラリの利用が強みの一つですが、標準機能でも利便性が上がっていていいなと思いました。
個人的に、簡潔にコードを書けることはバグを減らすことにつながると考えているので、こういった機能を活用することで、コンテスト中に苦しむ可能性を減らせればいいな、と思います。
履歴
2023/9/9 訂正：階乗→順列の総数 ゴリさん指摘ありがとうございます。
https://twitter.com/prd_xxx/status/1700315858915201209?s=20
2023/9/9 追記：bit_count noriocさん情報ありがとうございます。
https://twitter.com/norioc/status/1700332252050391315?s=20
2023/9/9 追記：match文
2023/9/9 訂正：ノルム関係の説明
2023/10/21 追記:アップデートで増えた罠の追記