Abstract
Yes.
（元ネタ：論文のアブストは、突き詰めるとここまで短くなる）
この話をする理由
研究でluigiを使っていて思ったのですが、明らかにjob数が数千単位になるとluigiの動きが悪くなります。線形なんてもんじゃない。
ということで、それを評価してみました。
用いるコード/普通に考えた場合の計算量
コードはこちら。
入力するnumberをnとして考えると、
simple_task1つにかかる時間は$O(1)$、それをn回実行します。また、main_taskのrunも$O(1)$ですので、全体としては$O(n)$になるはずです。
現実はそうもいかなくて
では、それを実際に計算してみた結果を以下に示します。あ、いつも通りtimeコマンドでの計測なので雑です。
| n | 1回目 | 2回目 | 3回目 |
|---|---|---|---|
| 1 | 0.156 sec. | 0.169 sec. | 0.171 sec. |
| 10 | 0.293 sec. | 0.303 sec. | 0.301 sec. |
| 100 | 1.403 sec. | 1.578 sec. | 1.313 sec. |
| 1000 | 16.718 sec. | 16.352 sec. | 16.868 sec. |
| 2000 | 41.440 sec. | 43.607 sec. | 42.829 sec. |
| 5000 | 196.317 sec. | 203.439 sec. | 201.425 sec. |
| 10000 | 672.231 sec. | 661.570 sec. | 671.289 sec. |
うーん、明らかに線形以上のオーダーで時間がかかってます。
見る限り、計算は瞬時に終わるのですが、jobを実行するまでが時間かかるんですよね・・・
これ、ちょっとexcelでフィッティングさせてみると、ものの見事に$O(n^2)$です。
（後から考えてみると、切片0でフィッティングさせるのはおかしいですよね、n=0でもmain_taskは走るので・・・）
個人的には、jobの選択/実行に$O({\rm log}n)$かかって、$O(n {\rm log} n)$くらいかなーなんて思ってたんですが、、、思ったより効率が悪いです。
というわけで、luigiを使うときはjob数が無駄に多くなりすぎないように注意しましょう、ということでした。
…あれ、パラメータチューニングの話と逆行するような…