[logo] Web連載「数学ガールの秘密ノート」
Share

第323回 シーズン33 エピソード3
アルゴリズム、なかなか大変(前編)

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

$ \newcommand{\ABS}[1]{\left|\mathstrut #1\right|} \newcommand{\TT}[1]{\textrm{#1}} \newcommand{\ANGLE}[1]{\angle\textrm{#1}} \newcommand{\TRI}[1]{\triangle\textrm{#1}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} \newcommand{\FOCUS}[1]{\fbox{ $#1$ }} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\NEQ}{\neq} \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\PS}[1]{\left(#1\right)} \newcommand{\LL}{\left\langle\,} \newcommand{\RR}{\,\right\rangle} \newcommand{\LLRR}[1]{\LL#1\RR} \newcommand{\Enil}{\textbf{nil}} \newcommand{\Fnext}{\textrm{next}} \newcommand{\Fprev}{\textrm{prev}} \newcommand{\Fvalue}{\textrm{value}} $

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

双倉図書館の一般講座《リンクとストラクチャー》でアルゴリズムを学んできたテトラちゃんは、 自分の理解のため、学んだことをに向けて《講義》している。

最大の値を求めるMAX-VALUEを題材にしたり(第321回参照)、 線形リストのノードを先頭に移動するMOVE-TO-FIRSTを題材にしたり(第322回参照)と、 いろんな議論を重ねてきた。

いまは、 リストヘッド付き線形リストというデータ構造を議論しているところ。

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

List 9:リストヘッド付き線形リスト版MOVE-TO-FIRST

実行例

はしばらくList 9を眺めた。

うん、確かにずいぶんシンプルになったけど……!

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

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

テトラちゃんが図を描こうとしているあいだ、はもう一度List 9を読み返した。

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

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

HEAD-TO-FIRST(H, v)でvに31が渡された場合の、H6, H7, H8の動き

は、彼女が描いた図を見てショックを受けた。

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

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

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

テトラ「先輩?」

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

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

「なるほどねえ……」

そしてまたは『グラフを描かないのが君の弱点だ』といったミルカさんのことを思い出した。

グラフに限った話じゃないなあ……

代入で起きていること(左辺値と右辺値)

テトラ「先輩はすっと理解してしまいましたが、あたしはアルゴリズムの一般講座で悩んだのは、たとえば、 $$ 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 $$ は自然に読んじゃったけど、左辺と右辺で確かに違うものを表しているね」

$p.\Fnext \leftarrow q.\Fnext$

左辺の $p.\Fnext$ は、《pが指している先にあるノードの、nextフィールドという場所》を表している。

右辺の $q.\Fnext$ は、《qが指している先にあるノードの、nextフィールドに保持されている》を表している。

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

※nextフィールドに書かれた数値はアドレスの例を表しているものとします。

※nextフィールドに書かれた数値はアドレスの例を表しているものとします。

テトラちゃんのクイズ

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

テトラちゃんはにこやかにそう言って、人差し指を立てた。

「おっ?」

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

「理由……?」

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

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

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

リストヘッドがない場合

  • 先頭のノードには《一つ前のノード》が存在しません。
  • 先頭のノード以外には《一つ前のノード》が存在します。

リストヘッドがある場合

  • すべてのノードには《一つ前のノード》が存在します。

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

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

「なるほどね」

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

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

「今度は何だろう」

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

「うーん……」

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

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

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

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

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

「循環リスト?」

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

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

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

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

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

「……」

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

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

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

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

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

与えられたリストヘッド付き循環リストCに含まれているノードのうち、 valueフィールドの値が、与えられたvに等しいものがあるかどうかを判定する手続きCONTAINS(C, v)を書いてください。

手続き

  • $\textbf{CONTAINS}(C, v)$

入力

  • 検索の対象となるリストヘッド付き循環リスト $C$
  • 検索する値 $v$

出力

  • vに等しいvalueフィールドを持つノードが見つかった場合にはtrueを返します。
  • vに等しいvalueフィールドを持つノードが見つからなかった場合にはfalseを返します。

CONTAINS(C,v)への入力&出力例1

入力

  • $C = \LLRR{31,41,59,26,53}$
  • $v = 59$

出力

  • true(Cが表す数列の中に59が含まれているため)

CONTAINS(C,v)への入力&出力例2

入力

  • $C = \LLRR{31,41,59,26,53}$
  • $v = 99$

出力

  • false(Cが表す数列の中に99は含まれていないため)

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

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

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 435本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2021年5月14日)

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home