PICTで制約条件をORでなくINで書いたら組み合わせ生成が爆速になった話

この記事は VeriServe Advent Calendar 2022 の20日目の記事です。

PICTとは

皆さん、PICT（ピクト）というツールをご存知ですか？
PICTはPairwise Independent Combinatorial Toolの略で、ペアワイズ法という方法で、テストの入力条件の組み合わせを生成するツールです。ペアワイズ法はオールペア法とも呼びます。

テストの入力条件とは、ここでは、テスト対象のソフトウェアに入力するパラメータや値のことを指しています。テストケースを作るときに、色々な入力条件の組み合わせを考えることがあると思いますが、パラメータやそのパラメータがとる値が多いと組み合わせの数が爆発します。

PICTを使えば、全ての組み合わせを網羅するのではなく、2パラメータ間の値の組み合わせの網羅に抑えてくれて、組み合わせの件数を削減できます。

PICTは以下のMicrosoft社のリポジトリで公開されています。

この記事では、執筆時点の最新バージョンであるVersion 3.7.4のpict.exeをダウンロードして、Windows10のPC上で使いました。

ペアワイズ法の詳細は、私が所属するベリサーブが公開しているこちらの記事が参考になります。

PICTにおける制約条件の書き方

PICTで組み合わせを生成するときに、あるパラメータに特定の値を入力した場合は別のパラメータも特定の値しか入力できない、などの制約条件を指定したいことがあります。その場合、PICTの公式のドキュメントに記載されているように、以下のIF文の形式で制約条件を指定できます。Typeなどコロンの前の部分がパラメータの名前で、コロンの後のPrimaryなどがそのパラメータが取る値を表しています。

Type:           Primary, Logical, Single, Span, Stripe, Mirror, RAID-5
Size:           10, 100, 500, 1000, 5000, 10000, 40000
Format method:  quick, slow
File system:    FAT, FAT32, NTFS
Cluster size:   512, 1024, 2048, 4096, 8192, 16384, 32768, 65536
Compression:    on, off

IF [File system] = "FAT" THEN [Size] <= 4096;
IF [File system] = "FAT32" THEN [Size] <= 32000;

1つ目の制約条件をORを使って書くと、以下のようにも書くことができます。

IF [File system] = "FAT" THEN [Size] = 10 OR [Size] = 100 OR [Size] = 500 OR [Size] =  1000;

INを使って書くと以下のようになります。

IF [File system] = "FAT" THEN [Size] IN {10, 100, 500, 1000};

この例だと、値が数値なので不等号（<=）で書くのが一番簡単ですが、値が文字列の場合はORかINで書くことになります。

制約条件をORでなくINで書いたら組み合わせ生成が爆速になった話

前置きが長くなりましたが、ここからがこの記事の本題です。タイトルに書いた通り、制約条件をORでなくINで書いたら組み合わせ生成が爆速になった事例がありました。

具体例で見てみましょう。

以下のようなパラメータと値があるとします。実際のデータはお見せできないので、Parameter1やValue1-1などに置き換えてあります。

Parameter1: Value1-1,Value1-2,Value1-3,Value1-4,Value1-5,Value1-6,Value1-7,Value1-8,Value1-9,Value1-10,Value1-11,Value1-12,Value1-13,Value1-14,Value1-15,Value1-16,Value1-17,Value1-18,Value1-19,Value1-20
Parameter2: Value2-1,Value2-3,Value2-4,Value2-5,Value2-6
Parameter3: Value3-1,Value3-2,Value3-3,Value3-4,Value3-5,Value3-6,Value3-7,Value3-8,Value3-9,Value3-10,Value3-11,Value3-12,Value3-13,Value3-14,Value3-15,Value3-16
Parameter4: Value4-1,Value4-2,Value4-3,Value4-4,Value4-5,Value4-6,Value4-7,Value4-8,Value4-9,Value4-10,Value4-11
Parameter5: Value5-1,Value5-2
Parameter6: Value6-1,Value6-2,Value6-3,Value6-4
Parameter7: Value7-1,Value7-2,Value7-3,Value7-4,Value7-5,Value7-6,Value7-7,Value7-8,Value7-9,Value7-10,Value7-11,Value7-12

これに対して、以下のような制約条件があるとします。ORで書いた場合です。

IF [Parameter2] = "Value2-6" THEN [Parameter1] = "Value1-8" OR [Parameter1] = "Value1-9" OR [Parameter1] = "Value1-10" OR [Parameter1] = "Value1-11" OR [Parameter1] = "Value1-12" OR [Parameter1] = "Value1-13" OR [Parameter1] = "Value1-14" OR [Parameter1] = "Value1-15" OR [Parameter1] = "Value1-16" OR [Parameter1] = "Value1-17" OR [Parameter1] = "Value1-18" OR [Parameter1] = "Value1-19" OR [Parameter1] = "Value1-20";

同じ制約条件をINで書くと以下のようになります。

IF [Parameter2] = "Value2-6" THEN [Parameter1] IN {"Value1-8", "Value1-9", "Value1-10", "Value1-11", "Value1-12", "Value1-13", "Value1-14", "Value1-15", "Value1-16", "Value1-17", "Value1-18", "Value1-19", "Value1-20"};

制約条件をORで書いた場合とINで書いた場合のそれぞれで、組み合わせ生成にかかった時間は以下の通りです。Windows PowerShellではMeasure-Commandというコマンドレットで実行時間を測ることができます。

> Measure-Command {.\pict.exe .\OR.txt}

Days              : 0
Hours             : 0
Minutes           : 2
Seconds           : 35
Milliseconds      : 828
Ticks             : 1558283491
TotalDays         : 0.00180356885532407
TotalHours        : 0.0432856525277778
TotalMinutes      : 2.59713915166667
TotalSeconds      : 155.8283491
TotalMilliseconds : 155828.3491

> Measure-Command {.\pict.exe .\IN.txt}

Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 0
Milliseconds      : 58
Ticks             : 580146
TotalDays         : 6.71465277777778E-07
TotalHours        : 1.61151666666667E-05
TotalMinutes      : 0.00096691
TotalSeconds      : 0.0580146
TotalMilliseconds : 58.0146

TotalMillisecondsで比べると、制約条件をORで書いたときは155828.3491、INで書いたときは58.0146になっており、INで書いたときの方が組み合わせ生成が約2,686倍も速くなっています！

生成結果が一致していることも念のため確認しました。生成結果をCSVファイルに書き出して以下のdiffコマンドを実行したところ、何も出力されなかったので一致していると言えます。

> diff (get-content .\Result_OR.csv)  (get-content .\Result_IN.csv)

PICTの内部の仕組みまでは分かっていないので常にINのほうが速いのかはなんとも言えませんが、少なくとも今回のようなケースではORではなくINで書くと良いということが分かりました。
INで書いたほうが、制約条件自体も短くて書くのが楽です。

まとめ

パラメータ・値・制約条件の個数によって速度向上の効果は違う可能性はありますが、「PICTで制約条件をINで書ける場合は、INで書くと組み合わせの生成が速い」ということを覚えておくと良いと思います。

私が所属するベリサーブではGIHOZ（ギホーズ）というクラウドツールを公開しており、GIHOZでもPICTと同じようにペアワイズ法による組み合わせの生成を行うことができます。
アカウント登録すれば無料で使うことができますので、今回ご紹介した組み合わせの生成を試したい場合はGIHOZを使うのも良いでしょう。
GIHOZだと、制約条件をORで書いた場合は組み合わせ生成に時間がかかりすぎてタイムアウトのエラーになるかもしれないため、INを使って書いてみてください。