競技プログラミングにおける様々なテスト

通常の競技プログラミングの中で現われるもの

サンプルテスト (sample testing)

競プロにおいて、サンプルテストとは、解答コードの振舞いが問題文中に与えられた入出力例に一致するかを確認するテストのことです。サンプルテストは主に提出前の確認として行われます。

サンプルテストは提出前に必ず実行しておくべきでしょう。これを確実にするためのツールは多数存在しています¹。

手で作ったテストケースによるテスト

「サンプルが合ったので提出してみたら WA だった」「サンプルが弱そうで不安である」などの場合には、自分でテストケースを作って試すことになります。このようなテストに個別の名前はありませんが、とても広く行なわれているテストです。状況によっては、テストと呼ぶよりデバッグ手法と呼ぶ方が適切かもしれません。

システムテスト (system tests)

競プロにおいて、システムテストとは、ジャッジサーバ上の非公開のテストケースを使っての AC かどうかの判定のためのテストのことです。

コードを提出するとその場でシステムテストが行われその結果がすぐにユーザに通知される形式のコンテストを、full-feedback 形式のコンテストと呼びます。たとえば AtCoder や yukicoder は full-feedback 形式です。Codeforces や Topcoder は full-feedback 形式ではありません。次に説明する「プリテスト」と比較されることが多いため、「システムテスト」という語が用いられるのはたいてい full-feedback 形式でないコンテストの場合です。

プリテスト (pretests)

競プロにおいて、プリテストとは、システムテストに先立って行われるコード提出時に行われる簡易のシステムテストのことです。 full-feedback 形式でないコンテストに特有です。

発展的なデバッグの手段として現われるもの

ランダムテスト (random testing)

一般には、ランダムテストとは、ランダムに生成される入力を用いたテストのことです。その出力が仕様と合致していれば成功とされます。これを行うツールとしては QuickCheck が有名です²。

競プロにおいては、たいてい、バグの存在性のみが知られている³プログラムに対し具体的な撃墜ケースを構成するために用いられます⁴。テストと呼ぶよりデバッグ手法と呼ぶ方が適切かもしれません。ストレステストと呼ばれる場合も多くあります。実際に行う際には、まったくのランダムではコーナーケースの検出が難しいことに注意しましょう。たとえば、入力の制約が $0 \le n \le 10^{18}$ でかつ $n = 0$ や $n = 2^k$ がコーナーケースだった場合を考えてみましょう。このランダムテストの実行を補助するツールもいくつか開発されています (例: oj コマンド, そのドキュメント)。

セキュリティの文脈では、ファジング (fuzzing, fuzz testing) という名前で (特に競プロにおける) ランダムテストと類似の行為が行われています。

ストレステスト (stress testing)

一般には、ストレステストとは、耐久性を調べるために通常以上の負荷をかけて正常に動作するか試すテストのことです。

競プロでは、先述した (競プロにおける) ランダムテストの同義語として用いられています⁵⁶。なお、この呼び方は不適切だとして批判されることがあります。

全数テスト (exhaustive testing)

全数テストとは、すべての入力の組合せについて行うテストです。通常のソフトウェア開発の場面ではまったく不可能ですが、競プロの場合はまれに可能です。なお、全数テストが可能な場合はたいてい埋め込みも可能です。

ライブラリのテストにおいて現われるもの

(競プロと通常のソフトウェア開発は異なることに注意してください)

end-to-end テスト (end-to-end testing)

一般に、end-to-end テストとは、そのプログラムが使われる状況をシミュレートしてみて期待通りに動作するかを確認するテストのことです。利点は「実際の使われ方とかなり一致している」ことであり、欠点は「時間がかかる」「不安定である」「失敗しても原因が分かりにくい」ことです⁷。

競プロにおいて、end-to-end テストは、「verify する」と呼ばれる形で広く行われています。ライブラリを verify するとは、そのライブラリを用いて実際の競プロの問題に対する解法を書き、それを提出してみて AC を確認することです。ライブラリをすこしいじるたびに毎回に手で提出をしていると大変なので、これを自動化するツールも開発されています (oj-verify コマンド)。また、そのような verify に使うことを意図したオンラインジャッジも運営されています (Library Checker)。

end-to-end テストの欠点として「時間がかかる」「不安定である」「失敗しても原因が分かりにくい」を挙げましたが、これらは競プロの場合にはあまりあてはまりません。これらの欠点は、たいてい「GUI を立ち上げ操作する」「ネットワークアクセスをする」「物理デバイスを動かす⁸」のような不安定な処理に起因しているためです。一方で競プロのコードの実行は、どんなに複雑なコードであってもたいてい純粋に数学的な計算しか行わないため、とても安定しています。あるコードを修正したときのその影響範囲も明確である⁹のでテスト結果のキャッシュがしやすく、このために高速です。ライブラリの個々の利用例の複雑さもさほど大きくならないので、失敗したときの原因の切り分けもたいてい容易です。これらのため、競プロのライブラリにおいてはとりあえず end-to-end テストを書いておけば済むことがたいていです。

単体テスト (unit testing)

一般に、単体テストとは、プログラムを構成する個々の単位 (たいていは関数やメソッド) がそれぞれ正しく動作することを確認するテストのことです。利点は「高速である」「安定している」「失敗の原因が分かりやすい」ことであり、欠点は「実際の使われ方と一致している保証がない」ことです⁷。

競プロのライブラリで単体テストが行われることは稀ですが、例はいくつかあります。たとえば AC Library には Google Test を用いた単体テストが書かれています (test/unittest/math_test.cpp - atcoder/ac-library)。

結合テスト (integration testing)

一般に、結合テストとは、プログラムを構成する複数の単位を組合せた場合に正しく動作することを確認するテストのことです。たいてい単体テストと比較されて用いられる語ですが、その境界は曖昧です。結合テストは end-to-end テストと単体テストの中間に位置するものだとして end-to-end テストと区別されることもありますが、あまり区別されないこともあります。

競プロのライブラリのために (end-to-end テストとは呼べないような種類の) 結合テストが書かれることはほぼないように思います。

注釈

たくさんあるので各自で調べてください。 ↩
QuickCheck などの場合は特に property-based testing とも呼ばれます。 ↩
つまり、提出してみたら WA だった ↩
なお、「入力ケースが人間のバイアスに影響されずかつ大量に得られること」が重要なのであって、「ランダムであること」はそのための手段のひとつでしかありません。もしたとえば静的コード解析 (static code analysis) やシンボリック実行 (symbolic execution) などのような技術でテストケースの自動生成ができるなら、これらを使うべきでしょう。 ↩
歴史的な経緯によるものです。最初に誰かがそう呼んでいたのが広まりました。最初のひとりが誰だったのか (私だったのかどうか) は今となっては確認できませんが、広まる過程 (特に日本語圏) においては私がかなりの影響を与えたように思います。 ↩
おそらくバグのないだろうコードについて安全のために (競プロにおける) ランダムテストを行う場合には、こちらの名前で呼びたくなるかもしれません。Codeforces ですべての問題についてプリテストを通して暇になった後などにやる場合です。また、マラソンマッチでは、クラウド環境を借りてクラスタを組んで大規模にこの手の安全のためのテストをすることがあります。 ↩
出展: Unit Tests vs. End-to-End Tests - Google Testing Blog: Just Say No to More End-to-End Tests ↩ ↩²
たとえば、スマホでの写真を取る機能のテストのために、実際にカメラで写真を撮ってみるなど ↩
複雑なシステムであると、ある部分の変更が他のどんな部分に影響するかが自明ではなく、すこし修正するたびにまったくすべてテストし直しになることがあります。 ↩

目次