明日から役立つ?プログラマーの考え方講座 その3
「大きい問題を小さく分ける」

こんにちは、鳥井雪です。
ヒューマンアカデミー こどもプログラミング教室の教材監修をしています。
このコラムでは、現役職業プログラマーとして、実際にプログラマーが毎日どんなことを考えてプログラミングしているかを、わかりやすく紹介していけたらと思っています。

今回は、「大きい問題を小さく分ける」について。

“これをしたい”“これをしてほしい”と課題が設定された時、それが大きめだったり難しめのものだと、「どこから手をつければいいんだろう……」とはたと手が止まってしまうことがあります。 そんな時にはまず深呼吸して、落ち着いてから、呪文をとなえます。 「大きい問題は、小さく分けられる。小さく分けたら、問題は解ける」 そうするとどうにか頭と手が動き始めるのですが、この「小さく分ける」にもコツがあります。 今回はその入り口を紹介できればと思います。

小さく分けるやり方で今回お話するのは、

の二つです。
ほんとうは「手順に分解する」の一種として「パターンを見つける」があるのですが、「パターンを見つける」のほうがちょっと特徴的なので、分けてお話ししますね。

手順に分解する

こちらは、プログラミングを始める時の基本動作のようなものです。
プログラミングの入門書にもよく、「コンピューターは大きな目的だけを伝えてもその手段を見つけることはできません。一つ一つの動作を順番通りに明確に指示しましょう」といった説明があると思います。 たとえばわたしがが翻訳を務めた子供むけプログラミング絵本『ルビィのぼうけん こんにちはプログラミング』(リンダ・リウカス著、翔泳社)では、練習問題の一つに

「歯をみがく」という動作を細かく分解して指示してみよう

というのがあります。
「歯みがき」と、人間なら一言で伝わる動作を、

・洗面所に行く
・歯ブラシを手に取る
・蛇口から水を出す
・歯ブラシを水で濡らす
・水を止める
・歯みがき粉チューブを手に取る
...

といった調子で分解してみよう、というものです。

これは、実際の仕事を進める時にも有効で、例えば

“このボタンを押すとTwitterのアカウントでログインできる機能を作りたい”

という課題を、

・ボタンを表示する
・ボタンが押された時にTwitterの認証画面へと繋がるよう設定する
・Twitterから返ってくる認証情報を受け取る
・ログイン成功だったらログイン後の画面を表示する

と分けていって、一つずつ解決してゆけば、いつのまにか課題が達成されていることになります。

手順に分解することで、一つ一つの小さな問題の解決に注力できるようになります。
小さな問題の解決は、

・考えやすい
・問題が単純なので、間違いがあってバグが起こっても気付きやすい
・気持ち的にも取り掛かりやすい

といいことだらけです。

また、作業を分割することで、一つ一つの時間の見積もりがしやすくなるため、 もとの大きなタスクの最終的な所要時間見積もりも逆算して正確になりやすい、という、職業プログラマーらしいメリットもあります。

ここでちょっと意識したいのは、大きな問題を小さく分けてから、最終的な問題解決につなげるためには、 本当は「小さく分けたものをもう一度集め直して大きな問題へと戻す」という過程があることです。 ここで挙げたような単純な手順化だと、その「戻す」過程が単に「順番に行動を積み重ねる」だけなので、 あまり気にされません。

ですが、次の「パターンを見つける」の場合はそうではありません。

パターンを見つける

大きな問題を小さく分けるとき、パターンを用いた次のような方法があります。

・同じパターンを持つ小さな部分に分ける
・分けた結果がまだ大きい場合は、その結果を同じ手順でさらに小さくする
・問題が解ける大きさになったら、その部分の問題を解いて、部分の解を出す

そして、部分の解が出揃ったら、

・分割したのと逆方向に、部分の解を統合していく
・最初の全体まで統合できたら、おしまい

なんて、言葉だけだとちょっと想像しにくいですよね。
このやり方の有名な例として、バラバラの順番の要素を一つの順番に並べ換える方法の一つ、「マージソート」があります。
ちょっと長くなりますが、面白いので次の例の数字の並びを目で追ってみてください。

[10, 1, 7, 5, 6, 11, 8]

という数を大きさ順に並べたいとき、

[10, 1, 7, 5] | [6, 11, 8]

と半分の長さ(奇数なので4つと3つ)の部分に分けます。
分けた部分もまだまだ、二回以上の並べ替えが必要そうなので、

( [10, 1] | [7, 5] ) と ( [6, 11] | [8] )

とさらに分けます。2つの数の大小は比べられるので、問題は解ける大きさになりました。ここで分解はおしまい。
それぞれの部分を大小で並べ替えます(8 は1つだけなのでそのまま)。

( [1, 10] | [5, 7] ) と ( [6, 11] | [8] )

部分の解が出揃ったので、今度はこれを統合していきます。
このとき、まず左の

[1, 10] | [5, 7]

だけを見ます。
2つに分けたうちのそれぞれ小さい(先頭にある)方、1 と 5 を比較して、1が小さいので、1を統合の結果に入れます。

結果:[1]

次に、残りの

[10] | [5, 7]

の2つに分けたうちのそれぞれ先頭の、10 と 5 を比較して、5が小さいので、 統合の結果の一番最後に5を入れて

結果:[1, 5]

(後から結果に追加される方が大きいことはすでに分かっているので、ここでは後ろに追加するだけです)

残った [10, 7] を比較して、7が小さいので、統合の結果の一番最後に7を入れて

結果:[1, 5, 7]

最後に

結果:[1, 5, 7, 10]

となります。これで、部分の解の集まりの

( [1, 10] | [5, 7] ) と ( [6, 11] | [8] )

の左側の整列ができました。現在の途中経過は

[1, 5, 7, 10] と ( [6, 11] | [8] )

です。右側 [6, 11] | [8] も同様にして、先頭同士を比較して、小さかった方を結果の最後に入れます。

結果: [6]
結果: [6, 8]
結果: [6, 8, 11]

となります。これで左右とも整列した結果になりましたので、最後の統合です。 全部今までと同じ統合のやり方、 「先頭同士を比較して、小さかった方を結果の最後に入れていく、残った要素でさらに先頭同士を比較する」を繰り返し、

[1, 5, 7, 10] | [6, 8, 11]
結果: [1]
結果: [1, 5]
結果: [1, 5, 6]
結果: [1, 5, 6, 7]
結果: [1, 5, 6, 7, 8]
結果: [1, 5, 6, 7, 8, 10]
結果: [1, 5, 6, 7, 8, 10, 11]

全ての部分を統合し終わったので、これで整列はおしまい。
「一つの順番に並べ換える」という目的が達成されています。

ちょっと長かったかもしれませんが、ポイントは、部分を全体にまとめ上げるときに「先頭同士を比較して、小さかった方を結果の一番後ろに加える」という単純な1つの処理を繰り返すことです。 1つの処理が単純であれば、間違いの余地は少なくなります。プログラムの文にする時にも同じく、単純に、間違いの余地なく書くことができるのです。

また、1つの処理の量が測りやすいので、その合計としての全体の処理の量の見積もりも可能です。
こういった短くすっきり書けるパターンを探したり、利用したりするのもプログラミングの楽しみの1つなのです。

まとめ

毎日の生活の中でも、ちょっと大きめの「やること」があると、ついおっくうで先延ばしにしてしまうことってあると思います。 そんなとき、1つの作業だと思っているものを細かく分けて手順を意識したり、パターンがどこかにないかを探したりすると、意外と取りかかれるものです(あと、作業の全体量が見積れて危機感が背中を押してくれたりします…)。
「大きい問題を小さく分ける」は、ぜひ自分の味方にしてみてください。

一覧ページへ戻る