paiza オンラインハッカソン Lite を大きなデータで試す

以前にも参加した paiza オンラインハッカソンに新しい問題が出題されていたので、さっそくチャレンジしてみました。ウェブサイトはこちらです。
天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」｜paizaオンラインハッカソンLite

ところが、今回は問題のサイズが小さいのか、あっさりと全ケースで 0.01 秒を達成してしまいました。ウェブサイトに掲載されている途中経過を見ても、早々に各言語で 0.01 秒が達成されているようです。そこで、チューニングなどを試せるように、もう少し大きな規模のデータを作成しました。サンプルデータとデータ生成スクリプトを GitHub に置いてあります。
y-uti/pohlite-data-generator · GitHub

スクリプトは PHP で書かれていて、実行には PECL::stats が必要です。また、利用している関数は PECL::stats のバグのためにそのままでは動作しません。以前の記事 にある手順でバグを修正する必要があります。

実行時間はデータのばらつきに影響を受けそうだと考え、各会社の人員数と単価はいくつかの確率分布から選択できるようにしてあります。なお、paiza オンラインハッカソンの評価用データの作成方法は不明なので、このデータでの実行時間がオンラインハッカソンでの実行時間に比例するとは限りません。

さて、GitHub のリポジトリの sample_data 以下に生成したデータを用いて、作成したプログラムの実行時間を計測してみます。なお、私が書いたプログラムは、簡単な枝刈りを行いながら幅優先で探索するものです。異なる解き方のプログラムでは、以下に掲載するグラフとは違う傾向を示すかもしれません。

最初のグラフは、人員数が平均 10 のポアソン分布に従い、単価が平均 100, 標準偏差 10 の正規分布に従うとしたときの結果です。会社数を横軸にとり、それぞれでの実行時間を縦軸に取っています。会社数に応じて、必要人数も変化させていることに注意してください。この設定では、データサイズが大きくなっても数秒で実行が完了しています。

次のグラフは、人員数の分布を 1 から 10,000 の一様分布に変えたものです。単価の分布は先ほどの設定と同じです。この設定では、計算に大きな時間がかかっています。

最後のグラフは、単価の分布を 1 から 500 の一様分布に変えたものです。人員数の分布は一様分布のままです。先ほどの、単価を正規分布にしていたものよりは短い時間で実行が完了するようです。

いずれの場合でも、会社数の変化に対する実行時間の増加は、同じような傾向になるようです。