先日、paiza オンラインハッカソン Lite の問題を解くプログラムを作成しました。作成したプログラムは、枝刈りによって解の候補を狭めながら処理を進めるもので、データの性質によって実行時間が大きく変わります。今回は、この様子を調べてみます。
問題の説明は paiza オンラインハッカソン Lite のウェブページを参照してください。
天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」｜paizaオンラインハッカソンLite
この問題に対して、私が作成したプログラムは以下にあります。
pohlite-data-generator/solve.cpp at master · y-uti/pohlite-data-generator · GitHub
プログラムは動的計画法に基づくもので、m を必要人数、n を下請け会社数とすると、計算量は O(m * n) になります。動的計画法の説明はウェブに数多くの情報がありますが、今回の問題はナップザック問題と呼ばれるものに近く、以下の記事などが図解も丁寧で分かりやすいと思います。
最強最速アルゴリズマー養成講座：病みつきになる「動的計画法」、その深淵に迫る (1/4) - ITmedia エンタープライズ
私のプログラムでの工夫は、解の候補を整列済みリストとして管理し、このリストを適宜枝刈りしながら計算を進めるようにしたことです。プログラムの動作の説明は 前回の記事 を参照してください。この工夫によって、ある入力データを処理するときの実際の計算時間は、反復処理の各回でのリスト長の合計に比例するようになります。リストの最大長は m なので*1、最悪の計算量は O(m * n) で変わりません。
今回は、下請け会社の (人員数、発注金額) として 4 種類の分布を考え、それぞれの場合について、n, m の変化に応じて計算時間がどのように変わっていくかを調べてみました。想定した分布は以下の 4 種類です*2。この分布からサンプリングして下請け会社のデータを作成しました。なお、発注金額については、一人あたり金額の分布を定めて、「人員数 * 一人あたり金額」として算出しています。
| 略号 | 人員数 | 一人あたり金額 |
|---|---|---|
| GN | 形状母数 2、尺度母数 500 のガンマ分布 | 平均 100、標準偏差 10 の正規分布 |
| PN | 平均 10 のポアソン分布 | 平均 100、標準偏差 10 の正規分布 |
| UN | 最小値 1、最大値 10,000 の一様分布 | 平均 100、標準偏差 10 の正規分布 |
| UU | 最小値 1、最大値 10,000 の一様分布 | 最小値 1、最大値 500 の一様分布 |
これらの分布から得られたデータがどのような様子になっているか、それぞれの散布図を示します。GN, PN, UN, UU の順で、いずれも n = 1,000 として得たものです。
まず、n (下請け会社数) を変えたときの反復処理中のリスト長の変化を調べます*3。ここでは、問題のサイズを大きくしたときの様子を知りたかったので、m (必要人員数) については、「n * 平均人員数 / 2」と n に応じて大きくしました。各分布での結果は以下のようになりました。GN, PN, UN, UU の順になります (グラフの順序は、これ以降の各グラフでも同じです)。横軸はプログラムのループカウンタ i に相当し、縦軸はそのときのリスト長です。
[2014-08-16 訂正: ガンマ分布のグラフが誤っていたので差し替えました*4]
計算時間はループカウンタ i が 0 から n まで動くときのリスト長の合計に比例します。各 n についてこれをプロットしたものが以下のグラフになります。近似曲線は原点を通る二次多項式で近似したものです。分布によって、縦軸の値が大きく異なっていることに注意してください。n = 1,000 のとき、GN や PN では数百万といったところですが、UN では 5,000 万を超える大きさになります。
[2014-08-16 訂正: ガンマ分布のグラフが誤っていたので差し替えました]
[2014-08-16 訂正: 近似曲線が誤っていたのでグラフから削除しました*5]
次に、n (下請け会社数) を 1,000 に固定して m (必要人員数) を変化させたときのリスト長の変化を調べます。プログラムの最悪計算量は O(m * n) なので m が大きくなるほど大きな時間がかかりますが、一方で、私の実装では「残り全ての会社に発注しても必要人員数に届かない」ものを枝刈りの対象にしているため、m が大きくなると枝刈りの効率は良くなってきます。したがって、どこか中間の m で計算時間が最大になりそうです。各分布について調べた結果が以下になります。
こちらについても、計算時間は i が 0 から n まで動くときのリスト長の合計に比例します。各 m についてプロットしたものが以下のグラフになります。人員一人あたりの金額を正規分布としたデータでは、m が「下請け会社の平均人員数 / 2」程度のところでリスト長が最大になっているようです。一方、人員一人あたりの金額を一様分布にしたデータでは、より大きな m でリスト長が最大になっています*6。
*1:0 から m - 1 までの全要素を保持している場合に最大となります。
*2:それぞれ、GitHub のサンプルデータに対応しています。
*3:前述したように、リスト長が計算時間に比例します。
*4:形状母数 2、尺度母数 500 のガンマ分布の平均は 1,000 ですが、これを 100 と誤って、一桁小さな m を設定していました。
*5:本来は y = ax^2 で近似したいのですが、誤って y = ax^2 + bx での近似を掲載していました。Excel で y = ax^2 での近似曲線を描く方法が分からないので、近似曲線を削除しておきます。
*6:いずれも、なぜそうなるのかという理由は、私には力不足で分かりません。
