【競プロ】Python codonの使い方(仮) 変更点編

2025年11月1日(土)に実施されたAtCoderジャッジアップデートで、高速なPythonコンパイラである「codon」が使えるようになりました。
codonの特徴を一言で言えばじゃじゃ馬です。不便な点が多く動作はまだまだ不安定ですが、実行速度だけは圧倒的で、同一文法のPyPyの比にならないほどに高速です。
特に従来のPython・PyPyは速度不安を抱えていましたから、互いの短所をカバーし合えるcodonは相性抜群です。
Pythonユーザーの皆さん、codonをまずはサブウェポンとして起用してみませんか。

本記事は変更点編です。
長話はいい、さっさとcodonを使いたい！という人は、次のテンプレ・ライブラリ編からご覧ください。

codonの長所・短所

長所は圧倒的な実行速度です。ABC405Cのfukubutyoさんの別解のように、単純な演算だけでもPyPy3の約3倍速です。
更にPyPy3はタプルや再帰が苦手でメモリ効率も極めて悪いので、PyPy3に不利な要素が増えるほどcodonとの差は広がります。

提出例: codon (49ms, 28MiB), PyPy3 (174ms, 152MiB)

ABC405C 提出例

ABC405C O(M^2)

#PyPy3のみ、入力高速化
import sys
input = sys.stdin.readline

#入力受取
N: int = int(input())
A: list[int] = list(map(int, input().split()))

#頻度分布を作成
M: int = max(A)
C: list[int] = [0] * (M + 1)
for Ai in A:
    C[Ai] += 1

#Ai, Ajの値を決め打ち、答えに加算
ans: int = 0
for Ai in range(M + 1):
    for Aj in range(Ai + 1, M + 1):
        ans += Ai * Aj * C[Ai] * C[Aj]
for Ai in range(M + 1):
    ans += Ai * Ai * C[Ai] * (C[Ai] - 1) // 2

#答えを出力
print(ans)

筆者の体感ですが、codonとPythonでは3～5倍近くの速度差があると感じています。「PyPyだから通せなかった」「PyPyだから最初から定数倍を意識した特殊なコードを書こう」といった苦しい状況も、codonなら解決してくれます。
使わない手はありません。

一方で短所として不安定さが挙げられます。
筆者が発見しただけでも、以下のバグや仕様変更が埋まっていました。
これらはどれも原因特定が困難であり、コンテスト中に踏むと致命的です。従って最初から完全にcodonメインに乗り換えるのはおすすめできません。
あくまでPython・PyPyのサブウェポンとして、相性補完としての起用をおすすめします。

1. 型推論バグ

関数内で配列名Tを使うと、型予測に失敗してエラーになります。

型推論

#関数内で配列名Tを使うとバグを起こす
def ABC325D():
    N: int = 4
    T: list[int] = [200, 150, 130, 320]  #イベントiの時刻(Time)
    
    #T[i]の昇順にiをソートしたい
    for i in sorted( range(N), key = lambda x: T[x] ):
        print(i)

ABC325D()
# → error: during the realization of %_lambda_89(x: int, T: TypeWrap[int])


#Tを他の文字(ここではAとした)に変更すれば大丈夫
def ABC325D_2():
    N: int = 4
    A: list[int] = [200, 150, 130, 320]  #T → Aに変更
    for i in sorted( range(N), key = lambda x: A[x] ):
        print(i)

ABC325D_2()
#→ 2, 1, 0, 3

2. pynumerics

ローカル環境限定ですが、import internal.pynumericsでcodonの除算規則をPythonと同様に変更できます。
ですがこれには大きな罠があり、内部で1.0 / 0.0 = infでfloat infを生成していた箇所が全部ZeroDivisionErrorを起こすようになります。
具体例として、 hash(float) を取る以下の操作は全部バグります。
危険すぎるので pynumericsは非推奨です 。

ZeroDivisionError暴発バグ

import internal.pynumerics

print(hash(1.0))  #→ ZeroDivisionError: float division by zero
D: dict[float, int] = {1.0: 100, 2.0: 400}  → ZeroDivisionError
S: set[float] = {1.0, 2.2, 3.4}  #→ ZeroDivisionError

3. match / case文

codonのmatch / case文の挙動が不安定です。
原因ははっきりしませんが、仮説としてcontinueが起因のバグと予想しています。

match / case文

for Xi in range(5):
    match Xi:
        case 0:
            print(f'case 0, matches: {Xi = }')
            continue  #for Xiに戻ってほしい
        case 1:
            print(f'case 1, matches: {Xi = }')
        case _:  #ワイルドカード: マッチングしなかった場合はここ
            print(f'case _, matches: {Xi = }')
# → case 0, matches: Xi =0 が無限に出力される

4. 関数内関数のバグ

関数内で関数を定義したときの変数の挙動が怪しいです。
twitterで報告したところ、issueを建ててもらえました。詳細はこちらのissueをご覧ください。

5. 同時代入の処理順変更

codonでは、同時代入の代入順序が結果に影響します。

同時代入

#A[i: 3] ← 4 と変更してから i ← 4 と変更したい
#Python・PyPy3は2つの実行結果が同じになるが、codonでは代入順序で結果が変わる
A: list[int] = [-5, -4, -3, -2, -1]
i: int = 3
A[i] = i = 4
print(A, i)  #[-5, -4, -3, -2, 4] 4  i ← 4 を先に実行してからA[i]にアクセス


A: list[int] = [-5, -4, -3, -2, -1]
i: int = 3
i = A[i] = 4
print(A, i)  #[-5, -4, -3, 4, -1] 4  A[i: 3] ← 4 を実行してからi ← 4 を実行

6. 多重代入の仕様変更

Python・PyPyと異なり、左辺と右辺の要素数が異なる場合も代入ができてしまいます。
入力の受け取りや配列渡しで潜在的なバグを起こす可能性があります。

多重代入

#左辺の要素数 < 右辺の要素数 でも代入ができてしまう
N, M = 1, 2, 3
print(N, M)  #(N, M) = (1, 2)

#入力受取時に変数が足りなくてもエラーにならない
S: str = '4 5 6 7'
X, Y = list(map(int, S.split()))
print(X, Y)  #(X, Y) = (4, 5)

codonの仕様変更 ピックアップ

codonのコードはPythonとそこそこ互換がありますが、意外な変更点も多数あります。
特に重要な変更点をピックアップします。長いので飛ばし飛ばし読んでください。

型厳格

codonは変数宣言時に型を決める必要があります。
とはいえ大抵はcodon側が自動推論してくれるので、慣れないうちはあえて書く必要はありません。
もし問題が起きるようなら、Pythonの型ヒントの構文で適宜型指定してください。

型指定 その1

#型はcodonが自動推論してくれる
a = 1
b = 2.0
c = 'abc'
print(a, b, c)  #1 2 abc
print(type(a), type(b), type(c))  #<class 'int'> <class 'float'> <class 'str'>

#型指定が必要な場合、型ヒントの構文を使う
i: int = 1
j: float = 2.0
k: str = 'abc'
L: bool  #変数と型だけ先に指定する構文
print(i, j, k, L)  1 2 abc False

#同一変数名に異なる型を使うのは、可能だが非推奨(予期しない型推論エラーの原因)
Xi, Yi = '1.123456 54321.01'.split()
print(Xi, Yi, type(Xi), type(Yi))  #1.123456 54321.01 <class 'str'> <class 'str'>
Xi, Yi = float(Xi), float(Yi)
print(Xi, Yi, type(Xi), type(Yi))  #1.12346 54321 <class 'float'> <class 'float'>

#悪い例: 多重代入や配列代入では型ヒントは使えない
Pi: int, Qi: int = 1, 2  #error: syntax error, unexpected ':'
Pi: int = Qi: int = 1  #error: syntax error, unexpected ':'
D: list[int] = list(range(4))
D[3]: int = 100  #Assert failed: unexpected type annotation

特にlist・set・dictといったコレクション型には、宣言した型と同じ型の要素しか入れられません。
コンテストでもABC335Dの出力形式のように、同一配列にint型とstr型を混在させたい場面はあるのですが、codonでは原則できません。諦めてPyPyを使ってください。

型厳格

#list
A: list[int] = [1, 2, 3]  #listの要素の型はintに限定される
A.append('abc')   #error: 'str' does not match expected type 'int'


#set
B: set[str] = {'a', 'bc', 'def'}
B.add('ghij')  #同じstr型の要素を追加
print(B)  #{'a', 'bc', 'ghij', 'def'}


#dict: キーがint・要素がboolで宣言
C: dict[int, bool] = {1: True, 10: False}
C[2] = True
print(C)  #{1: True, 10: False, 2: True}

#dict: キーの型と要素の型、どちらも変えてはいけない
C['100'] = True  #error: 'str' does not match expected type 'int'
C[100] = 'True'  #error: 'str' does not match expected type 'bool'

codonでは、異なる型同士を==や!=で比較することはできません。
どうしても比較が必要な場合、擬似的にisで比較してください。

型比較

a: int = 1
b: bool = True

#異なる型はisで比較する
print(a == b)  #error: unsupported operand type(s) for ==: 'int' and 'bool'
print(a is b)  #False

関数を型指定する場合、以下のようにつけます。

関数に型ヒント 1

#引数・返り値の型指定
def gcd(x: int, y: int) -> int:
    'コメント: xとyの最大公約数を返します。ただし、gcd(0, 0)は0とします。'
    return gcd(y, x % y) if y else abs(x)

#返り値がint または Noneの場合: Optionalを使う
def isqrt(n: int) -> Optional[int]:
    '''
    コメント: n < 0 の場合、Noneを返します。
    そうでない場合、m ** 2 <= n < (m + 1) ** 2 を満たす非負整数mを返します。
    '''
    if n < 0:
        return None
    if n >= 3037000499 ** 2:  #floor( √(2 ** 63 - 1) ) = 3037000499
       return 3037000499
    m: int = int(float(n).sqrt())  #codonではfloat.sqrt()が可能
    while m * m < n:
        m += 1
    while m * m > n:
        m -= 1
    return m

クラスは インスタンス変数を事前に変数宣言する必要があります 。
最低限変数名の確保ができればcodonが型推論で補ってくれますが、動作の安定のためにも可能な限り型指定をしておきましょう。
以下のように、クラス変数と同じ位置に書いてください。

インスタンス変数の型指定

class UnionFind:
    #インスタンス変数: self.xxx として使う変数 の型指定
    N: int
    parent: list[int]

    def __init__(self, N: int) -> None:
        self.N = N
        self.parent = [-1] * N

#最終手段: (インスタンス変数) = None とでもしておけばcodonがなんとかしてくれる
class nCr_mod_P:
    #インスタンス変数 型の書き方が分からないので全部Noneにしてみた
    #ただしこの場合 __init__で型変更するので、__slots__は使わないこと(エラーになる)
    P = None
    fact = None
    finv = None

    def __init__(self, maxN: int, P: int) -> None:
        assert 0 <= maxN < P
        self.P = P
        self.fact = [1] * (maxN + 1)
        self.finv = [1] * (maxN + 1)

        for i in range(2, maxN + 1):
            self.fact[i] = self.fact[i - 1] * i % P
        a, b, x, y = self.fact[maxN], P, 1, 0  #finv[N] = x = pow(N!, -1, P) を計算
        while b:
            q = a // b
            a, b, x, y = b, a - q * b, y, x - q * y
        assert a == 1
        self.finv[maxN] = x if x >= 0 else x + P
        for i in range(maxN, 1, -1):
            self.finv[i - 1] = self.finv[i] * i % P

    def comb(self, n: int, k: int) -> int:
        if not 0 <= k <= n:
            return 0
        else:
            return self.fact[n] * self.finv[k] % self.P * self.finv[n - k] % self.P

#実行 型推論できている
nCr = nCr_mod_P(5, 998_244_353)
print(nCr.fact)  #[1, 1, 2, 6, 24, 120]
print(nCr.finv)  #[1, 1, 499122177, 166374059, 291154603, 856826403]
print(nCr.comb(5, 2))  #10

関数やクラスには型ジェネリクスを指定することも可能です。
抽象的に型を受けたい時はもちろん、特定の型の書き方が分からない場合の回避策として大活躍します。
ただしバージョンの都合上、 PyPy3.11との互換がなくなる点に注意してください 。

型ジェネリクス

#関数の型ジェネリクス: []内で抽象型を指定
def outer_product[T](P: tuple[T, T], Q: tuple[T, T]) -> T:
    '二次元ベクトルの外積を計算します。正ならQはPから見て反時計回り側です。'
    return P[0] * Q[1] - P[1] * Q[0]

def inner_product[T](P: tuple[T, T], Q: tuple[T, T]) -> T:
    '二次元ベクトルの内積を計算します。0ならPとQは直交します。'
    return P[0] * Q[0] + P[1] * Q[1]


A: tuple[int, int] = (1, 2)
B: tuple[int, int] = (2, -1)
print( outer_product(A, B) )  #-5
print( inner_product(A, B) )  #0


#クラスの型ジェネリクス
class BinaryIndexedTree[T]:  #方法1. クラス名の隣に[]で囲って宣言する
    N: int
    node: list[T]
    def __init__(self, N: int) -> None:
        self.N = N
        self.node = [T(0)] * (N + 1)
    def add(self, i: int, value: T) -> None:
        'A[i] += value'
        i += 1
        while i <= self.N:
            self.node[i] += value
            i += i & - i
    def sum(self, i: int) -> T:
        'sum(A[0], A[1], ･･･, A[i])'
        i += 1
        ans: T = T(0)
        while i > 0:
            ans += self.node[i]
            i ^= i & - i
        return ans

BIT = BinaryIndexedTree(5)
BIT.add(0, 3.6)  #float型で追加
BIT.add(1, 1.3)
print(BIT.sum(2))  #4.9


class SegmentTree:  #方法2. クラス内でT: type として宣言する
    T: type

    N: int
    logN: int
    size: int
    node: list[T]
    identity_e: T
    node_func: Function[tuple[T, T], T]
    def __init__(self, N: int, e: T, f: Function[tuple[T, T], T]) -> None:
        self.N = N
        n = max(0, N - 1)
        self.logN = 0
        while n > 0:
            n >>= 1
            self.logN += 1
        self.size = 1 << self.logN
        self.identity_e = e
        self.node_func = f
        self.node = [e for _ in range(self.size << 1)]

ST = SegmentTree(10, 0, lambda x, y: x + y)
print(ST.T)  #<class 'int'>

intの仕様変更

codonのintは符号つき64bit整数であり、$-2^{63} \leq n \leq 2^{63} - 1$を満たす整数nが表現範囲です。
この表現範囲を超えると、Pythonでは自動的に多倍長整数に切り替わりますが、 codonではオーバーフローします 。

オーバーフロー

n: int = ~(-1 << 63)
print(n)  #9223372036854775807 = 2 ** 63 - 1
n += 1
print(n)  #-9223372036854775808 = - 2 ** 63

#x * yで符号つき64bit整数の表現範囲を超え、オーバーフロー
x: int = 10 ** 10
y: int = 10 ** 10
z: int = 10 ** 18
print(x * y)  #codon: 7766279631452241920, Python: 10 ** 20
print(x * y % z)  #codon: 766279631452241920, Python: 0

#ちなみにpowもしれっとオーバーフローする
print(pow(x, 2, z))  #codon: 766279631452241920, Python: 0

codonにも多倍長整数クラスがあるので、どうしてもオーバーフローしてしまう場面では切り替えて使ってください。
さしあたりは符号つき128bit整数 i128 だけ覚えておけば十分だと思います。表現範囲は$-2^{127} \leq n \leq 2^{127} - 1$です。

多倍長整数

x: i128 = i128(10 ** 10)
y: i128 = i128(10 ** 10)
z: i128 = i128(10 ** 18)
print(x * y)  #100000000000000000000 = 10 ** 20
print(x * y % z)  #0

#演算は同じ型同士に限る
print(i128(100) * int(10))  #error: unsupported operand type(s) for *: 'Int[128]' and 'int'
print(i128(100) * i128(10))  #1000
print(i128(1) << i128(10))  #1024


#以下参考: 符号つきNbit整数は Int[N] として表記する
n = Int[201](10) ** Int[201](60)
print(n)  #1000000000000000000000000000000000000000000000000000000000000 = 10 ** 60

#符号なしNbit整数は UInt[N] として表記する
m = UInt[200](10) ** UInt[200](60)
print( m == UInt[200](n) )  #True

#ただし、N > 128 では除算できないので注意
x = Int[129](10)
y = Int[129](1)
print(x // y)  #error: division is not supported on Int[N] when N > 128
print(x % y)  #error: modulus is not supported on Int[N] when N > 128

デフォルトの除算方向も変わっています。
Pythonでは「負の無限大丸め」でしたが、codonでは「ゼロ方向丸め」です。
ただし後述しますが、これは各自で変更可能です。

除算方向の変更

#codonは割られる数の符号(±20)とあまりの符号(±2)が一致する
#Pythonは割る数の符号(±3)とあまりの符号(2, 1, -1, -2)が一致する
print( 20 //  3,  20 %  3)  #codon: ( 6,  2), Python: ( 6,  2)
print(-20 //  3, -20 %  3)  #codon: (-6, -2), Python: (-7,  1)
print( 20 // -3,  20 % -3)  #codon: (-6,  2), Python: (-7, -1)
print(-20 // -3, -20 % -3)  #codon: ( 6, -2), Python: ( 6, -2)

#ただしdivmodは実装上、Pythonと同様の演算結果になるように補正が入る
print(divmod( 20,  3))  #codon・Python: ( 6,  2)
print(divmod(-20,  3))  #codon・Python: (-7,  1) 
print(divmod( 20, -3))  #codon・Python: (-7, -1)
print(divmod(-20, -3))  #codon・Python: ( 6, -2)

#intだけでなく、符号つき多倍長整数でも除算仕様が変更されている
print(i128(-20) // i128(3), i128(-20) % i128(3))  #(-6, -2)
print(divmod(i128(-20), i128(3)))  #(Int[128](-7), Int[128](1))


#参考: ビットシフトはいわば「負の無限大丸め」のまま
print(-51 // 8)  #-6
print(-51 >> 3)  #-7

tupleの仕様変更

codonのタプルは固定長限定です。簡単に言えば、コード中に丸括弧で囲って書いたタプルだけがタプルです。
公式ドキュメントによるともっと奥が深そうですが、これは一旦横に置いておきます。

なおPyPy3のタプルは動作が遅すぎることで有名でしたが、codonのタプルは爆速です。安心してご利用ください。

tuple

#良い例: コード中で ( ) で囲って書いたタプルは従来通り使える
P: tuple[int, str] = (1, 'abc')

#Pythonではエラーになるが、おそらくこの記法も大丈夫？
Q = tuple(0, True, 2, '3')
print(Q)  #(0, True, 2, '3')


#悪い例: tuple( list ) のような変換はできない
R = tuple([1, 2, 3, 4])  #変換だけならエラーにならない
print(type(R))  #<class 'Tuple[int,Array[int]]'>
print(R)  #error

#悪い例: list(range(4)) = [0, 1, 2, 3] を期待したのに勝手に壊れている
S = tuple(range(4))
print(S)  #(0, 4, 1)

地味ながらやっかいな変更なので補足します。
例えばABC430Bのようにsetやdictに任意長tupleを入れたいケースでは、Pythonのコードをそのままcodonで動かすとタプル変換でエラーになってしまいます。
ですが実は、codonは仕様変更で listがそのままsetやdictに入るようになっています 。なのでPyPy3のACコードから、list → tupleの変換を削除すれば大丈夫です。

ABC430B codon

#入力受取
N, M = list(map(int, input().split()))
S: list[str] = [input() for _ in range(N)]

#set Aを宣言
A: set[list[str]] = set()

#MxM領域を切り取り、list[str]のまま集合Aに追加
for Lh in range(N - M + 1):
    for Lw in range(N - M + 1):
        B: list[str] = [S[h][Lw: Lw + M] for h in range(Lh, Lh + M)]
        A.add(B)

#答えを出力
print(len(A))

また、長さや要素の順序が異なるタプルは別の型として認識します。
不要な部分を埋めて型を統一するか、要素が同一ならlistに変換して処理してください。

タプルの長さ・要素順合わせ

#0 i c: S[i]を英小文字cに変更
#1 c: 文字列Sに含まれる英小文字cの個数を出力
query = []
query.append((0, 1, 'a'))
query.append((1, 'b'))  #error: 'Tuple[int,str]' does not match expected type 'Tuple[int,int,str]'


#tuple[int, int, str]と決め、空欄は適当に埋めて要素順や長さを合わせて対応する
query: list[tuple[int, int, str]] = [(0, 1, 'a'), (1, -1, 'b')]


#すべての要素が同じ場合は、listに変換してもいい
S = {(0, ), (0, 1)}  #error: 'Tuple[int,int]' does not match expected type 'Tuple[int]'

T: set[list[int]] = {[0], [0, 1], [0, 1, 2]}
print(T)  #{[0, 1, 2], [0], [0, 1]}

ライブラリ対応状況

公式ドキュメントの通り、codonは標準ライブラリを含めて未対応のものが多いです。
@pythonでPythonで処理することもできますが、呼び出しごとに1ms以上の巨大なオーバーヘッドが入るようなので使える場面は皆無といっていいでしょう。

kemunikuさんのまとめとも重複しますが、特に気になった点を列挙します。
ちなみに対策ですが、足りないものは都度自作すればいいです。とても簡単ですね。

組み込み関数

• bytearray, bytes: UInt[8]の配列で代用可能
• classmethod, staticmethod
• eval, exec
• exit: sys.exit()で疑似対応ができそうだが検証中
• frozenset: 計算量は悪いが、sorted(set)などで代用
• __import__, __builtins__

標準ライブラリ

• math: dist, isqrt, combがない
• numpy: base_repr(進数変換)ができない
• itertools: だいたいある。permutations, combinationsの返り値はタプル・リストどちらもあり得るなので注意(コンパイル時固定長ならタプル)。
  リストのアンパッキングができなくなっているので、productによる直積列挙が困難になっている
• decimal: 存在しない。かわりにfloat128が使えるが、機能が不十分なので開発待ち
• fractions: 存在しない。タプルでそれっぽいのは作れる
• collections: dequeのランダムアクセスが$O(1)$になっていて嬉しい
• sys: stdin.readlineがないが、入出力は高速なので不要。(stdin.read や stdout.writeはある)
  setrecursionlimitは存在しないが、実験上5 * 10 ** 7回の再帰に耐えたので問題なし

検証・自作など

DIYコードなどをおいておきます。
動作保証はありません。

isqrt メモ

#note: float(n) ** 0.5 だと実測上 u128 → 1500 程度 の誤差が生じる
def isqrt[T](n: T) -> T:
    assert n >= T(0)
    m: T = T( float(n).sqrt() )
    m2: T = m * m
    while m2 < n:
        m2 += m << T(1) | T(1)
        m += T(1)
    while m2 > n:
        m -= T(1)
        m2 -= m << T(1) | T(1)
    return m

math.isqrtの多倍長拡張を考えていましたが、floatを介すると精度が全く足りません。
float128は現状多倍長キャストに対応していないので、サボるのは難しそうです。素直に二分探索を書いた方がいい気がします。

fractions.Fraction の代用になるかも

def compare[T](A: T, B: T, C: T, D: T) -> int:
    '''
    コメント: A / B と C / D の大小比較を行います。
    A / B  < C / D なら -1
    A / B == C / D なら 0
    A / B >  C / D なら +1 を返します。
    制約: B != 0, D != 0, 除算が可能(int, Int[<= 128], UInt[<= 128])
    計算量: 除算1命令の計算量をL, M = max(A, B, C, D)として O(L logM)
    '''
    assert B != T(0) and D != T(0)
    assert isinstance(T, int) or isinstance(T, Int) or isinstance(T, UInt)
    
    #符号の正規化
    if B < T(0):
        A, B = - A, - B
    if D < T(0):
        C, D = - C, - D
    if A ^ C < T(0):  #A / B と C / D の符号が異なる場合
        return -1 if A < T(0) else +1
    if A & C < T(0):  #両方の符号が負の場合
        A, B, C, D = - C, D, - A, B
    assert A >= T(0) and B > T(0) and C >= T(0) and D > T(0)

    #帯分数で比較: 積を取って AD / BD と BC / BD を大小比較したほうが絶対早い
    while True:
        div_A, rem_A = A // B, A % B
        div_C, rem_C = C // D, C % D
        if div_A < div_C:
            return -1
        elif div_A > div_C:
            return +1
        elif rem_A == T(0) or rem_C == T(0):
            return 0 if rem_A == rem_C == T(0) else -1 if rem_A == T(0) else +1
        else:
            A, B, C, D = D, rem_C, B, rem_A


print(compare(22, 7, 314, 100))  #+1: 22 / 7 ≒ 3.1429 > 314 / 100

itertools.product

#2次元リストの直積を作る
def product[T](A: list[list[T]]) -> generator[list[T]]:
    if len(A) == 0 or any(len(A[i]) == 0 for i in range(len(A))):
        return
    N: int = len(A)
    B: list[T] = [A[i][0] for i in range(N)]
    C: list[int] = [0] * N
    while True:
        yield B  #コピーするなら yield B[:]
        i: int = N - 1
        C[i] += 1
        while i >= 0 and C[i] == len(A[i]):
            if i == 0:
                return
            C[i] = 0
            C[i - 1] += 1
            i -= 1
        while i < N:
            B[i] = A[i][C[i]]
            i += 1


for S in product([ [1, 2], [3, 4], [5, 6, 7] ]):
    print(S)
#実行結果は順に
# [1, 3, 5], [1, 3, 6], [1, 3, 7], [1, 4, 5], [1, 4, 6], [1, 4, 7],
# [2, 3, 5], [2, 3, 6], [2, 3, 7], [2, 4, 5], [2, 4, 6], [2, 4, 7]

再帰深さ検証

import random
def f(n: int, stop: int) -> int:
    if n == stop:
        random.seed(n)
        return random.getrandbits(31)
    else:
        return f(n + 1, stop) ^ random.getrandbits(31)

print(f(0, stop = 5 * 10 ** 7))  #189390371

AtCoder環境ではこの再帰が 580ms・770MiB で動作します。
ちなみにローカル環境だと2 * 10 ** 5回の再帰で落ちます。スペック差ですね。(終)

その他

巻きでいきます

再帰

PyPy3ではなぜか遅かった再帰関数ですが、codonでは安定して動作します。
これまでのようにstackで非再帰化する必要はありません。

DFS 速度比較

以下のコードで比較すると、PyPy3 600ms/580MiB, codon 110ms/110MiB程度でした。(終)

codon vs PyPy3 DFS比較

'''
#PyPy3の時のみ、以下の2つをインポート
import sys
sys.setrecursionlimit(10 ** 6)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
'''

#N頂点のパスグラフの端点から、最遠点(もう片方の端点)までの距離を求める
N: int = 5 * 10 ** 5
G: list[list[int]] = [[] for _ in range(N)]
for i in range(N - 1):
    G[i].append(i + 1)
    G[i + 1].append(i)

def dfs(now: int, back: int) -> int:
    max_dist: int = 0
    for nxt in G[now]:
        if nxt != back:
            max_dist = max(max_dist, dfs(nxt, now) + 1)
    return max_dist

assert dfs(0, -1) == N - 1

アンパッキング

アンパッキングができるのはタプルだけです。

アンパッキング

#タプルのアンパッキングは従来通り可能
A: tuple[int, int, str] = (1, 2, 'san')
print(*A)  #1 2 san

#リストのアンパッキングはできない
B: list[int] = [0, 1, 1, 2, 3, 5, 8]
print(*B)  #error: argument after * must be a tuple, not 'List[int]'

#print(*list) は' '.join() で代用する
C: list[int] = [5, 16, 8, 4, 2, 1]
print(' '.join(str(Ci) for Ci in C))  #5 16 8 4 2 1

#関数へのアンパッキングにも支障が出る
import math
print( math.lcm(3, 4, 5) )  #60
print( math.lcm(*(3, 4, 5)) )  #60
print( math.lcm(*[3, 4, 5]) )  #error: argument after * must be a tuple, not 'List[int]'

generatorの仕様変更

generatorに__getitem__, __contains__が定義されていません。
特にmapでの入力受取はできなくなっています。
list(map)のようにlistを挟むか、後述の拡張機能を使いましょう。

map受け取り

#初期設定ではmap受け取りができない
N, M = map(int, '1 2'.split())  #error: 'Generator[int]' object has no attribute '__getitem__'

#右辺をlist(map) に変更すれば大丈夫
N, M = list(map(int, '1 2'.split()))
print(N, M)  #(N, M) = (1, 2)

float

除算仕様変更により、 1.0 / 0.0の結果がZeroDivisionErrorからinfに変更されました。
先述の通り、この仕様は変更しないことを推奨します。変更するとhash(float)でバグります。

float 除算仕様変更

print(1.0 / 0.0)  #inf
print(float('inf') / float('inf'))  #nan
print(float('inf') - float('1e308'))  #inf

codonの初期設定では、floatの出力桁数が非常に少ないです。
必要に応じてformat文で出力桁数を増やす必要があります。
なお、ローカル環境ではkenunikuさんの記事にあるLinuxコマンドを実行しておく必要があります。

なお、float128の出力桁数指定はうまくいっていません。
解決策が見つかれば追記します。

floatの出力桁数

a: float = 123456789.012345
print(a)  #1.23457e+08

b: float = float('1.23457e+08')
print(b)  #1.23457e+08
print(a < b)  #True
print(b - a)  #210.988  表示以上に有効数字がある

#formatはf stringで指定する
#print('{:15f}'.format(a))  #error: ''{:15f}'' object has no attribute 'format'
print(f'{a:15f}')  #123456789.012345
print(f'{b:15f}')  #123457000.000000

codonの新機能 ピックアップ

今後のライブラリ魔改造に関係する、@overloadと@extendだけ説明します。

overload

同じ関数名に複数の異なる関数を重ねることができます。
クラス内関数は@overloadを書かなくても自動でオーバーロードするようですが、書いて損は無いと思います。

overload

def range_sum(Rt: int) -> int:
    '0以上Rt未満の整数の総和を返します。'
    assert 0 <= Rt
    return Rt * (Rt - 1) // 2

@overload
def range_sum(Lt: int, Rt: int) -> int:
    'Lt以上Rt未満の整数の総和を返します。'
    assert 0 <= Lt <= Rt
    return (Rt * (Rt - 1) // 2) - (Lt * (Lt - 1) // 2)

@overload
def range_sum(Lt: str, Rt: str) -> str:
    '辞書順が英小文字Lt以上英小文字Rt未満の小文字を連結して出力します。'
    assert Lt <= Rt
    assert Lt.islower() and Rt.islower()
    assert len(Lt) == len(Rt) == 1
    return ''.join(chr(i) for i in range(ord(Lt), ord(Rt)))


print( range_sum(4) )  #6 : 0 + 1 + 2 + 3  int1引数のrange_sum
print( range_sum(2, 6) )  #14: 2 + 3 + 4 + 5  int2引数のrange_sum
print( range_sum('a', 'e'))  #abcd  str2引数のrange_sum

extend

@extendで既存のクラスに新しい機能を追加できます。
codonの快適化に一役買っているぶっ壊れ機能です。
早速ですが、例としてintの除算方向をPythonと同様の負の無限大丸めに修正してみましょう。
githubのintのコードや、pynumericsのコードや、divmodの実装を参考にしつつ変更コードを書いてみます。

int除算パッチ

#int同士の除算結果をPythonの負の無限大丸めに合わせる
@extend
class int:
    @pure
    @llvm
    def _floordiv_int_int(self: int, other: int) -> int:
        %0 = sdiv i64 %self, %other
        ret i64 %0
    @overload
    def __floordiv__(self, other: int):
        d = self._floordiv_int_int(other)
        m = self - d * other
        if m and ((other ^ m) < 0):
            d -= 1
        return d
    @pure
    @llvm
    def _mod_int_int(self: int, other: int) -> int:
        %0 = srem i64 %self, %other
        ret i64 %0
    @overload
    def __mod__(self, other: int) -> int:
        m = self._mod_int_int(other)
        if m and ((other ^ m) < 0):
            m += other
        return m

これをテンプレに貼るだけで、除算方向がPythonと同じ負の無限大丸めに変わります。
実際に以下のコードで確認可能です。

確認用コード

extendの変更を行わないと、-1000 // 3 = -333, -1000 % 3 = -1で落ちると思います。

確認用コード

#int同士の除算結果をPythonの負の無限大丸めに合わせる
@extend
class int:
    @pure
    @llvm
    def _floordiv_int_int(self: int, other: int) -> int:
        %0 = sdiv i64 %self, %other
        ret i64 %0
    @overload
    def __floordiv__(self, other: int):
        d = self._floordiv_int_int(other)
        m = self - d * other
        if m and ((other ^ m) < 0):
            d -= 1
        return d
    @pure
    @llvm
    def _mod_int_int(self: int, other: int) -> int:
        %0 = srem i64 %self, %other
        ret i64 %0
    @overload
    def __mod__(self, other: int) -> int:
        m = self._mod_int_int(other)
        if m and ((other ^ m) < 0):
            m += other
        return m


for a in range(- 1000, 1001):
    for b in range(- 1000, 1001):
        if b == 0:
            continue
        div, mod = a // b, a % b
        assert div * b + mod == a
        if b > 0:
            assert 0 <= mod < b
        else:
            assert b < mod <= 0
else:
    print('OK')

関数の変更ができるなら追加もできるので、例えばcodonで削除されたint.bit_length, int.bit_countを復活させたり、listにrandom.choiceやrandom.shuffleのような機能を持たせることもできます。
根幹の変更なので思わぬバグの原因になりうるんですが、その時はその時です。

おわりに

主要な変更点はこれくらいだと思います。
記事が長くなったので、使い方編は次の記事にします。