第323回 シーズン33 エピソード3

アルゴリズム、なかなか大変（前編）

特別な場合もうまくいく？

テトラ「リストヘッドがあると、List 9のようにシンプルに書けるんですよ！」

僕「ちょっと待って。これって $a_1 = v$ のときでもうまくいく？　怪しくない？　だって、 H5〜H9ではどんなときでもリンクを切り換えてしまうよね？」

テトラ「驚くことに、うまく行くんですよ！」

僕「いやいや、駄目だよ。だって、 $a_1 = v$ のときは、pはリストヘッドを指していて、qは最初のノードを指している。 その状態でH6にやってくる。H6はいいとして、H7がまずいよ。だって、 $$ q.\Fnext \leftarrow H.\Fnext $$ を実行してしまったら、最初のノードは自分自身を指してしまうことになる！　線形リストが途中で切れてしまうはずだよ」

テトラ「……ところがそうはならないんですよ、先輩。 こちらのステップ・バイ・ステップで描いた図をごらんください。 先輩が気になさっていたH7を実行するときには、 $H.\Fnext$ の値は最初のノードではなくなっているので、 途中で切れることはないんですっ！」

僕「本当だね。うーん……」

テトラ「もちろんこの場合、代入を三回行って結局は何も変わっていないことになります。 でも、先頭を特別扱いしなくて済むとプログラムはシンプルになりますので、 間違いが入り込む危険性も少なくなります。 リストヘッド付きの線形リストでは、そういうことがよくあるそうです」

僕「いや……それはわかったんだけど」

テトラ「先輩？」

僕「テトラちゃんはきちんと図を描いて説明してくれたけれど、 僕は先を急いで読もうとしてしまい……まちがった。 たった三ステップしかないんだから、ほんの少しの時間を使うだけですぐに図を描けるし、 図を描きさえすれば自分のまちがいに気がつく。 その《ほんの少しの時間》を、自分が無意識のうちに惜しんだことがショックなんだ」

テトラ「双倉図書館の一般講座でも、講師の先生はそんなことをおっしゃっていました。 《ステップ・バイ・ステップ》で確かめることが、結局のところ近道になることが多いというお話です。 あたし、それにすごく励まされました。 たとえ、すごいひらめきがやってこなくても、 根気よく確かめることはあたしにもできそうだからです！」

僕「なるほどねえ……」

代入で起きていること（左辺値と右辺値）

テトラ「先輩はすっと理解してしまいましたが、あたしはアルゴリズムの一般講座で悩んだのは、たとえば、 $$ p \leftarrow H $$ という代入でした。この表記が……」

僕「これはHをpに代入するということだよね」

テトラ「はい。もちろんそうなんですが、あたしが引っかかったのは、 $$ p \leftarrow H $$ と表現されたとき、pとHとでは意味が違うという点でした」

僕「意味が違う？」

テトラ「はい。こういうことです」

• 左辺の $p$ は、どこかにあるメモリの場所を表している。
• 右辺の $H$ は、どこかにあるメモリの場所に保持されている値を表している。

僕「……ああ、確かにそうだね。 $p \leftarrow H$ と書かれているときに行われるのは、こうだから」

• $H$ と名前がついている場所に保持されている値を、
• $p$ と名前がついている場所に格納する。

テトラ「はいはい！　そういうことです。図を描いていて、それに気付いてからプログラムが読みやすくなりました。 講師の先生にお尋ねしたところ、左辺値（さへんち）と右辺値（うへんち）という名前がついているそうです。 《左辺値》は《値を保持している場所を表す値》のことで《メモリのアドレス》と思えばわかりやすいです」

僕「《左辺値》は代入の左辺に来ることができる値ってことだね。代入できる場所を表す値だ」

テトラ「だいたいはそうなんですが、プログラミング言語によってはメモリのアドレスは表しているけれど、 代入できない定数のような概念があるので《左辺値》のことを《代入できる場所を表す値》というのは不正確だそうです」

僕「そうなんだね……ところで《右辺値》の方は123のような値のことかな」

テトラ「はい。《右辺値》は、123のような値の場合もあるし、《左辺値》を《右辺値》として扱う場合もあるそうです。 先ほどの $p \leftarrow H$ の場合もそうですよね」

僕「変数Hの値は、ノードを表すアドレスだから《左辺値》といえるけど、 $$ p \leftarrow H $$ では、その値を変数pに代入する《右辺値》として扱っている？」

テトラ「そうです、そうです。いずれにしても、図を描けばあまりまちがうことはありません」

僕「いわれてみると、 $$ p.\Fnext \leftarrow q.\Fnext $$ は自然に読んじゃったけど、左辺と右辺で確かに違うものを表しているね」

テトラ「そうです！　この場合、代入によって、同じ場所を指すようになるわけですね。図に描くとわかりやすいです」

テトラちゃんのクイズ

テトラ「それではここで先輩にクイズをひとつ、お出しします！」

僕「おっ？」

テトラ「線形リストにリストヘッドをつけて、プログラムがシンプルになった理由は何でしょう？」

僕「理由……？」

テトラ「いかがですか？」

僕「リストヘッドをつけると、先頭を特別扱いしなくて良くなるから、かな。 List 8のテトラちゃんのプログラムがまさに先頭を特別扱いしていたから（第322回参照）」

テトラ「はい、そうですね。先頭を特別扱いしなくてよくなります。 もう少しいいますと、こうなります」

僕「確かにそうなるね。リストヘッドという特別のノードを最初に置くことで、 すべてのノードを統一的に扱えるようになる。だからプログラムがシンプルになる」

テトラ「はい。いうなれば《一様性》や《均一性》があるためにシンプルになるんです」

僕「なるほどね」

テトラちゃんのクイズ、もっと

テトラ「ところで先輩に、もうひとつ、クイズをお出しします」

僕「今度は何だろう」

テトラ「あたしたちは《リストヘッド付き線形リスト》を扱ってきましたけれど、 ここにはまだ《一様性》に欠けている部分があります。 それはどこでしょうか？」

僕「うーん……」

テトラ「いかがでしょう？」

僕「たぶん、リストの最後だね。リストの最後にあるノードには《一つ次のノード》が存在しない。 最後のノードのnextフィールドには、nilが保持されている。 でも、nextフィールドにnilが保持されているのは最後のノードだけ。ここじゃない？」

テトラ「はいっ！　正解です！」

僕「ということは、《リストテール付きの線形リスト》を考えることができるんだね」

テトラ「それでもいいんですが……もっと便利なものがあります。それは《リストヘッド付き循環リスト》です」

僕「循環リスト？」

リストヘッド付き循環リスト

テトラ「はい。この図のように、リスト最後のノードのnextフィールドが必ずリストヘッドを指すようにするんです。 そうすると、山手線のようにぐるっと回るデータ構造ができあがります。 これが《リストヘッド付き循環リスト》です。nextフィールドにnilはもう出てこなくなります」

僕「ちょっと待って。だったら、どうやってリストの終わりを判定するんだろう……ああ、 リストヘッドかどうかで判定すればいいのか」

テトラ「その通りです！　《リストヘッドを指している》という状況を《nilである》という扱いにするんです」

僕「……」

テトラ「な、何かおかしいでしょうか？」

僕「いや、おかしくはないし、確かに《一様性》はわかるんだけど、それだけでそんなにシンプルになるのかなあ……」

テトラ「では問題3ですっ！　プログラムを書きましょうっ！」

問題3　数列内に値が存在するかどうかの判定

僕「ああ、これは簡単だね……っとっと。いや、ちゃんと考えないと」

テトラ「……いかがでしょうか？」