Linuxを生み出したリーナス・トーバルズが考える「優れたコード」とは何か？

プログラミングをする上で、コメントをきちんと残したり、わかりやすい変数名をつけたりして「読みやすいコード」を目指す作業は重要です。しかし、「読みやすいコード」と「優れたコード」の間には、時として構造上の大きな違いがあるのも事実。そんな「優れたコード」に対するLinuxの開発者リーナス・トーバルズ氏の考え方について、エンジニアのmkirchner氏が説明しています。

mkirchner/linked-list-good-taste: Linus Torvalds' linked list argument for good taste, explained
https://github.com/mkirchner/linked-list-good-taste

Linus Torvalds: The mind behind Linux | TED Talk
https://www.ted.com/talks/linus_torvalds_the_mind_behind_linux?language=ja

トーバルズ氏は2016年のTEDインタビュー内で「連結リストの実装方法」を例とし、自身の「優れたコード」に対する考えを説明しています。連結リストはデータを線形につなげたリストのことで、データを扱う構造のひとつ。具体的には「4」や「12」といった値そのものと「次の値」を示すポインタで構成される「ボックス」を順番につなげたものが連結リストです。

連結リストをC言語で実装したコードは以下。値そのものである「value」と次の値を示すポインタ「next」で「IntListItem」構造体が作られており、IntListItem構造体からボックスが生成されます。「IntList」構造体はリストの先頭を表す変数「head」を持っています。

この連結リストからあるボックスを消去する処理について、スタンフォード大学の計算機科学講義「Computer Science 101(CS101)」で紹介されていたコードが以下とのこと。

上のコードが行っている処理はこんな感じ。まずはコードの以下の部分で「消去したいボックス」をリストの先頭から探索します。連結リストはリストの先頭からしか値をたどることができないので、まずリスト先頭のボックスのアドレスを「cur」ポインタに格納し、「prev」ポインタはNULLで初期化。curポインタが消去したいボックスのアドレスと一致するまで、curポインタを次のボックスのアドレスへと移しながら照合していきます。

先ほどの処理のイメージを図で表したものが以下。ちょうどprevポインタとcurポインタがリスト後部のボックスへスライドしていくようなイメージです。

curポインタが消去対象のボックスのアドレスと一致したら、次はボックスを消去します。以下の処理では、もし消去対象のボックスがリストの先頭でない場合は、消去対象のボックスの前のボックスが持つnextポインタに消去対象のボックスの次のボックスのアドレスを格納します。消去対象のボックスがリストの先頭である場合は、リストの先頭を指すheadポインタに消去対象のボックスの次のボックスのアドレスを格納します。

消去対象のボックスがリストの先頭でない場合の処理を図で説明するとこんな感じ。消去対象の前のボックスが持つnextポインタが、消去対象の次のボックスを指すようになるため、消去対象のボックスはどのボックスからも参照されなくなり、リストから消去されるというわけです。以下の図では「12」を値に持つボックスが消去されています。

消去対象のボックスがリストの先頭の場合は、以下のようにheadポインタがリストから2つめのボックスのアドレスを指すように処理します。

確かにCS101で紹介されているコードでもリストから要素を削除することは可能。しかし、トーバルズ氏は2016年のTEDでのインタビューにて、さらに優れたコードを紹介しています。

トーバルズ氏によるコードが以下。先ほどのコードにはあったif文が消え、シンプルなコードになっています。

C101のコードとトーバルズ氏のコードの大きな違いは「ボックスのポインタのポインタ」という、新しいポインタ「**p」が導入されている点。まず「**p」は「headポインタのポインタ」として初期化されています。

ボックスのポインタ「*p」が消去対象のボックスのアドレスと一致しない場合は、「次のボックスのポインタのポインタ」に変更。

図に表すとこんな感じで、「ボックスのポインタのポインタ」がリスト後方のボックスへと移動していきます。

消去対象のボックスが見つかるとwhile文を抜け、ボックスのポインタを消去対象の次のボックスのアドレスへと移動させることで、対象のボックスをリストから除外します。

削除処理はこんな感じ。

トーバルズ氏による改善後のコードでは、「ポインタのポインタ」を導入することで、headポインタの状態による条件分岐が不要になっています。また、curとprevの2変数による代入を行う必要もなくなり、処理がシンプルになっています。

トーバルズ氏はTEDのインタビュー内で「時には問題を別の角度から見て、特殊なケースを通常のケースに落とし込んでコードを書き直せることもあるということを理解して欲しいのです、それが優れたコードなのです」とコメント。また、mkirchner氏はトーバルズ氏によるコードを応用したボックスを追加するコードを実装し、GitHubに公開しています。