[[Codon（AtCoder Language Update 2025 に際して）]]
現在位置: トップページ » アルゴリズム » Python 競プロ用 Tips » Codon（AtCoder Language Update 2025 に際して）

目次

Codon（AtCoder Language Update 2025 に際して）

AtCoder では、2025年10月に予定されているアップデートより、Pythonをコンパイルして高速に動かせる「Codon」が使えるようになる。

まだ調べ始めたばかりだが、第一印象としては「64bit整数・浮動小数点やベクタなどの LLVM の基本的な型が背景にあることを注意して書きさえすれば、既存のPythonを比較的簡単に、大幅高速化できる言語」という感じがした。

未実装の機能はあるものの、型を自動推論してくれることなどで、競プロくらいシンプルなコードならそこそこの割合でPythonコードがそのままコンパイル可能。（ただし、ある程度は型推論“させてあげる”ような書き方が必要。寄り添いって大事）

特徴

比較対象として、Pythonコードを高速化する機能を持つものに、PyPy, Numba, Cython などがある。
（他にもNuitka,mypycなど、Pythonに近い記法で速い言語ならNim,Mojoなどいろいろある）

  • PyPy
    • ◎:Pythonと文法の互換性が高く、そのまま動くことが多い。
      • 他と比較して高速化の程度は弱めだが、基本的に下手な実装をしなければAtCoderではほとんどの問題が通る（はず）。
    • ×:実行時コンパイルのため、実行時間にコンパイル時間が含まれ、100～200ms程度のオーバーヘッドがある。
    • ×:再帰が遅いなど稀に変なハマりポイントがある。
  • Numba
    • ◎:数値計算中心の処理を、手軽に大きく高速化できる。
      • 文字列や独自クラスの扱いは弱め。
    • ×:関数内関数での再帰ができない。
    • ×:コンパイルエラー時のメッセージがちょっと分かりづらい。
    • △:互換性の面で、Numpy配列を中心に使うなど、いつものPythonとは違う書き方を敢えてしないと高速化の恩恵を十分に得られないことがある。
      • ただし、元のPythonで動かなくなるようなレベルまで変えることはない。
  • Cython
    • ◎:型をしっかり指定し、確実に高速化しやすい。
    • ○:Cとの連携がしやすい。
    • ×:独自言語となり、元のPythonでは動かなくなる。Cコンパイラが必要など、環境構築が手間。
    • ※AtCoder 2025言語アップデートでは削除されている。
  • Codon
    • ○:あまりライブラリに頼っていないPythonコードならほぼそのままコンパイルでき、大きく高速化できる。
      • 静的配列やポインタなどでさらなる高速化もできるが、そうするとPython非互換の記法をする必要がある。
      • LLVM の制約上、使えない記法や、Pythonとは異なる挙動をする関数もある。
    • ×:未実装機能が散見される。まだ ver.0.19 の開発途上で、今後の見通しは不透明。
    • △:Windowsは未対応で、WSLなど経由で使う。1)

（参考）ChatGPTによるまとめ

項目 PyPy Numba Cython Codon
種別 JIT付きPython実装 JITコンパイラ（関数単位） Python拡張コンパイラ（Python→C） Python類似の静的コンパイル言語
実行形態 実行時コンパイル（JIT） 実行時コンパイル（LLVM JIT） 事前コンパイル（AOT） 事前コンパイル（AOT、LLVMベース）
速度向上の主な要因 トレースJITによる最適化 LLVMによる関数単位JIT最適化 静的型付け＋Cコード生成 静的型付け＋LLVM最適化
コード変更 ほぼ不要（純Pythonで可） 対象関数に`@jit`などデコレータ追加 型指定（`cdef` など）必要 Python風だが文法拡張あり
ビルド必要性 不要 不要 必要（Cコンパイラ要） 必要（Codonコンパイラ要）
ライブラリ互換性 一部非互換あり（C拡張に弱い） NumPyを中心に良好 CPython完全互換 Python構文互換ありだが別言語
主な用途 既存Pythonコードの高速化 科学計算・数値演算 ネイティブ拡張／組込み配布 高速科学計算・システム統合
メモリ管理 PyPy独自GC Python互換 CPython互換 LLVMネイティブ管理（非Python的）
並列実行 GILあり（制限あり） 一部対応（`parallel=True`） OpenMPなどCレベルで可能 スレッド／SIMD完全対応可
外部連携 弱い 限定的（NumPy中心） C/C++連携が容易 C/C++/CUDAとも連携可能
用途 最適な選択肢 理由
純Pythonコードをそのまま速くしたい PyPy コード変更不要、JIT最適化が自動
NumPy中心の科学計算を高速化 Numba デコレータのみでJIT
C/C++との連携や配布用モジュール Cython 拡張モジュールをビルド可能
静的型付きでC/C++/GPU統合した高速言語 Codon LLVMベース、C並の性能、Python風文法

インストール

とりあえず使う場合

公式に従ってコマンド実行するだけ。Windowsでは、WSLからおこなう。

最後に「パスに登録していいか？」と聞かれるのでYesと答えると、~/.profile に登録され、コンソール再起動で使えるようになる。

JetBrains IDE での実行

今のところ、デフォルトではCodonでの実行はサポートしていない。

Windows上で動くPyCharmなどのIDEで編集中のコードをWSL上のCodonで実行させるには、External Toolsを使う。

  • [File]→[Settings]→[Tools]→[External Tools]
  • “+” で新規ツールを登録
    • Name: 適当に Codon とか
    • Program: wsl.exe
    • Arguments: bash -l -c "codon run \"$(wslpath '$FilePath$')\""
      • デフォルト以外のディストリビューションを使う場合は、先頭に -d ディストリビューション名 を追加
    • Working directory: $ProjectFileDir$

これで、「編集中のファイルをWSL上のcodonで実行する」というコマンドが追加される。
これに適当なショートカットキーを登録する。

  • [File]→[Settings]→[Keymap]
  • さっきの “Name” で検索
  • 出てきたコマンドに、ショートカットキーを登録

AtCoder相当の環境構築

AtCoderで入るCodonには、AtCoderLibrary や scipy, sympy などの第三者ライブラリが追加されている。2)
これには、一旦Pythonで環境を構築し、それをCodon用にビルドする、という手順が必要になる。

全部自分でやるのは大変だが、有志が作成してくださっているインストール用スクリプトがある。
以下の言語アップデート関連のページから、Discordに行ける。

Codonのチャンネルにてインストール用スクリプト codon.toml（最も新しいもの）を取得する。
install = … から始まるコマンドを ~/codon_install.sh などに保存し、（一応、何をしているのか目を通し） WSLから bash codon_install.sh で実行すると、それなりに長いビルドの後、/usr/local/lib/libpython3.13.so が生成される。

このパスを環境変数 CODON_PYTHON に与えた上で codon run ○○.py すると、AtCoder相当の環境でローカル実行できる。

  • ※AtCoderの環境は Ubuntu24.04.1 らしいので、インストール環境および実行環境もそれに揃える。

JetBrains IDE での実行

さっきの External Tools での定義を、1箇所だけ変える。

  • Arguments:
    • bash -c "env CODON_PYTHON=/usr/local/lib/libpython3.13.so codon run \"$(wslpath '$FilePath$')\""

ライブラリのインポート

第三者ライブラリのインポートに関しては、純Pythonと同じようにはいかない。

例えば、AtCoderLibrary の string.z_algorithm を使いたいとき、以下のような方法となる。 

# 純Python
from atcoder.string import z_algorithm

z_algorithm('abracadabra')


# Codon
from python import atcoder.string as ACS

ACS.z_algorithm('abracadabra')

  • まず第三者ライブラリ全体が「python」という大きなパッケージに入っている
  • import できるのはモジュール（ファイル）までで、その中の個々のクラス・関数は直接インポートできない。
    • モジュールごとインポートして、ドットから使う。

標準ライブラリおよびNumPyのうち、Codon側で実装されなおしているものは通常通りの import が使えるが、それ以外はこの方法となる。

CodonでもACLなどが使えるのは素晴らしいことではあるのだが、 ただ、IDEの補完が効かなくなる（対応もしにくそう）ので、なかなか難儀だなあ。

あと、第三者ライブラリは使えはするが、Pythonのままで実行されるので、速度に関しては恩恵がない点に注意。

非対応・未対応の記法、注意点

見つけたやつを追加していくので、まだまだ未完全。

以下のサイトの方が充実してる（再掲）

対応されている標準ライブラリ

ここに、部分的にでも実装されている標準ライブラリ一覧がある。

が、例えば functools なんかは partial() のみが、何もしない関数として登録されているだけだったりするので、ちゃんと使いたい機能があるかどうかはAPIを確認した方がいい。

また、上記のドキュメントは最新版しか扱ってない？（過去バージョンのを見る方法が分からない）ので、 今後、開発が進むと、ドキュメントとAtCoderで動く版の内容に齟齬が生じうる。
多少見にくいが、GitHubでは過去の版の .md のドキュメントやソースコードそのものが見られるので、そっちを参照した方が確実。

個人的に使うことがあるが未対応の標準機能は以下。（問題を解きながら見つかった範囲で）

  • functools.cmp_to_key()
  • functools.reduce()
  • functools.lru_cache()

タプルの扱い

Codonでは、タプルを使う際の制約がPythonよりかなり厳しくなっていて、安易に使えない。

Pythonでの tuple は「immutableな、何個かの値をひとまとめにできる便利なデータ型」くらいの気持ちで使えるが、 LLVM における tuple はコンパイル前から「値の型と個数」が決まっているものであり、codon もそのように tuple を扱う。

そのため、「DPをする時、キーに可変長な列を持たせたいから tuple で Hashable な値にする」みたいな使い方はできない。 代替となるようなデータ構造も今のところ無いようなので、このような場合は実装から見直す必要がある。

また、意外と以下のような記法が使えない。以下のような場合は、List にすればコンパイルは通ってくれる。 

# ×
a, b = map(int, input().split())

# ○
a, b = list(map(int, input().split()))


# ×
n = int(input())
aaa = [tuple(map(int, input().split())) for _ in range(n)]
for a, b in aaa:
    pass

# ○
n = int(input())
aaa = [list(map(int, input().split())) for _ in range(n)]
for a, b in aaa:
    pass

また、@extend 構文を使うことで可能らしい。

数値関連の細かいこと

bit_length, bit_count は無い

Pythonとの互換性は失われるが、以下で代用できる。

  • int.bit_length() → 64 - abs(self).__ctlz__()
  • int.bit_count() → int.popcnt()

Numbaでも存在しないので、LLVMではすんなりと置き換えられない理由があるのかな。

floatのデフォルト桁数が短い

小数で出力するような問題の誤差判定に引っかかりうる。f-string などで、桁数をちゃんと指定する必要がある。 

pi = 3.1415926535897932384626

print(pi)
# => 3.14159

print(f'{pi:.10f}')
# => 3.1415926536

負の数の剰余が負

C++では初心者キラーとなる、「負数を正数で割ったあまりは負数」という仕様が Codon でも発生する。 

# 純Python
print(-13 % 5)
# => 2

# Codon
print(-13 % 5)
# => -3

Listのスター記法での関数渡しが不可(printなど)

aaa = [1, 2, 3, 4, 5]

# ×: error: argument after * must be a tuple, not 'List[int]'
print(*aaa)

# ○
print(" ".join(map(str, aaa)))

# ×: error: 'Array[int]' object has no attribute '__repr__'
bbb = tuple(aaa)
print(*bbb)

不定長の要素のスター記法によるprintはできない。
なんかエラーメッセージが「tupleならいいよ」といってるが、List を tuple にすることはできない。（前述の通り、要素数が固定されないため）

joinならOK。

Optional な返値は避ける

ちょっと限定されたケースでそこまで気にしなくていいかもだが、 「NoneまたはListを返す関数」の返値を「f-string で加工」しようとするとエラーが出た。

まぁ、空リストを返すなど、値の型は統一していた方が安全かも。 

# ○: 返すのがList固定ならOK
def get_range(n):
    return list(range(n))

aaa = get_range(5)
print(" ".join(f'{a}' for a in aaa))
# => 0 1 2 3 4

# ○: f-stringで加工せず、map(str, *) ならOK
def optional_range(n):
    if n == 0:
        return None
    return list(range(n))

bbb = optional_range(5)
print(" ".join(map(str, bbb)))
# => 0 1 2 3 4

# ×
# optional_range は同じ
ccc = optional_range(5)
print(" ".join(f'{c}' for c in ccc))
# => Assert failed: not a class: ?41429 [codon_test.py:12:24]
#    Expression:    t && t->getClass()
#    Source:        /github/workspace/codon/parser/visitors/translate/translate.cpp:677

組み込みのsortedlist

競プロでたまに出題されるデータ構造として、平衡二分探索木がある。
Pythonには標準ライブラリが存在しないため明確に不利だったが、tatyamさんのライブラリの公開や、sortedcontainersモジュールが入ったことでその差は縮まっていた。
（内部実装は平衡二分探索木ではなく平方分割的なアプローチだが、Pythonではこちらの方が速いらしい）

AtCoder環境のCodonでも sortedcontainers は入っているが、これはコンパイラによる高速化は期待できない。（まぁ、それでも良ければ使える）

それとは別に、Codon側で実装された sortedlist モジュールがある、のだが、、、

現時点では二分探索とかの機能は実装されておらず、add と clear しか無くさすがに使えない。

tatyamさんがCodon用ライブラリを作成・公開してくれたので、有難く使用させていただくのが、Codonでの SortedSet, SortedList のアプローチになるか。

生成関数の注入

関係ない人の方が多いと思うが、例えばモノイド注入可能なセグ木において、 単位元を「値」でなくて「生成関数」で渡す実装をしている場合に、ちょっと注意。 


# 値を渡す実装
class SegmentTree[T]:
    def __init__(n:int, id_:T, func:Callable[[T, T], T]):
        # 略...

sgt = SegmentTree(n, 0, add)


# 生成関数を渡す実装。
#   リストやオブジェクトを載せるなら、上記の実装では全て同じ参照になってしまうためこちらの方がよい。
class SegmentTree[T]:
    def __init__(n:int, id_factory:Callable[[], T], func:Callable[[T, T], T]):
        # 略...

sgt = SegmentTree(n, int, add)

Pythonならどちらでも動くが、Codonでは下は動かない。
引数の int を lambda: 0 にすれば動く。

要は、「type型のオブジェクト」と「関数」はしっかり区別されるということ。
int は、int() のように関数呼び出しっぽく使うことによって $0$ を生成できるため、 Pythonなら実質的に生成関数のように扱えるが、Codon ではしっかり区別されるため、型が違うとエラーが出る。

…あと、元も子もないが、生成関数の実装はあんまり速くないのでなるべく tuple にして値を渡す実装にした方がいい。

classmethod は無い

（インスタンスでなく）クラスに対するメソッドであることを示す @classmethod デコレータは無い。

使わなくてもなんとかなる場合が多いので、インスタンスが持つメソッドに書き換えるなどする。

ちなみに @staticmethod は使える。

で、結局使うか

個人的には「メインでは使わないが、TLEが取れないときの補助にはとても強力」という感じ。

慣れたPythonとの違いが多くあり、「型の制約が結構きつい」「うっかり細かな仕様違いの罠に陥る可能性が高い」、 また「Pythonとの差異がある部分はIDEが対応してないのでコードハイライト・補間が効かない」という面が大きく、とりあえずは困らない限り Python/PyPy で提出するかなぁ。 メインで使うには「別言語」という気がする。開発者も、Pythonの完全な互換は目指していないっぽい。

Python/PyPyではTLEが取れない（または事前に厳しそうな予感がする）という問題に遭遇した場合は、Numba か Codon を検討することになる。

とりあえず、Codonは「書き換え無しで動く可能性がある」という点がNumbaと比べて優れている。
ワンチャン、PythonコードをそのままCodonで動かしてみて、動いて通ればそれでよし。 また、動いたがTLEが取れない場合はさすがにアルゴリズムが間違っている可能性が高い、ということを時間コストなしで確信できるのも助かる。 （Numbaは、ちゃんと高速化の恩恵を受けようと思うとまず書き換えが必要になる。ある程度は流用できるが）

この“ワンチャン”のためだけでも、Codonは「とりあえず使えるようにはしておく」価値はあると思う。

動かなかったり、なんかCodonの仕様の違いを踏んで出力結果が変わったりした場合は、いよいよ高速化のための書き換えが必要になる。 この時の判断をどうするかが、まだ感覚的に不透明。

上記の“ワンチャン”の結果、コンパイルエラーが出たものの少し修正すれば通りそうな場合は、そのまま修正してCodonで提出するのが自然だ。 だが、一箇所修正すれば次のコンパイルエラーが発生する、ということが繰り返される可能性は十分にあり、どの程度の頻度で発生するかによる。

「事前に厳しそうと見積もって1から書く場合」はNumba を使うと思う。 なんだかんだ 純Python と同じコードで動くのでIDE補完が効くし、現段階ではライブラリ資産があるので。

以下のような状況では、Codon を使ってみるかもしれない。

  • 再帰で書いた方が楽
  • クラスを使用したい
  • 辞書を多用する（Numba は辞書は少し高速化の恩恵が薄い。ただしCodonがどうかは未検証）
  • Numba ではコンパイラエラーを起こしそうな、複雑な型を扱う（でもその場合は Codon も苦手そう。。。）

また今後Codonが浸透し3)、IDEが対応したり、パクれ参考にできる競プロ用ライブラリが充実してきた場合は、NumbaよりCodonにシフトしていくかもしれない。

何にしろ手段が増えるのはいいことだ。

1)
将来的に対応予定はある? windows support · Issue #69 · exaloop/codon “We plan to support Windows in the future.” ただ、Githubの“windows”ブランチは最終更新が2年前なので、少なくとも当分は対応されなさそう
2)
ただしコンパイルされないまま動くので、あまり高速化は期待できない、らしい
3)
浸透したらしたで、ゲノム研究界隈に鬱陶しがられそう。コドン
programming_algorithm/python_tips/codon.txt · 最終更新: by ikatakos
文書の先頭へ
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0