意外と簡単!ペアワイズツールを作ったので大まかな仕組みを解説するよ

2020-06-06

テストケースを作ったことがある方はわかると思いますが、 単純に総当たりで作るととんでもない組み合わせになってしまうことがあります。

そこで、2因子間の組み合わせのみを網羅することでテストケース数を劇的に減らせます。 2因子間網羅のツールではペアワイズ(オールペア法)と直交表が有名ですが、 ここではペアワイズについて解説していきます。

なお、2因子間網羅のペアワイズは満たすべき配列の大きさが2、つまりペアとなりますが、 3因子間網羅の場合は配列の大きさが3となり、 ペアワイズ ではなく カバリングアレイ (被覆配列) と呼びます。 カバリングアレイはペアワイズのツールとしてサポートされていることがありますが、混同しないように注意しましょう。

備考

この記事では断りがない限りカバリングアレイではなくペアワイズについての解説となります。

プログラムを動かした CPU は 2.7 GHz Intel Core i5 です。

目次

用語

因子

テストしたいパラメータのことです。

例えば、「ブラウザ」「端末」の組み合わせでテストケースを作りたいという場合、 因子数は 2 となります。

水準

特定の因子内に含まれる値のことです。

例えば、「FireFox」「Chrome」「Edge」のブラウザで表示チェックをしたいという場合、 ブラウザの水準数は 3 となります。

因子 (因子数:3)

水準

ブラウザ(水準数:3)

  • FireFox

  • Chrome

  • Edge

OS(水準数:4)

  • iOS

  • Android

  • Windows

  • Linux

端末(水準数:3)

  • Windows phone

  • iPhone

  • Pixel

2因子間網羅とは 全因子 から 2つを選択し、それらを組み合わせたペアを満たすことです。

今回であれば以下の合計で 33 個が満たすべきペアの個数です。

  • ブラウザ(水準数:3) x OS(水準数:4) = 12

  • ブラウザ(水準数:3) x 端末(水準数:3) = 9

  • OS(水準数:4) x 端末(水準数:3) = 12

仕組み

端的にいうと「すべてのペアを順番に敷き詰める」だけです。

すべてのペアとは先程の2因子間における水準の組み合わせ(直積)の和です。

組み合わせ

ペア

ブラウザ x OS (3 x 4 = 12)

  • FireFox x iOS

  • Chrome x iOS

  • Edge x iOS

  • FireFox x Android

  • Chrome x Android

  • Edge x Android

  • FireFox x Windows

  • Chrome x Windows

  • Edge x Windows

  • FireFox x Linux

  • Chrome x Linux

  • Edge x Linux

ブラウザ x 端末 (3 x 3 = 9)

  • FireFox x Windows phone

  • Chrome x Windows phone

  • Edge x Windows phone

  • FireFox x iPhone

  • Chrome x iPhone

  • Edge x iPhone

  • FireFox x Pixel

  • Chrome x Pixel

  • Edge x Pixel

端末 x OS (3 x 4 = 12)

  • Windows phone x iOS

  • iPhone x iOS

  • Pixel x iOS

  • Windows phone x Android

  • iPhone x Android

  • Pixel x Android

  • Windows phone x Windows

  • iPhone x Windows

  • Pixel x Windows

  • Windows phone x Linux

  • iPhone x Linux

  • Pixel x Linux

これらの ペアを適切な列に格納し、列が全て埋まったらその行が1つのテストケースとなります。

すべての列が埋まった行はもう格納できないので新しい行を用意し、次はそれがペアの格納対象になります。

上記をすべてのペアが格納し終わるまで繰り返します。

大まかに言えばこれだけですが、細かいルールがあるので以下ではそれについて説明していきます。

格納条件

ペアはいつでも格納できるわけではありません。

格納対象列に異なる要素が格納されている場合、そのペアは行には格納できません。

例えば、行が下記のように格納されている場合、(端末 列が未格納)

ブラウザ

OS

端末

FireFox

iOS

端末を列に持つペアのうち、ブラウザが FireFox か OSが iOS のものが格納可能なペアとなります。

格納可否

ペア

ブラウザ

OS

端末

o

(FireFox, Windows phone)

Firefox == FireFox

Windows phone

o

(FireFox, iPhone)

Firefox == FireFox

iPhone

o

(Firefox, Pixel)

Firefox == FireFox

Pixel

x

(Chrome, Windows phone)

Firefox != Chrome

Windows phone

x

(Chrome, iPhone)

Firefox != Chrome

iPhone

x

(Chrome, Pixel)

Firefox != Chrome

Pixel

x

(Edge, Windows phone)

Firefox != Edge

Windows phone

x

(Edge, iPhone)

Firefox != Edge

iPhone

x

(Edge, Pixel)

Firefox != Edge

Pixel

o

(iOS, Windows phone)

iOS == iOS

Windows phone

o

(iOS, iPhone)

iOS == iOS

iPhone

o

(iOS, Pixel)

iOS == iOS

Pixel

x

(Android, WIndows phone)

iOS != Android

Windows phone

x

(Android, iPhone)

iOS != Android

iPhone

x

(Android, Pixel)

iOS != Android

Pixel

x

(Windows, Windows phone)

iOS != Windows

Windows phone

x

(Windows, iPhone)

iOS != Windows

iPhone

x

(Windows, Pixel)

iOS != Windows

Pixel

x

(Linux, Windows phone)

iOS != Linux

Windows phone

x

(Linux, iPhone)

iOS != Linux

iPhone

x

(Linux, Pixel)

iOS != Linux

Pixel

補完

未格納のペアが少なくなってくると、行が空いていても格納できるペアがないという事態に高確率で遭遇します。

こういう時は適当な値を空いている列に格納してあげるのです。

例えば未格納ペアがない状態で現在の行が次のような状態だとします。

ブラウザ

OS

端末

Chrome

Android

端末の列が空なので以下のうち適当のものを入れてあげればよいです。

  • Windows phone

  • iPhone

  • Pixel

制約条件

このように簡単な仕組みでできているため、ペアワイズは制約条件によるフィルタをかけやすいのです。

先程の組み合わせに違和感を感じていた方もいると思います。 例えば Pixel x iOS のような組み合わせはありえませんね。 (ほかにもありえない組み合わせはいっぱいありますが、スルーで)

ペアワイズではこのような組み合わせをもつテストケースの除外が容易に実装できます。 実際、ほとんどのペアワイズツールでは制約条件を指定できるはずです。(ちゃんとは調査してない)

covertable

covertable というライブラリを自作しました。

本当は TypeScript (JS) だけあればよかったんですが、 あんまり実装に慣れていなかったので まずPython で作ってから移植しました。

そのため Python と TypeScript で2実装あります。 このブログを見ている人は Python 使いの人が多いと思うので、 Python ライブラリの方のみ解説します。 とはいえ、npm の方も 使い方は概ね同じです。しかし標準関数の関係で Python ライブラリのほうが2倍ほど高速です。

TypeScript版の詳しい使い方については typescript/README を見てください。

ソースコードが公開されているペアワイズツールは PICT を始めいくつかありますが、 ソースコードが複雑で読む気がしなかったので完全なオリジナルです。

使い方

まずいちばん簡単な例

>>> import covertable

>>> browser = ['FireFox', 'Chrome', 'Edge']
>>> os = ['iOS', 'Android', 'Windows', 'Linux']
>>> machine = ['Windows phone', 'iPhone', 'Pixel']

# リスト型だと出力の内側もリスト型
>>> covertable.make([browser, os, machine])
[
  ['Edge', 'Windows', 'Pixel'],
  ['FireFox', 'Android', 'Windows phone'],
  ['Edge', 'Linux', 'Pixel'],
  ['Chrome', 'iOS', 'Pixel'],
  ['Edge', 'Android', 'iPhone'],
  ['Chrome', 'Android', 'Pixel'],
  ['Chrome', 'Linux', 'Windows phone'],
  ['Edge', 'Windows', 'Windows phone'],
  ['FireFox', 'Linux', 'iPhone'],
  ['Chrome', 'iOS', 'iPhone'],
  ['Chrome', 'Windows', 'iPhone'],
  ['FireFox', 'Windows', 'Pixel'],
  ['FireFox', 'iOS', 'Windows phone'],
  ['Edge', 'iOS', 'Windows phone']
]

# 辞書型だと出力の内側も辞書型
>>> covertable.make({'browser': browser, 'os': os, 'machine': machine})
[
  {'os': 'Windows', 'machine': 'Pixel', 'browser': 'Edge'},
  {'os': 'Android', 'machine': 'Windows phone', 'browser': 'FireFox'},
  {'os': 'Linux', 'machine': 'Pixel', 'browser': 'Edge'},
  {'browser': 'Chrome', 'os': 'iOS', 'machine': 'Pixel'},
  {'os': 'Android', 'machine': 'iPhone', 'browser': 'Edge'},
  {'browser': 'Chrome', 'os': 'Android', 'machine': 'Pixel'},
  {'browser': 'Chrome', 'os': 'Linux', 'machine': 'Windows phone'},
  {'browser': 'Edge', 'machine': 'Windows phone', 'os': 'Windows'},
  {'os': 'Linux', 'machine': 'iPhone', 'browser': 'FireFox'},
  {'os': 'iOS', 'machine': 'iPhone', 'browser': 'Chrome'},
  {'browser': 'Chrome', 'os': 'Windows', 'machine': 'iPhone'},
  {'browser': 'FireFox', 'os': 'Windows', 'machine': 'Pixel'},
  {'os': 'iOS', 'machine': 'Windows phone', 'browser': 'FireFox'},
  {'browser': 'Edge', 'os': 'iOS', 'machine': 'Windows phone'}
]

備考

covertable は ペアワイズもできますが、3因子間網羅も可能なカバリングアレイのツールでもあります。

make 関数の length キーワード引数が網羅する因子数を意味します。省略した場合は自動的に 2 となります。

この値(length)は必ず因子よりも小さくなるようにしてください。 例えば、3因子しかないのに3因子間網羅をしても 総当たりと変わりません。

フィルタ

フィルタは前述した 制約条件で、 covertable では以下の2種類があります

  • 前条件に当たる pre_filter

  • 後条件に当たる post_filter

呼び出されるタイミングは違いますが使い方は全く同じです。

いずれのフィルタも を辞書として第一引数に受け取り、各列の値に応じて 真偽値を返すことで登録可否を決定できます。 拒否する場合は False を返します。

>>> covertable.make(
...     {'browser': browser, 'os': os, 'machine': machine},
...     pre_filter=lambda row: not(row['os'] == 'Android' and row['machine'] != 'Pixel'),
...     post_filter=lambda row: not(row['os'] == 'iOS' and row['machine'] != 'iPhone'),
... )
[
  {'os': 'Windows', 'machine': 'Pixel', 'browser': 'FireFox'},
  {'os': 'Linux', 'machine': 'Pixel', 'browser': 'Edge'},
  {'browser': 'Edge', 'machine': 'iPhone', 'os': 'iOS'},
  {'browser': 'Edge', 'machine': 'Windows phone', 'os': 'Linux'},
  {'os': 'Android', 'machine': 'Pixel', 'browser': 'FireFox'},
  {'os': 'Linux', 'machine': 'iPhone', 'browser': 'FireFox'},
  {'browser': 'Chrome', 'os': 'Windows', 'machine': 'iPhone'},
  {'browser': 'Edge', 'os': 'Windows', 'machine': 'Windows phone'},
  {'browser': 'Chrome', 'os': 'Linux', 'machine': 'Windows phone'}
]
  • pre_filter は 値を格納する前にフィルタを行い、条件に合わなければ別のペアか妥当な値で補完します。

  • post_filter は 値を格納してテストケースが出来上がった後にフィルタを行い、条件に合わないケースを削除します。

    • filter() 関数で除外しているのとほぼ同じです。

その性質より、同じ条件のフィルタでも post_filter のほうが最終的に出来上がるテストケースは少なくなります。 必要に応じて使い分けてください。

警告

pre_filter ですべての組み合わせを弾くような(ありえない)フィルタを入力すると 例外が発生するようになっているので注意してください

>>> covertable.make(
...     {'browser': browser, 'os': os, 'machine': machine},
...     # browser が ['FireFox', 'Chrome', 'Edge'] にならないことはないので全部弾かれてしまうはず
...     pre_filter=lambda row: row['browser'] not in ['FireFox', 'Chrome', 'Edge']
... )
Traceback (most recent call last):
  File "<stdin>", line 3, in <module>
  File "/venv/lib/python3.7/site-packages/covertable/main.py", line 113, in make
    row.complement()
  File "/venv/lib/python3.7/site-packages/covertable/main.py", line 64, in complement
    raise InvalidCondition(InvalidCondition.message)
covertable.exceptions.InvalidCondition: It will never meet the condition

Criterion

格納基準です。 現状 simplegreedy の2つがあります。 1系 の covertable では sorter のなかに greedy が含まれていましたが、オプションを分割して criterion オプションが誕生しました。

名前の通り greedy貪欲 な格納基準で、処理中の行に対して未格納ペアを最も消費するようなペアを採用します。 simple は格納可能なペアであれば何でも採用するため greedy よりもかなり高速です。

大抵の場合 greedy のほうが出力されるケース数は少なくなりますが、必ずしも simple よりも少なくなるとは限りません。 因子に含まれる水準が少ないと greedy による効果は小さくなる傾向にあります。

備考

全ペアの順番を総当たりすれば確実に最小のテストケースが得られそうですが 未格納ペア長の階乗の計算量になってしまうの採用しませんでした。

先程のケースでも 33!8683317618811886495518194401280000000 回のループが発生してしまいます。

Tolerance

tolerancegreedy criterion にわたすオプションであり、ここでは許容範囲という意味で使っています。

結論から言うとこの数値を上げると出力する件数が大きくなる代わりに実行時間が小さくなります。

このオプションが登場した経緯をお話します。興味ない方は次のセクションまで飛ばしてください。

2.0.0 のリリースによって covertable はかなり高速化しました。というか 1系の greedy はおそすぎましたね...

アルゴリズム改善の結果も含まれますが、最大の要因は 未格納ペアの最大消化数の上限を設定した ことです。 今まで greedy はすべての未格納ペアを最も消化するペアを探して最後までループしていましたが、 未格納ペアの最大消化数には上限は 格納可能な要素数 * 現在の行に格納されている要素数 で求められます。 この数に達した瞬間に、そのペアを最大としてループを抜けるようにしたことで同じ結果を得つつ、処理を高速化できました。

しかし、まだ高速化の余地があります。 格納可能な要素数 * 現在の行に格納されている要素数 より基準を下げることで数倍から10倍程度の高速化を見込めます。

この基準を下げる数値が tolerance です。大きければ大きいほど基準が下がるため高速化されるというわけです。

詳しくは こちら を参照ください。

Sorter

格納を試行する順番は最終的に出来上がるケースを左右する重要なものです。

バージョン 2.0 の現在は hashrandom の2種類があります。

備考

sequential sorter は 2.0 で削除されました。

TypeScript版だと生成するペア数が膨大になってしまうのです。

`random` は試行する順番をランダムで決定します。毎回異なった結果を得たい場合はこちらを採用すると良いでしょう。

hash はペアと seed (オプション) によって 順番を決定します。 この sorter は オプションとして seeduse_cache (default: True)を受け取ります。

seed は ペアをハッシュ化するためのソルトのようなものです。 hash sorter は受け取った因子数、要素数が同じであれば、毎回同じ数のケースを作成できますが、それが絶対に最小のケースとは限りません。 seed を変えることでいろいろ試行できます。

use_cache はハッシュ化した結果をメモリ内に保存するかどうかを選択します。 hash sorter が利用するハッシュ関数は md5 なのでそこまで大きな負荷にはなりませんが、キャッシュを利用することで多少の高速化が見込めます。 Python版だと 約10%, TypeScript(JavaScript)版だと30%ほど高速化されます。

10^100 のテストケースだと 60MB ほどのメモリを消費します。メモリの使用量を抑えたい場合はこのオプションを OFF にしてください。

covertable で作られる結果(最小)を総当たり数と比較してみます。

水準数^因子数

条件

最小ケース数

総当たり数

時間

3^4

デフォルト

9

81

0.0006s

3^13

greedy, hash(seed:1084)

17

1594323

0.03s

4^15 3^17 2^29

greedy, hash(seed:19)

34

145398897491341278707712

7.47s

4^1 3^39 2^35

greedy, hash(seed:14)

26

28297461724253869811171328

14.70s

2^100

simple, hash(seed:6)

12

1267650600228229401496703205376

0.63s

10^20

greedy, hash(seed:1139)

195

100000000000000000000

14.48s

結果だけを見れば 他の製品に引けを取らない感じになっていると思います。

./products.gif

どう作ったか

ループのネストが深くなるとぼくのような鳥頭ではとてもプログラムを理解できないので、 できるだけシンプルな構造になるように工夫しました。

まず、全ての要素に一意な連番を振ります。 (内部では convert_factors_to_serials という関数で作成)

例えば以下のような要素があったら

factors = [
  ['FireFox', 'Chrome', 'Edge'],
  ['iOS', 'Android', 'Windows', 'Linux'],
  ['Windows phone', 'iPhone', 'Pixel'],
]

以下のような連番に差し替わり、内部的にはこの数値で管理されます。

serials = [
  [0, 1, 2],
  [3, 4, 5, 6],
  [7, 8, 9],
]

これにより、ペアを構成する値が必ず一意になるので、ペアのみを set で管理できるようになります。(未格納ペアという)

また、番号により要素がどの因子に属しているかも自動的に判定されるので混ざることはありません。 (内部では make_incompleted という関数で作成)

備考

例えば、 Firefox x iOS のペアは (0, 3) のタプルで表せます。

また、 0 ~ 2 が ブラウザ、 3 ~ 6 が OS、 7 ~ 10 が 端末 を意味するということを別のマッピング(parents)で管理しています。

その後は未格納ペアから 順に ペアを取り出し格納可否を判定、 可能であれば行に値を格納した後に未格納ペアから当該ペアを削除します。(これで格納済判定となります)

上記を未格納ペアがなくなるまで繰り返します。

以上がプログラムの概要です。

メインのソースコードは 150行ほどしかないので簡単に読めると思います。

スターまってるぜ〜

https://github.com/walkframe/covertable

参考