acl-cpp-python
日本語 | English
acl-cpp-python は、C++ で実装された AtCoder Library (ACL) を Python に bind したパッケージです。
内部的には C++ で実装されているので、高速な畳み込みやフロー、文字列アルゴリズムなどを Python から利用できます。
インストール
python3 -m pip install acl-cpp-python
error: externally-managed-environment が出る場合:
動かしたいフォルダの中に 仮想環境 を作成して、再実行しましょう。
仮想環境なんて面倒！どこでも使えるようにしたい！という場合は
python3 -m pip install acl-cpp-python --break-system-packages
を実行してしまいましょう。
更新
python3 -m pip install --upgrade acl-cpp-python
使用例
from acl_cpp.convolution import convolution998244353
a = [1, 1]
b = convolution998244353(a, a)
print(b) # [1, 2, 1]
from acl_cpp.string import z_algorithm
a = z_algorithm("abacaba")
print(a) # [7, 0, 1, 0, 3, 0, 1]
注意点
C++ ↔︎ Python 間のデータの変換にはオーバーヘッドがあるため、関数の 1 回の実行時間が長いほど高速化が期待できます。
segtree,lazysegtree,modintは高速化が期待できないため、現在実装されていません。オーバーフローに注意してください。多くの整数は 64 bit 符号付き整数として実装されているため、この範囲を超える計算を行うとオーバーフローが発生し、結果が間違ったものになります。
ドキュメントでは、
long long(64 bit 符号付き整数) をllと表記します。