アルゴリズムの説明

アルゴリズムを正しく設計そして解析するためのスキルは、アルゴリズムを分かりやすく説明するためのスキルと結びついています。少なくとも私の講義において、アルゴリズムを完全に説明するために必要な要素は次の四つです:

四つの要素をこの順番で開発する必要はありません (というより、そうしない方がいいかもしれません)。問題の仕様、アルゴリズムの説明、正しいことの証明、そして実行時間の解析は同時に発展します。例えば速いアルゴリズムを得るために問題をいじったり、正しさの証明におけるトリッキーなケースに対処するためにアルゴリズムを変更したりするかもしれません。ただしそうだとしても、四つの要素を別々に示すのが読者にとって普通は最も分かりやすいでしょう。

どんな書き物もそうですが、書こうとしている説明を正しい聴衆に向けることは重要です。私が勧めているのは、疑い深く、能力があるけれども自分ほど賢くないプログラマーに向けて説明を書くことです。例えば六か月前の自分を考えてみてください。新しいアルゴリズムを開発する中で、あなたは問題とそれを解く自分のアルゴリズムに対する様々な視点からの直感を手に入れ、形式的でない証明は頭の中で行えるようになります。しかし、後になってあなたのアルゴリズムを読む人、あるいはそのアルゴリズムに基づいて書いたコードは、あなたと同じ直感や体験を共有しません。六か月後のあなたもそうです。彼らが受け取るのは、あなたが書き下した説明だけなのです。

アルゴリズムを他人に説明する必要がなかったとしても、聴衆を考えながらアルゴリズムを開発することは重要です。正確に伝えようとすれば正確に考えるからです。特に、文章を文字通りに解釈する初心者を聴衆として考えれば、自分の高レベルのアイデアがどれだけ「明らか」で「直感的」に見えたとしても、アルゴリズムを詳細に検討せざるを得ません1。同様に疑い深い聴衆を考えれば、正しさと効率に関する議論は自分の直感と知性ではなくて強固な論理に基づいたものになるでしょう。

次の点はどれだけ強調してもしすぎることはありません: アルゴリズム設計者としてのあなたの一番重要な仕事は、他の人になぜ自分のアルゴリズムが動くのかを説明することです。もしアイデアを他の人間に伝えられないのなら、そんなアイデアは存在しないも同然です。正しく動いて効率の良い実行可能なプログラムを書くことは、二番目のゴールにすぎません。自分の賢さを自分自身、教官、(未来の) 雇い主、同僚、生徒に向かって見せつけることは、どんなに良くても三番目のゴールです。

問題の特定

新しいアルゴリズムの設計を始めるには、まずアルゴリズムが解く問題をきちんと定義する必要があります。同様にアルゴリズムの説明を始めるには、まずアルゴリズムが解く問題を説明する必要があります。

アルゴリズムの問題は現実世界の概念を使って通常の英語で表現されており、形式的で数学的な対象とは異なります。こういった問題を抽象的で正式な数学的対象 ――数、配列、リスト、グラフ、木など―― を使って書き直すのは、アルゴリズム設計者である我々の仕事です。私たちは問題に隠されている仮定がないかを調べ、明示しなければなりません (例えば "\(n\) Bottles of Beer on the Wall" の歌の例では \(n\) は非負の整数です2)。

アルゴリズムを開発する中で、仕様を改訂する必要が生じるかもしれません。例えば元の形式的でない問題の説明では指定されていなかった入出力の表現を、なんらかの表現に固定する必要が生じることがあります。また開発されたアルゴリズムが最初に目標としていた問題よりもより一般的な問題を解決することもあるかもしれません (再帰的なアルゴリズムではよくあることです)。

アルゴリズムの仕様が含むべきなのは、他の人が内部で何が起こるかを知ることなくブラックボックスとしてアルゴリズムを使うときに必要となるちょうど十分な情報です。具体的には入力の型と意味、そして出力が入力にどう依存するかです。一方、アルゴリズムの仕様はブラックボックスとしてアルゴリズムを使うときに不必要な詳細を意図的に隠すべきです。重要でないものは消しましょう。

例えば、格子掛け算アルゴリズムと農民の掛け算アルゴリズムは同じ問題を解くと言えます。なぜなら、桁の配列として表された二つの非負整数 \(x\) と \(y\) を受け取って同じように表された積 \(x \cdot y\) を計算するからです。このアルゴリズムを使う人にとって、どちらのアルゴリズムを使うかは全く重要ではありません。これに対して定規とコンパスを使ったギリシャ人のアルゴリズムが解くのは違う問題です。入出力値が桁の配列ではなく線分として与えられるからです。

アルゴリズムの説明

コンピューターで実行できるプログラムはアルゴリズムの具体的な表現です。しかしアルゴリズムはプログラムではありません。アルゴリズムとは抽象的な機械が解釈するための手続きであり、仮定している基本処理をサポートするどんなプログラミング言語でも実装できます。あなたの好きなプログラミング言語に特有な構文はアルゴリズムに全く関係ありません。構文上の細かな点を説明したとしても、本質的な部分で起こっていること3からあなた (と読者) の気を逸らしてしまうだけでしょう。優れたアルゴリズムの説明とはコードというよりも現実のプログラムにおいてコメントとして書くべきものといった方がより近いはずです。コードは物語を伝えるのに優れた媒体ではありません。

一方で平易な英語の散文による説明も通常は良いアイデアではありません。アルゴリズムには独特な構造 ――条件文、ループ、関数呼び出し、再帰など―― があり、構造化されていない散文でアルゴリズムを表現した場合、こういった構造が分かりにくくなってしまうからです。口語英語には曖昧な語や意味が微妙に違う語がたくさん含まれるので、できるだけ明確でなくてはならないアルゴリズムの説明には向きません。散文は正確さを考えると優れた媒体ではありません。

アルゴリズムを表現する一番明確な方法は疑似コードと構造化された英語である、というのが私の意見です。疑似コードは形式的なプログラミング言語と数学の構造を使ってアルゴリズムを基本ステップに分解します。そして基本ステップは数学的な記法、純粋な英語、あるいは二つを混ぜたものなどの中から一番明確なものを使って表現されます。優れた疑似コードはアルゴリズム内部の構造を説明しつつも関係ない実装の詳細を隠すことで、アルゴリズムの理解、解析、デバッグ、実装を容易にします。

アルゴリズムの説明に含めるべき情報とは、アルゴリズムを規定し、正しさを証明し、そして実行時間を解析するために必要な全ての情報です。同時に、必要でない情報は排除しなければなりません。具体的にいうと、この本を読んでいない、能力があり疑い深いプログラマーが、なぜ動くのかを理解することなく、彼らの好きなプログラミング言語でアルゴリズムを正しくかつ素早く実装できるような説明を目指すべきです。

疑似コードを書くときの私のルールであなたをうんざりさせたくはありませんが、無意識に行ってしまいかねない特にひどい致命的な行為については注意しておかなくてはなりません。絶対に、繰り返しの処理をくだけた形で書かないでください。つまり「最初に (これを) やる。次に (あれを) やる。以下同様」あるいは「この処理を (...) まで続ける」などと書かないでください。このような文章を読んで「この処理の次に何が来るんだ？」という感想を抱いたことがある人なら分かると思いますが、アルゴリズムの最初の数ステップを説明しただけでは、後のステップで何を行うかはほとんどあるいは全く分かりません。もしアルゴリズムにループが含まれるのなら、ループとして書いてください。そしてループの各反復で何が起こるのかを明示的に書いてください。同様に、もしアルゴリズムが再帰的ならば、再帰的に書き、場合分けとそれぞれの場合で何をするのかを明示的に書いてください。

  1. とりわけ、私はあなたが疑い深い初心者であると仮定します！[return]

  2. "\(\sqrt{2}\) Bottles of Beer on the Wall" と歌っている人を見たことはありませんが、"\(\aleph_{0}\) Bottles of Beer on the Wall" と歌っている集合理論学者なら何回か見たことがあります。どういうわけか彼らはいつも歌い終わる前に歌うのを止めていました。[return]

  3. もちろんこれは宗教的信念に関わる話題です。安楽椅子言語学者が絶え間なく議論を交わしている Sapir-Whorf (サピア-ウォーフ) 仮説においては、人は使う言語に紐づいた区分でしか考えることができないとされます。この仮説に関する極端な意見によると、ある言語における概念の中には他の言語話者に理解できないものがあり、それは技術が発展していない ――"jump the shark" や "Fortnite streamer" をアラム語に訳せるとは思いません―― ためではなく、言語と文化における固有の構造上の差異があるためであると言います。これよりも疑い深い視点については Steven Pinker (スティーブン・ピンカー) の『言語を生み出す本能 (The Language Instinct)』を見てください。異なるプログラミングパラダイムについてもこのアイデアはいくらか当てはまるでしょう: 「Y コンビネータがまた出てきた、なんだっけ？」「テンプレートってどうなってるの？」「Abstract Factory って何？」などです。幸いこの本が触れる分野ではプログラミング言語間の差異は十分小さく、大きな影響はありません。説得力のある反例としては、Chris Okasaki (クリス・オカサキ) による専門書 Functional Data Structures および最近のその続編を見てください。[return]

広告
このページの文章はテキストゆれないくんを使って校正されました。