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

2019-06-27

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

そこで、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 の方も 使い方は概ね同じです。しかし標準関数の関係でパフォーマンスには差異があるかもしれません。

詳しい使い方については 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

Sorter

格納を試行する順番は最終的に出来上がるテストケースを左右する重要なものですし、 速度を重視するかケース数を重視するかは現場によって異なるでしょう。

そこで covertable では 順番を利用者が制御できるようにしています。

この順番を制御するのが sorter という仕組みで、プラグインとして make 関数に指定できます。

現状以下の4種類があります。

sorters.sequential
もっとも単純で早い sorter です. (デフォルト)
sorters.random
毎回異なる組み合わせを作るための sorter です.
sorters.hash
ペアと seed によって順番を決定する sorter です.
sorters.greedy

未格納ペアを最もたくさん消費する順にペアを返却する sorter です。 全てのペアを確認してから最大のものを判定しているため、オーダは他の sorter よりも悪いです。

出力されるテストケース数は大抵は少なくなりますが、他の sorter と比較して必ずしも少なくなるとは限りません。

備考

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

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

今回は greedy sorter に変えただけで 14通りから 12通りに減りました

>>> covertable.make(
...     {'browser': browser, 'os': os, 'machine': machine},
...     sorter=covertable.sorters.greedy,
... )
[
    {'browser': 'Chrome', 'os': 'Windows', 'machine': 'iPhone'},
    {'browser': 'Chrome', 'os': 'iOS', 'machine': 'Windows phone'},
    {'os': 'Linux', 'machine': 'Pixel', 'browser': 'Chrome'},
    {'browser': 'Edge', 'os': 'iOS', 'machine': 'iPhone'},
    {'os': 'Android', 'machine': 'iPhone', 'browser': 'FireFox'},
    {'browser': 'Edge', 'os': 'Linux', 'machine': 'Windows phone'},
    {'browser': 'Chrome', 'os': 'Android', 'machine': 'Pixel'},
    {'browser': 'FireFox', 'os': 'iOS', 'machine': 'Pixel'},
    {'os': 'Windows', 'machine': 'Windows phone', 'browser': 'FireFox'},
    {'os': 'Linux', 'machine': 'iPhone', 'browser': 'FireFox'},
    {'browser': 'Edge', 'os': 'Windows', 'machine': 'Pixel'},
    {'browser': 'Edge', 'os': 'Android', 'machine': 'Windows phone'}
]

備考

hash sorter と greedy sorter は sort_kwargs 引数にて seed 引数を受け取れます。 これによって順番が変えられるので、テストケース数を調整できたりします。 (といっても今回は 12 が最小っぽいので seed を指定する意味はなさそうです)

seed の型は数値でも文字列でも何でも構いません。

>>> rows = covertable.make(
...     {'browser': browser, 'os': os, 'machine': machine},
...     sorter=covertable.sorters.greedy,
...     sort_kwargs={'seed': 1},
... )
>>> len(rows)
13

因子、水準の組み合わせが変わらない限り毎回同じテストケースが出来上がるのが seed を使った sorter の特徴です

covertable で作られるテストケース数(最小)を総当たり数と比較してみます。

水準数^因子数 アルゴリズム(sorter) 最小ケース数 総当たり数 備考
3^4 Greedy 10 81
  • seed: 1 のとき
3^13 Greedy 18 1594323
  • seed: 12 のとき
4^15 3^17 2^20 Greedy 35 145398897491341278707712
  • seed: 5 のとき
  • 7分くらいかかる
4^1 3^30 2^35 Hash 26 28297461724253869811171328
  • seed: 85 のとき
2^100 Hash 12 1267650600228229401496703205376
  • seed: 13 のとき
  • greedy sorter ではめちゃくちゃ時間かかる(多分数時間レベル)ので hash sorter を使うと2秒くらい
10^20 Greedy 196 100000000000000000000
  • seed: 16 のとき
  • 10分くらいかかる

テストケース数だけを見れば 他の製品に引けを取らない感じになっていると思います。 とはいえ、他の製品がどういう条件で計測してるかわからないのでなんとも言えませんが。

./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

参考