2023/12/29追記。最新版を出しました。
https://github.com/toast-uz/ahc_tools/
今作では、前作に、以下の特徴を追加しています。
- 初期環境整備を
setup.pyとして別プログラム化し、本体をシンプルに - 初期環境整備で
.gitignoreやrust-toolchainも作成 - インタラクティブ型、非インタラクティブ型を自動切り替え
- コンパイル後にダミー実行するようにして、コンパイル直後の実行が遅いことを防止
- Pythonの並列処理ライブラリ
rayを利用することで並列処理を安定化 - エラーやTLEでテスト対象プログラムが落ちた時、プロセスが暴走することがあったバグを解消
- テストケースの特徴量によるスコア差がわかりやすくなるように、特徴量をスコアとあわせて表示
- 相対スコアゲーに効果ある $Σ\log(1+score)$ 評価を追加
- Optunaに対応、ストレージ、enqueue_trial、枝刈りにも対応
- https://img.atcoder.jp/ahc_standings/ のローカル実行に対応
以下、旧記事
AtCoder AHC向けの、並列処理可能な自動テストツールをPythonで作成しましたので、共有します。筆者の環境で逐次テストと比較して、約10倍の速度向上を達成しました。
全ソースコードはこちら
※最終更新 2022/9/27
多数のテストケースについて並列テストをすると、OSのファイル同時オープン上限を超過する場合があります。Macの場合の解決策はこちらなどを参照ください。
初期設定の並列多重最大数はCPU数×2としていますが、各テストの負荷を適正化したい場合は、CPU数×1にすると良いでしょう。
1. AtCoder AHCとは
AtCoder Heuristic Contest (略称AHC)は、いわゆるマラソンコンテストです。マラソンコンテストは、正解というものを実時間で求める手段が基本無く、正解になるべく近づけるように自分の提出プログラムの得点をいかに上げていくか、が競われます。
2. ローカルテストツール
2.1. AHCの解答提出までのフロー
AHCの解答提出までのフローを図示します。水色部分が本ツールによる自動化範囲です。
並列処理をせずに逐次処理でテスト実行するコマンドラインオプションも、用意しています。
2.2. ローカルテストとは
フローに記述されているように、提出前に自分の開発環境において、テストを実行します。これを「ローカルテスト」と呼びます。
ローカルテストを実施した方が良い理由として、以下があります。
- AHCのシステムに解答を提出すると、再提出まで一定時間提出ができない。
- システム側のテストは本ツールのような並列処理はされておらず時間がかかる。
- 提出プログラムに様々なエラーログ出力を組み込むことで、ローカルテスト実行により改善のヒントを得る。
2.3. ローカルテストのためのツールの必要性
このローカルテストは、何もツールを準備していないと、フローにある手順を愚直に手作業でコマンド投入して繰り返す必要があり、現実的ではありません。
また、ローカルテストは、2〜3秒の実行時間の提出プログラムを、精度を上げるために50〜100回のテストデータで動作させます。そのため、1セットのテスト実行完了まで、手作業を無視しても、2〜5分を要します。これは、比較的短時間な4時間コンテストでは、結構な重荷になります。さらに、上位者は、特に提出近くなると、もっと多いテストデータを使って、精度を上げてきます。
これらを改善するために、適切なツールが必要になります。
2.4. 本ツールについて
本ツールのカバー範囲は、解答提出までのフロー図の水色の部分です。
- ローカルテスト作業全体を自動化
- テストの並列処理化
- ローカルテストでスコア算出に使うビジュアライザのビルド
- なぜかいつも運営のローカルテストツール内に存在しない
out/ディレクトリの作成
本ツールにより、筆者の環境（MacBook Pro 2018, 2.3GHz クアッドコア Intel Core i5、メモリー8GB）で、約10倍の速度でテスト完了させることが可能です。
提出プログラムはRustであることを前提としていますが、ソースのコメントを変えることで、PyPy3にも対応可能です（動作確認済み）。また、C++にも簡単に移植できるでしょう。
前提となる環境は、MacOS Monterey 12.4ですが、力のある人であれば、Windowsへの移植は可能かもしれません。
2.5. 本ツールの動作例
本ツールの動作例を示します。(snip)は記載を省略している箇所です。気持ちよく、自動実行かつ並列処理が行われて、普通に順番にテストした場合と比較して、9.6倍の速度でテストを完了させています。
3. 本ツールのプログラムのポイント解説
3.1. 全体図
以下が全体図です。グレーの濃いところを解説します。
3.2. テスト1回実行 single_test()
single_test()は、同じサブルーチンでありながら、逐次テストの場合は普通の関数呼び出しで呼ばれ、並列テストの場合はmultiprocessing関数群から呼ばれるように、設計しています。
single_test()の中では、subprocess.run()で、コマンドライン子プロセスを起動してテスト実行を行います。テスト結果はファイルに出力するため、テスト実行時間のみを返します。並列テストの場合は関数呼び出しでは無いため、返り値は取得できません。よって、multiprocessing.SimpleQueueに実行時間をput()します。
3.3. コマンドライン解析 parser()
argparseモジュールを使って、コマンドライン解析をします。argparseの使い方については、ソースを参照するか、argparseに関連する記事を参照してください。
どのようなコマンドラインオプションをサポートしているかは、argparseが提供するヘルプを見るとわかります。
(.venv) toast-uz@MacBook-Pro ahc012 % ./eval.py -h
usage: eval.py [-h] [-s [SPECIFIED ...]] [-f] [--seq]
Parallel processing tester driver for AtCoder Heuristic Contest
optional arguments:
-h, --help show this help message and exit
-s [SPECIFIED ...], --specified [SPECIFIED ...]
Test specified number as [from [to]] .
-f, --force Force (re)build tester.
--seq Force sequential tests.
3.4. 初期環境確認と設定 init_environment()
AHCのローカルテスト環境が整備されているかを、タイムスタンプ含めて確認し、以下の準備を、必要に応じてユーザーに確認しつつ行います。
- テスト出力データのディレクトリ
out/の新規作成 - スコア算出ツールとして利用するビジュアライザのビルド
- 提出プログラムのビルド
3.5. 並列テスト parallel_test_all()
3.5.1. 並列処理フロー制御
並列処理の多重度の上限をコントロールします。現在実行中の処理を数え、予め設定した上限に達していない場合のみ、追加のプロセスをスタートさせます。
3.5.2. 実行結果収集
multiprocessing.SimpleQueueに蓄積された実行時間を収集します。
3.5.3. 実行時間補正率取得
並列実行は、逐次実行と比較して、1回のテストにおいて、わずかにオーバーヘッドが生じます。そのため、最大実行時間だったテスト1回のみ、逐次実行を行い、両者の時間比を「補正率」として得ます。
補正率をもとに、スコア表示の時に、実行時間の補正板を表示させます。これは、おおよその値ですので、TLEに注意ください。
3.6. スコア算出 compute_score()
運営のローカルツールとして提供される中に、ビジュアライザがあります。このビジュアライザは、その中の通り結果をビジュアルで表示させるのですが、実行の際にコマンドライン上にスコアを出力してくれます。
これを使って、スコア算出をすることができます。subprocess.run()で、コマンドライン子プロセスを起動してビジュアライザ実行を行います。