Big Dataと計算量
『サンプルデータではデータ加工処理がうまくいっていたのに、本番データでは処理が遅すぎて使い物にならない！』なんてことありませんか？
加工処理の実行速度は単純なデータ量で比例するわけではありません。
予想する方法として『計算量』という考え方が重要になります。
そして、Big Dataと計算量はアルゴリズムとデータ構造に密接に関連しています。今回は記事ではその関係性をイメージしやすいように登場人物AさんとBさんのやりとりに当てはめてまとめてみました。
ある日の夕方
Aさん：あれ？今朝、テスト実行した処理が終わらない。
どうしよう。。。
Bさん：どうしたの？
Aさん：サンプルデータで確認の終わったデータ加工処理を本番データで
試したんです。まだ終わらなくって。。。
Bさん：本番データって？1億件のあれ？
Aさん：はい。20万件くらいのサンプルデータは、5分くらいで
終わってました。1億件でも、朝に実行すれば帰るころには余裕で
終わっていると思っていたんです。
Bさん：それは、終わらないよ。
Aさん：えっ？
Bさん：明日、時間があるから説明してあげる。
今日は、その処理を止めて帰っても大丈夫だよ。
翌日
Aさん：昨日の処理、どうして終わらなかったのですか？データ量が
50倍なので実行時間も50倍位だと思っていました。
Bさん：そうなることもあるのだけれど、そうならないことが多いんだ。
Aさん：。。。
Bさん：それを予想する方法はあって、”計算量” っていうんだ。
Aさん：計算量？
Bさん：それじゃ、説明するね。
計算量とは
アルゴリズムの性能を評価するための指標です。
・時間計算量
・処理時間がどれだけ掛かるのか
・空間計算量
・どれだけの記憶容量を必要とするか
一般には、時間計算量を計算量と呼ぶことが多いです。
与えられたデータ量をあるアルゴリズムで処理したときにどのくらい時間がかかるか推定しようということです。
計算量は、多項式の数式で表すことが可能です。
例：𝑎𝑥^2+𝑥𝑙𝑜𝑔(𝑥)+𝑏𝑥+𝑐
数式の最も次数の高い項の係数を除いた部分をオーダーと呼びOと書きます。
上の例では、𝑥^2をO(𝑛^2)と書きます。
アルゴリズムとデータ構造
Aさん：計算量って、初めて聞きました。
Bさん：計算量は、アルゴリズムとデータの構造と密接に
関係しているんだ。関係を簡単に下の図にしてみたよ。
Aさん：アルゴリズムとデータ構造もあまり聞かないですよね。
Bさん：昨日テストしていたデータ加工の処理だと、データ加工ツールや
データベース、プログラミング言語のライブラリに隠されている
から気がつかないことが多いんだ。
Aさん：知らなかった。。。
Bさん：アルゴリズムとデータ構造は、他の技術のベースになって
いるんだ。いろいろな本が出ているから1冊買って読んでみると
いい よ。
計算量のいろいろ
Bさん：さっき、計算量は、処理の計算量を表す多項式の最大次数を指すと
言ったよね。主なものを表にしたのがこれ。
O記法（オーダー記法）で書きます。
Aさん：なんかよくわからない。。。
Bさん：確かにこれだけじゃわからないよね。グラフを書いてみようか。
計算量の増え方
Aさん：このグラフはどう見たらいいんですか。
Bさん：横軸がデータの件数、縦軸が計算量を表しているんだ。
注目してもらいたいのは値そのものではなくってグラフの傾き
なんだ。O(𝑛^2)やO(2^𝑛)は、少し件数が増えただけで計算量が
一気に増えるよね。
Aさん：でも、O(n)のグラフ以外は曲線ですよね。
Bさん：もう少しわかりやすいグラフにしてみよう。横軸の０から100を
拡大したグラフにしてみるね。
Aさん：確かに曲線ですね。
Bさん：注目してもらいたいのは、赤丸で囲んだ部分なんだ。データ量が
少なければ、どんなアルゴリズムでもグラフの傾きが小さいよね。
傾きが小さいということは、この範囲ならデータが増えても時間が
かからないことを示しているんだ。
Aさん：昨日のテストのデータだと、ザックリ3桁もデータ量を増やして
しまいました。
昨日の処理に当てはめると
Bさん：昨日の処理の概略はこんな感じだよね。データ量 を増やしたのは、
上側のデータ入力の1億件の所だね。
Aさん：はい。
Bさん：計算量がO(n)を緑、O(n log n)に色分けしてみた。全体の計算量は、
オーダーの次数が最も高いものになるから、この処理の計算量の
オーダーは、O(n log n)になるんだ。
Aさん：さっきのグラフに当てはめると。。。全然終わらなかったですね。
昨日、終わらないよと言われたとき、なんでわかるんだろうって
思ってました。
Bさん：データ量の多い処理（Big Dataの処理）の時は、計算量の知識が役に立つこともあるんだ。
Big Data では・・・
ここで、AさんとBさんのやりとりから少し整理したいと思います。
Big Data ではETLやELT、分析の処理で計算量を考える必要があります。
Big Dataの世界では、O(𝑛^2)以上の時間計算量のアルゴリズムは使い物にならないと思われます。O(n log n)の処理でも相当きついです。
例えば、100億とか1000億件のデータを並べ替えることを考えてみてください。
並列処理で何とかなるか？
なりません。並列処理は、1/定数なので、オーダー計算の簡略の方法は、 無視されます。
ただし、計算量のグラフの傾きがO(n)の傾きに近い範囲では有効なことも あります。
ETLツールやSQLの内部処理、分析ソフトの内部処理の計算量に注意を払う必要があります。
分析ソフトにマニュアルでは、計算量理論の用語で説明されていることがあります。例えば、「このアルゴリズムは、NP完全です。」と書いてあったりします。（要するに、サンプルデータくらいなら動くけど、実用には耐えられないよという意味）
では最後にもう少しだけ、ＡさんとＢさんのやりとりを見てみましょう。
最近の話題
Bさん：量子コンピュータとか聞いたことある？
Aさん：ネットのニュースで見たような。。。
Bさん：赤枠の計算量オーダーの処理が劇的に早くなるといわれている技術なんだ。
Aさん：技術はどんどん進歩してるんですね。遅れないようにしないと。
Bさん：そうだね。
まとめ
計算量はアルゴリズムとデータ構造に密接に関連しています。
アルゴリズムとデータ構造はIT技術の基本ですが最近は表に出てくることが少なくなりました。
計算量とアルゴリズムの関連について知っておくとBig Dataだけでなく様々な処理を考えるときに役立ちます。
この分野は書籍が数多く出ているので、自分に合ったものを手元に置いておくといいでしょう。
量子コンピュータのような全く新しい技術が出てきています。
このような技術の考え方にも興味を持ってもらえるといいと思います。