みなさんこんにちは。ずっと続くコロナ禍の第五波も一段落して、街にはちょっとだけ活気が戻っているようですね。SNSを見ても、飲み会や旅行に行っている人の楽しそうな写真がながれてくるようになりました。私は仕事が多忙で相変わらずの引きこもり生活を送っていますけどねっ！！
TEXT＿痴山紘史 / Hiroshi Chiyama（日本CGサービス）
EDIT＿尾形美幸 / Miyuki Ogata（CGWORLD）
計算量を意識する
ここ最近Twitterのエンジニア界隈で話題になっていた連載、「100日後に退職する47歳」が無事に最終回を迎えました。この連載の内容はエンジニアあるあるで毎日胃をキリキリ痛めながら読んでいた人は多いでしょう。この90日目で唐突に計算量の話が投下され、計算量に対していろいろと言いたいエンジニアがホイホイと釣られておおにぎわい、遂にはクイックソートがトレンド入りを果たすなんていう状況になりました。
.........まあ、私もそんなこんなで見事に釣り上げられて今回の記事のネタにしているわけなのですが。
ここで出てくる47歳氏のように、普段の業務で計算量を意識しないで済むという仕事はたくさんあるので、突然話題をふられて答えられなくてもしかたないなとは思います。私もクイックソートの内容とか計算量をいきなり聞かれても答えられないですしね。最近のライブラリはとても優秀で、基本的に自分で何かつくったら負け、いかにいい感じに既存のものにブン投げるかがキモと言っても過言ではないです。探してもなかったり、既存のライブラリを使うとどうしても対応できないときに「ヤレヤレ.........めんどくさいナァ～」と言いながら重い腰を上げて何とかがんばるのが適度に良い、怠惰なプログラマーではないでしょうか。ソートなんて、sort(), sorted() がいい感じにやってくれるからいいんですよッ！！
とは言いつつ、計算量 (O) は、まったく知らないよりはある程度概要を知っておき、普段から意識できるようにしておいた方がよい概念なので、今回は計算量についてざっくり感覚を掴めるようにご紹介します。計算量のきちんとした定義の話は長くなるので、しっかり勉強したい人は別のちゃんとした資料を当たってください。
計算量は、O(1) や O(n) のように O() の中に数値や式を書いて表します。カッコの中にはその処理がどれくらい大変かが記してあり、処理する対象が増えていくとどのようにして大変さが増えていくかを表しています。そのため、これだけで実際の処理時間が求まるわけではないですし、仮に O(n) という計算量であったとしても n に具体的な数値を代入して何か具体的な値が求まるものでもないということに注意をしてください。
また、一般的な計算量には様々な対象が含まれています。例えば、処理時間やメモリ使用量といったものも対象になります。今回はひとまず処理時間に注目していきます。
計算量の例
代表的な計算量の例をあげていきます。
O(1)：処理をする対象が1個でも10,000個でも、値を取得する時間はほとんど変わりません。リストから値を取る場合、O(1) です。コードの例としては以下のような感じです。
print(list_data[i])
O(n)：処理をする対象の数が増えると、それにつれて処理時間がかかるケースです。リストの内容を全て調べる場合、n 個要素があれば n 回処理が必要なわけで、O(n) になります。直感的にもわかりやすいですね。コードの例としては以下のような感じです。
for d in list_data:
print(d)
O(n^x)：処理をする対象の数が増えると、数の n 乗倍の速さで処理時間がかかるケースです。例えば、FullHD(2K) から4Kになると一辺の画素数は倍でも面積は4倍になりますね。コードの例としては以下のような感じです。
width = 1920
for y in range(width * 9 / 16):
for x in range(width):
print(image[x][y])
O(logn)：log は魔法の関数で、中の数字が10倍になっても logn の結果は1しか増えない（底が10の場合←こういうのを書いておかないと突っ込まれるので書くのですが、ざっくり雰囲気を掴むときには気にしなくて良いです）ということになります。つまり、扱うデータの数が爆発的に増えても、処理に必要な時間はそれほど増えないということを意味します。
ソート済みのリストから指定した値のものを取得する場合に二分探索という方法を使うことができます。この二分探索が O(logn) となります。コードの例としては以下のような感じです。
def binary_search(list_data, v):
l = 0
r = len(list_data)
while True:
p = (l + r) / 2
print(l, p, r)
if list_data[p] == v:
return p
if v < list_data[p]:
r = p - 1
else:
l = p + 1
list_data = [pow(i, 2) for i in range(10)]
print(binary_search(list_data, 9))
While ループが回るたびに調べる範囲が半分になっていき、最終的に必要な値の入っているインデックスを取得できます。そのため、range(10) の値を増やしても探索にかかる時間の増加は少しで済みます。
このあたりを把握していれば普段の業務で使い所があるとおもいます。ざっくり、O(1) は神、O(logn) はすごい、O(n) はまあ普通、O(n^x) は x が多いか扱うデータが多いとヤバいという意識をもっておくのが良いです。
計算量の何が嬉しいの？
計算量という概念は、まずは自分がやりたいと思っている処理がどれくらい大変かを把握することに使用できます。また、自分が見積もった処理時間と実際の処理時間に大きなちがいが生じていないかを確認することにも使用できます。
計算量という概念自体はプログラミングだけではなく、ほかの部分にも応用することができます。例えば業務を行う場合でも、扱う画像のサイズが2Kから4Kになったらヤバいなという感覚をもつことは多いですよね。ただ、それを発注する側は単純に2Kから4Kという、倍になった数字しか見ていないので感覚と実体に差が生まれてくるのが恐ろしいところです。これが8Kになると、さらに4倍で、2Kに比べて面積比で16倍となります。しかし、見た目の数字上では4倍しかなく、直感と実体に大きなずれが生じてしまうため、非常に危険です。このような画像処理をするときは、横幅が倍なら必要になるピクセル数は4倍だな～という感覚がとても大事です。
こういう感覚を具体的な記述に落とし込んだのが計算量です。
計算量という概念に落とし込むことができれば、次はその計算量をどう扱うかを考えることができます。処理時間がかかっているところに O(n^2) の処理があれば、O(n) に落とし込めないか考えるといったことができるようになります。実際の感覚としては、O(n^2) を O(n) に、もしくは O(n) を O(1) に落とし込めれば、実時間で数十倍から数百倍程度の高速化ができることがよくあります。
計算量のハマりどころ
肝心なのは、O は実際の処理時間と対応するものではないということです。O(1) の計算量でも1日かかる処理だってあり得ますし、O(n^100) でも一瞬で終わる処理だってあり得ます。理論上の計算量はとても大事ですが、仕事で使う場合は、いくら計算量が多くても実用的な時間で処理が完了するなら十分だという考え方もできます。また、計算量で現れる部分以外の処理時間がほとんどを占めることも多々あります。画像処理をいくら高速化しても、ファイルの読み書きに大部分の時間を使っていたら有効な手だてを打ったとは言えません。
現場では実際の処理時間を測ることがとても大事で、それを元に各種見積もりを立てます。その上で、扱う対象が大きくなったときにどうなるかという予測に使ったり、何かトラブルが起きたときに計算量を見積もって適切な内容に収まっているかを判断するという使い方をするのが良いでしょう。
まとめ
今回は計算量に焦点を当てました。計算量という概念はより良いプログラムを書くことに直結するわけではないですが、ユーザーに負担をかけないプログラムをつくる上でとても役に立つものです。本連載の第35回でご紹介した、レスポンスタイムを改善するために行なった処理の分割や並列化のながれも、O(n) となっている処理を O(1) に変換する手続きと見ることもできます。また、これまでの連載で何度も繰り返してきた「データを細かく分けて個別に管理する」というやり方も、複雑な概念を単純化して個々の複雑さ（計算量）を減らすとともに、n の部分を小さくすることで扱いづらい状態になるのを防ぐという効果があります。こうやって考えると、意外と応用が効きそうな気がしてきます。
今回は時事問題（？）ということで計算量について考えていきましたが、本当はそれ以前にプログラムの処理時間を計測するという話に触れる必要があります。そのため、次回はプログラムの処理時間の測り方について考えていきます。
第39回の公開は、2021年11月を予定しております。
プロフィール
