一度計算した値を再利用して、高速化するアルゴリズムを考えよう #パズルのアルゴリズム問題

前回（複数の解き方を考えて実装してみよう！ #パズルのアルゴリズム問題）は単純にプログラムを作成するだけでなく、数学的な考え方を取り入れることで効率よくパズルを解けることを紹介しました。また、複数の解き方を考えることがプログラミングの醍醐味だということも書きました。今回の問題も、ぜひ以下の解き方を参考にして、複数の解き方を考えてみてください。

しかも、「動くプログラム」を作るだけでなく、できるだけ速く処理するための工夫を考えてみることが大切です。ほんの少しアルゴリズムを見直すだけで、処理速度が10倍、100倍になることは珍しくありません。よく使われるアルゴリズムを学んでおき、いつでも使えるようにしましょう。

先月の問題の解答例

【先月の問題】
こどもの頃に階段でよく遊んだゲームを考えます。じゃんけんして、勝った手によって進む段数が異なるゲームで、グーで勝ったときは「グリコ」、チョキで勝ったときは「チョコレート」、パーで勝ったときは「パイナップル」と言いながら進みます（それぞれ3段、6段、6段進む）。
AさんとBさんの2人がこのゲームをします。整数m, nが与えられたとき、３m段の階段で、じゃんけんをn回行います。じゃんけんに勝ったほうが進むことを繰り返したとき、Aさんが先にゴールに到達するようなそれぞれの出す手が何通りあるか求めるプログラムを作成してください。

なお、じゃんけんがn回未満でもAさんが先にゴールした場合や、Aさんがゴールの段数を超えた場合もカウントします。あいこの場合は2人とも進みません。m, nはともに1以上10以下の整数とします。
例えば、m=5, n=3のとき、次の20通りがあります。

再帰を使って考える

じゃんけんをしたときに、変わるのはその勝者の位置と残りの回数です。ここでは、勝者だけでなく、AさんとBさんの両方の位置と残りの回数を元に計算する関数を考えてみましょう。どちらかがゴールに着くまで何度も同じ処理を繰り返すので、パラメータを変えながらこの関数を繰り返し実行して解くことにします。

この処理を行う関数を定義すると、その関数からまた同じ関数を呼び出すことになります。このように、ある関数の中から同じ関数（自分自身）を呼び出すことを「再帰」といいます。

再帰はプログラミングだけで使われる言葉ではありません。身近な例として、「合わせ鏡」を使って説明されることがあります。2枚の鏡を向かい合わせに置き、一方を覗き込むともう一方の鏡に映ったものが無限に現れます。

また、カメラで撮影している映像をリアルタイムにディスプレイに写し、そのディスプレイをカメラで撮ってみると、同じように無限に表示されます。これも再帰の身近な例だと言えます。

先月の問題の解答例

先月の問題も、この再帰を使って実装できます。必要なパラメータはAさんの位置、Bさんの位置、残りの回数だけですので、これを引数として渡します。Aさんの位置を「a」、Bさんの位置を「b」、残りの回数を「remain」としてプログラムを実装してみます。

Aさんの位置が指定された段数以上になるとゴールに到達して探索を終了します。また、Bさんの位置が指定された段数以上になった、もしくは残りの回数がなくなった場合は、失敗して探索は終了します。

それ以外の場合は、AさんとBさんが出した手によって動く段数を変えていきます。このパターン数を数えると、Rubyでは、以下のように実装できます。

このプログラムでも、階段の段数が少ない場合は問題なく処理できますが、じゃんけんを行う回数が10回あたりから処理に時間がかかるようになります。今回のように、10回であればなんとか解けますが、これを超えるともう少し工夫が必要です。

一度使ったものを再利用してみる

処理に時間がかかるのは、AさんとBさんの位置としてすでに調べたパターンを何度も計算しているからです。例えば、「最初にAさんがグーで勝って次にBさんがグー勝った場合」と、「最初にBさんがグーで勝って次にAさんがグーで勝った場合」では、それ以降の処理は同じです。

同様に、AさんとBさんの位置、残りの回数が与えられたとき、同じ位置、同じ残り回数の場合が何度も発生します。そこで、一度調べた場合はその計算結果を記憶しておくと、処理量を減らすことができます。

今回のように再帰的な処理を行うときに、一度処理した結果を保存しておく方法は「メモ化」といいます。保存する量が多くなってくると、メモリの使用量は増えますが、今回のような例では処理が圧倒的に高速になります。

メモ化を実装するには、処理した結果を保存しておく領域を用意しておきます。関数の先頭で保存されているかチェックを行う処理を入れておくと、処理を呼び出したときにすでに保存されていればそれを使い、保存されていない場合は関数の処理を実行します。関数の結果を返すときに、合わせて結果を保存しておきます。

例えば、Rubyの場合は以下のように数行追加するだけで実装できます。

このように変更すると、今回の場合はじゃんけんの回数が30回であっても一瞬で処理が終わります（出力結果の桁数が大きくなるため、32bit整数の範囲内に収まらなくなりますが）。実際に試してみると、その処理速度の違いに驚く方もいらっしゃるかもしれません。

今回のポイント

再帰を使うと、処理量が多くても非常に短いソースコードで実装できることがよくあります。ただ、実装するのは簡単でも、単純に実装すると処理に時間がかかってしまいます。ソースコードを短くできるとそれで満足してしまいがちですが、同じ処理を何度も実行すると見た目以上に処理に時間がかかる場合があります。

再帰を使うとシンプルなソースコードで解ける問題はパズル問題ではよく登場します。さらに、この「一度使った値を保存しておいて、処理を高速化する」という考え方は、パズル問題だけでなく実務においても役立ちます。

例えば、データベースにアクセスして条件を満たすデータを取得する場面を考えてみましょう。郵便番号が与えられ、データベースから該当する住所の情報を取得するようなプログラムはよく見かけます。このとき、取得するデータが1件であれば問題ありませんが、もし大量のデータが存在した場合、同じ郵便番号のデータを何度も取得するような実装になっていることはないでしょうか？

データベースへのアクセスはローカルにあるファイルやメモリへのアクセスに比べて圧倒的に時間がかかります。場合によっては外部にあるデータベースサーバーとの通信が発生するかもしれません。このような場合、一度検索した結果を保存しておくことは有効です。事前に郵便番号で並べ替えておくなど工夫すると、メモリ領域もほとんど消費しません。

テストデータとして数件用意するだけでは気づかないことも、ソフトウェアの開発ではよくあります。大量のデータが与えられたとき、どれくらいの時間がかかるのか、開発する段階である程度考えておく必要があります。

今月の問題

この連載では、毎月1回問題を出題し、次回にその解答や解説、アルゴリズムの紹介を行います。問題を解く速さを競うわけではありませんが、解いた方は自由にオリジナルの解答を公開していただいて構いません。

【今月の問題】
山手線には現在29個の駅があります。
n人をそれぞれ異なる駅に、間隔ができるだけ離れるように配置することにしました。
この配置におけるn人の間隔の最小値を求めてください。
（つまり、間隔の最小値が最大になるような配置を求め、その間隔の最小値を求める。）

なお、各駅の間の距離はWikipedia（https://ja.wikipedia.org/wiki/山手線）による値を使用します。
このページによると、各駅の間の距離(単位：km)は、東京駅から内回りで以下のリストのようになっています。

[1.3, 0.7, 1.0, 0.6, 1.1, 1.1, 0.5, 0.8, 1.6, 0.7, 1.1, 1.8, 1.2, 0.9, 1.4, 1.3, 0.7, 1.5, 1.2, 1.6, 1.5, 1.2, 0.9, 2.0, 2.2, 1.5, 1.2, 1.1, 0.8]

例えば、n=3のとき、大塚駅と恵比寿駅、有楽町駅に配置すると、それぞれの間隔は以下のようになります。
大塚駅 ←11.6km→ 恵比寿駅 ←11.6km→ 有楽町駅 ←11.3km→ 大塚駅
このとき、その間隔の最小値は11.3となります。

なお、nは1<n<15の整数とします。

（著者プロフィール）

WRITING：増井敏克（マスイトシカツ）

増井技術士事務所　代表。技術士（情報工学部門）、テクニカルエンジニア（ネットワーク、情報セキュリティ）、その他情報処理技術者試験に多数合格。また、ビジネス数学検定1級に合格し、公益財団法人日本数学検定協会認定トレーナーとしても活動。「ビジネス」×「数学」×「IT」を組み合わせ、コンピュータを「正しく」「効率よく」使うためのスキルアップ支援を行っている。著書に『エンジニアが生き残るためのテクノロジーの授業』『おうちで学べるセキュリティのきほん』『プログラマ脳を鍛える数学パズル』『もっとプログラマ脳を鍛える数学パズル』『図解まるわかりセキュリティのしくみ』（翔泳社）、『プログラミング言語図鑑』『シゴトに役立つデータ分析・統計のトリセツ』（ソシム）がある。

なつよさん☆インフラガール