Algorithm of Dijkstra (ダイクストラ法)
そう言えば書いていなかったので三度目のプログラミング演習の感想を書き留めておく。これで今セメスターの演習は最後となる。最後の課題ということもあり、以前に比べて難易度が少し高くなっているように感じる。
求められる要素は３つ、「リスト構造」と「String型」の習熟と「ダイクストラ法」の理解。周りの反応を聞いてみるとダイクストラ法がよくわからないまま、String型のやmallocの引き起こすセグメンテーションエラーに苦しんでいるようだ。
今回の課題は提出するソースが以前と比べ長くなるが、その分学生たちにはサンプルソースが与えられる。サンプルはデータ構造の作成やダイクストラ法に関する部分のみが抜けており、それ以外の型宣言や出力関数など大半の部分は既に与えられている。プログラムの核となる箇所以外、８割程度がサンプルソースに書かれていた。これを利用することで大幅な時間削減が得られる。その代わり書かれていたコードは非常に読みづらかった。無駄なfor文やif文もあったように思う。しかし大学が生徒に求めているものに意識を集中させるための措置と考えると有用であったのは確かだ。
この最短経路問題で僕が得た一番の経験と言えばやはりデバッグ作業だろう。ご多分に漏れず、僕もセグメンテーションエラーは何度もお目にかかることとなった。だがそうした時、エラー表示"check"を挟むことでエラー発生処理部分を特定し、原因を探る作業をすれば必ず解決できた。セグメンテーションエラーというのはポインタやメモリに関するエラーであるから、そのエラー行自体ないしエラー処理部分に関わる行を推測し、エラーの理由を探る。これで大概のところはなんとかなった。大抵は確保されていないメモリにアクセスするだとかそんな理由だった。mallocでいくつの配列を確保したか、実体が代入されている箇所は正しいのか、そういった点を入念に、時には手元の雑紙に図示しながら検証していく。この作業ですべてのセグメンテーションエラーは消すことができた。
また、今までにないエラーを見ることもあった。端末にあんなにエラー表示が並んだのは初めての事だったので驚いたが、エラー表示を検索してみるとなんのことはない、ただのメモリリークだった。mallocで確保した領域を開放していないために２度目以降の実行時にエラーが起こっていた。こういう経験をすることで、ガベージコレクションの重要性を感じることができた。たしかに、GCがあるとないとではかなり違うだろう。
しかし何度やってもアロー演算子を使ってリストを移動する処理はなれない。
例）
node= &root
if (node->next != NULL)
node = node->next
（最初、nodeの場所をrootにセットし、その後node->nextの場所がNULLでなかったならnodeをnode->nextの場所へ移動するというもの。頂点のrootから順々に下へくだっていくというイメージ）
言っていることはわからなくもないのだが、しかし代入という操作が移動という操作につながる点がイマイチ納得 しきれていないようだ。そのため最後の課題はデータ構造として隣接行列と隣接リストのどちらで解いても良いという問題だったが、双方向グラフをリストで表現するのが面倒だったため隣接行列の方で解いた。リストに比べ、行列はただ単に対称行列を作ればよいだけなので双方向化するのが非常に楽に済んだ。
ポインタの移動やString型など、今回の課題はC言語の中でもややこしい部分を取り扱った課題のように感じる。その点pythonやらなんやらといった最近の、新しくて強力な言語であればここらへんの処理は適当に書いても上手くいってしまうだろう。便利ではあるが、メモリの理解という点に関しては微妙なところだろう。
今後また、C以外の言語でもダイクストラ法に挑戦してみようかと思う。
求められる要素は３つ、「リスト構造」と「String型」の習熟と「ダイクストラ法」の理解。周りの反応を聞いてみるとダイクストラ法がよくわからないまま、String型のやmallocの引き起こすセグメンテーションエラーに苦しんでいるようだ。
今回の課題は提出するソースが以前と比べ長くなるが、その分学生たちにはサンプルソースが与えられる。サンプルはデータ構造の作成やダイクストラ法に関する部分のみが抜けており、それ以外の型宣言や出力関数など大半の部分は既に与えられている。プログラムの核となる箇所以外、８割程度がサンプルソースに書かれていた。これを利用することで大幅な時間削減が得られる。その代わり書かれていたコードは非常に読みづらかった。無駄なfor文やif文もあったように思う。しかし大学が生徒に求めているものに意識を集中させるための措置と考えると有用であったのは確かだ。
この最短経路問題で僕が得た一番の経験と言えばやはりデバッグ作業だろう。ご多分に漏れず、僕もセグメンテーションエラーは何度もお目にかかることとなった。だがそうした時、エラー表示"check"を挟むことでエラー発生処理部分を特定し、原因を探る作業をすれば必ず解決できた。セグメンテーションエラーというのはポインタやメモリに関するエラーであるから、そのエラー行自体ないしエラー処理部分に関わる行を推測し、エラーの理由を探る。これで大概のところはなんとかなった。大抵は確保されていないメモリにアクセスするだとかそんな理由だった。mallocでいくつの配列を確保したか、実体が代入されている箇所は正しいのか、そういった点を入念に、時には手元の雑紙に図示しながら検証していく。この作業ですべてのセグメンテーションエラーは消すことができた。
また、今までにないエラーを見ることもあった。端末にあんなにエラー表示が並んだのは初めての事だったので驚いたが、エラー表示を検索してみるとなんのことはない、ただのメモリリークだった。mallocで確保した領域を開放していないために２度目以降の実行時にエラーが起こっていた。こういう経験をすることで、ガベージコレクションの重要性を感じることができた。たしかに、GCがあるとないとではかなり違うだろう。
しかし何度やってもアロー演算子を使ってリストを移動する処理はなれない。
例）
node= &root
if (node->next != NULL)
node = node->next
（最初、nodeの場所をrootにセットし、その後node->nextの場所がNULLでなかったならnodeをnode->nextの場所へ移動するというもの。頂点のrootから順々に下へくだっていくというイメージ）
言っていることはわからなくもないのだが、しかし代入という操作が移動という操作につながる点がイマイチ納得 しきれていないようだ。そのため最後の課題はデータ構造として隣接行列と隣接リストのどちらで解いても良いという問題だったが、双方向グラフをリストで表現するのが面倒だったため隣接行列の方で解いた。リストに比べ、行列はただ単に対称行列を作ればよいだけなので双方向化するのが非常に楽に済んだ。
ポインタの移動やString型など、今回の課題はC言語の中でもややこしい部分を取り扱った課題のように感じる。その点pythonやらなんやらといった最近の、新しくて強力な言語であればここらへんの処理は適当に書いても上手くいってしまうだろう。便利ではあるが、メモリの理解という点に関しては微妙なところだろう。
今後また、C以外の言語でもダイクストラ法に挑戦してみようかと思う。
