アルゴリズムってなんやいね？　って時に読む記事【初心者向け】

図書館でアルゴリズムの本を見かけたときに「そういえば会社の研修でもやったなぁ」とふと思い出しました。

アルゴリズムはコンピュータになんらかの処理をさせて解を得る時の手順のこと。

Unityでスクリプトを書く時には、みんな意識的、無意識的にアルゴリズムを考えて、それをプログラミング言語で表現しているのです。

いいプログラミングを行うためには、いいアルゴリズムが欠かせません。

というわけで、今一度初心に立ち返ってアルゴリズムについて考えます。この記事では具体的なソートや有向グラフの話はせず、アルゴリズムって何？　どんなことを考えればいいの？　といったあたりを扱いたいと思います。

環境

macOS 10.14 Mojave

Unity2018.3.14f1

Unity Hub 2.1.0

アルゴリズムって？

アルゴリズムとは目的を達成するための一連の手順のこと。

よくある例えですが、朝起きて会社に行く時の自分の動きを考えてみましょう。

朝起きたら、カーテンを開けて、トイレに行って、洗面所に行って手と顔を洗って、着替えて、髪をセットして、ご飯を食べて、歯を磨いて、カバンの中身を確認して、家の鍵を持って、靴を履いて、鍵を閉めて、駅に向かう、みたいな一連の手順がアルゴリズムです。

もっと言えば、起きた時間でも条件分岐が必要ですよね。余裕を持って起きたのなら、準備が終わった後に勉強タイムを設けたり、ギリギリで起きたのならいくつかの手順をすっ飛ばしたり。もうダメな時間だったら会社にごめんなさいの連絡をする手順が増えたりと、人間って結構細かいアルゴリズムを無意識でさばいているんです。コードで実装したらしんどそう。

コンピュータでも、ひとつひとつの手順を考えてあげて、手順を教えてあげる必要があります。IT系の人が「アルゴリズム」って言ってたらだいたいこっちのコンピュータアルゴリズムを指しています。

アルゴリズムを考える上で大切なのは、正しい解を効率的な資源利用で導き出すこと。

コンピュータで何らかの計算をさせる以上、正しい計算結果を出してもらわないといけません。さらに、時間だったり、計算で使うメモリだったりの資源もなるべく少なめに使うアルゴリズムが理想です。

正しい結果を出せるけど計算に100年かかります、だとなかなか実用は難しいですよね。

なので、なるべく最短時間で解を導き出すアルゴリズムを選択するのがポイントです。

アルゴリズムの正しさ

何を持って正しいとするかは、目的や入力によります。

例えば、カーナビで目的地までの最短経路を表示したい場合は、一番短時間で進める道が正解になります。

古いナビなんかだと地図情報が更新されていなくて、目の前にビルが建っているにもかかわらず「直進してください」みたいなこともありますが、アルゴリズム的には正しかったりします。「え？」って思う気持ち、よく分かります。ちゃんと意図を説明します。

アルゴリズムはざっくり言うと方程式みたいなもので、与えられた入力に対して、方程式を通して解を導きだします。

カーナビが知っている地図情報の中で目的地までの最短経路を選んだだけなので、アルゴリズムは間違っておらず、入力としての「カーナビが知っている地図情報」が間違っていただけです。だから、地図情報を更新する必要があったんですね。

シミュレーションなどの近似的な計算の場合は、導きだした結果が現実の事象と完全一致することは少ないです。しかし、誤差が許容できる範囲に収まっていれば「正しい」と言って良いでしょう。

プログラミングの世界に翻訳すれば、アルゴリズムはメソッドで、入力は引数、計算結果は戻り値です。想定される引数を元にメソッド内で処理を行なって、戻り値として値を返します。

資源利用の効率

同じ結果を出すのであれば、コストは少なければ少ないほど良いです。

アルゴリズムAでは処理時間が1秒、アルゴリズムBでは処理時間が3秒、出す結果はどちらも同じだったら、そりゃアルゴリズムAが良いに決まっています。

アルゴリズムが資源を使う、と言った時によく使われる指標は時間です。次いでメモリ、CPUなどのコンピュータ内の資源です。

これらの指標をよく見て、なるべくコストが少ないようなアルゴリズムを組み立てるのがイケてるゲーム開発者(プログラマ)なのです。

処理時間の見積もり

時間効率の良いアルゴリズムを選択(または作成)するにあたって、処理時間の見積もりが必要になります。

コンピュータ内の処理には必ず終わりがあります。(無限ループは勘弁な！)

処理の終了をいつ迎えるのか、見積もることも重要なんです。

この見積もりに使われるのはO記法(おーきほう)、あるいはランダウ記法、漸近記法とも呼ばれる表し方です。この大きいOは英語のorderから。orderは桁数の程度を表す意味で使われます。

\(O(n)\)といったように表記され、\(O\)はオー記法ですよーという宣言、nは入力データの数です。この表記の意味するところは「処理時間は入力データの数に比例して大きくなりますよ」です。

ループ処理の中にループ処理が含まれているなど、入れ子のループなどの場合は入力データの2乗の規模になったりします。この場合は\(O(n^2)\)のように表記され、入力データの2乗のオーダーで処理時間が増えていきます。

数学が嫌いな人にとっては身の毛のよだつ話ですが、\(O(n\log n)\)みたいな見積もりも出てきます。(底は2)

これらの見積もりでは具体的な処理時間の計算はしなくて良く、入力データnの数が増えると、処理時間がどのように増加するかの指標として使います。

指数関数的に増加する\(O(n^2)\)のようなアルゴリズムでは、nが小さければそれほど処理時間を気にしなくて済みますが、nが大きいとびっくりするくらい処理時間が大きくなります。指数関数の例として2の累乗をグラフ化してみました。nが10でもこの通り、急激に大きくなっていきます。

逆に対数関数的に増加するアルゴリズムでは、nが大きくなったとしてもそこまで大幅な処理時間の増加には繋がりません。グラフでは底が2の対数を表しています。nが10でも、指数関数のグラフに比べたら処理時間はそんなに増えてないですね。

同じ結果を出せるのであれば、処理時間の短いアルゴリズムを選択するのがベストです。上の例なら、対数のアルゴリズムを選びましょう。ほら、これで対数も好きに……はならないか。

このように、効率的なアルゴリズムを選択する上でも処理時間の見積もりができるといい感じです。

いまアルゴリズムを考えるメリット

2019年現在、近年のコンピュータの進化は凄まじく、スマートフォンですら一昔前のPCと同等の性能を持つまでになりました。

このブログはUnityでゲームを作ることがテーマになっているのでスマホアプリに目を向けると、多少処理時間が長いアプリ、煩雑な処理を行なっているアプリでもスマホで動いちゃうんですよね。

だからあまり意識しなくてもゲームが作れちゃう部分ではありますが、そうした中で処理時間が早く、ユーザを待たせないようなゲームがあれば、快適に遊べることからどんどんユーザが流れていきます。

正直に言えばゲームの印象の8割は見た目と音楽で決まってしまいます。でも残り2割の部分でユーザを取りこぼさないためにも、快適なゲームプレイを支えるプログラミングが大切ですし、そのベースとなるアルゴリズムはもっと重要です。

単純に動かすための手順という位置付けから、快適に効率よく動かすための手順という考え方にシフトすると、ゲーム作りだけではなくプログラミング全般でレベルアップできます。こうなれば、どこでも戦えるプログラマにもなります。そのはず。

なので、プログラミングに慣れている人だったら自身の振り返りに、初心者だったら基礎固めにアルゴリズムのことを意識してみると良いと思います。

まとめ

アルゴリズムについて、そもそも何なのかという話から、効率の良いアルゴリズムを選択、あるいは作成するための指標である処理時間の見積もりについて考えてみました。

初心者向けに書いているのでちょっとざっくりではありますが、Unityでスクリプトを書くときにアルゴリズム、処理時間を意識していけるとゲーム作り自体も楽しくなっていきます。