「抽象データ型」の編集履歴（バックアップ）一覧はこちら
「抽象データ型」(2019/01/07 (月) 21:42:34) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
データの扱い方についての諸観念について、ここで、もうちょっと補完しておくことにします。特に、いつもついでに言及されてきた「抽象データ型」という観念について、もう少し正確に書いておこうかと思います。きちんとやろうとすると本一冊分くらいにはなってしまう題材のようですが、まあ、ごく簡単に。複雑なデータ構造の使い方とか、得失とかにはふれません。また、コードも書きません。って、そういう話を、コードを交えてやるのが、「データ構造とアルゴリスム」とかいう学科の教科書そのものなんで、このページに教科書の一章分を書くなんて大変なことは、わたしにはできません。定評のある教科書を写してもしょうがないし(^^;;)。でも、まあ、汎用の知識ですから、よい教科書はいっぱいあるでしょう。もし後で実際に使う例を見つけられたら、コードも考えてみたいと思います。ここでは、表面を撫で撫で(^^;;)。
抽象データ型という言葉は、ここまでも何回かでてきました。データの並べ方(構造化)と処理手続がパックになったような考え方、これが抽象データ型という言葉で意味されているものだといえます。オブジェクト、というか、クラスという考えは、まさにこの「抽象データ型」という考えに適合しています。構造化されたデータの塊と、それに適合した処理手続であるメソッドのパッケージ化。
**アレイ(配列)もスタックも抽象データ型
でも、抽象データ型という考え方は、必ずしもクラスに限られるものではありません。実をいうと、ここまでにも、抽象データ型といえるものをいくつか説明してきました。アレイ(配列)も、スタックも、一種の抽象データ型といえるのです。
というのは、例えば、アレイの説明として、同じ幅のアイテムを縦列し、ポインタのジャンプでもって必要なデータアイテムに到達するというようなことを書いた記憶があります。アレイを、等幅データのメモリー上への縦列として実装するのは、まさにそのような簡単なポインタ計算によるデータの読み出し、あるいは上書きに適合したやりかたであるといえます。このアイテムを隣り合わせで並べていくというのが、アレイのデータ構造(データの構造化方法)であるということができます。そして、アイテムポインタ経由の高速なデータのアクセス(読み出しと上書き)というデータ処理と、アレイのデータ構造はパッケージ化されていると考えることができます。なので、こういったアレイのパターンを用いることは、抽象データ構造の一例と考えることができるわけです。
スタックは、先入後出しという規則を適用することによって、特にデータアイテムの追加/削除を効率化を図ったものです。この規則によって、アイテムの追加/削除にはトップアイテムの所在を管理するポインタだけで済むようになり、アイテムの追加/削除ごとに他のアイテムを移動して順番を詰めたりする必要がなくなるわけです。この観点から、スタックもまたデータ構造とそのアイテムの加除操作を結びつけた抽象データ型としてとらえることができます。
**最初の交通整理
ところで、Mopsや一般のForthのスタックは、1セル幅のアレイ風データ構造で実装されていますが、スタック一般がそうでなければならないわけではありません。例えば、いわゆるスタックフレームなどは、区々の幅の塊がつまれていくようになっています。また、各アイテムを隣り合わせで並置していくことも、スタックには必然ではありません。トップスタックを指すポインタが管理できて、先入後出しのデータ追加/削除をするようになっていれば、それはスタックといえるわけです。アレイは「配列」ということで、メモリー上のデータ配置にこだわった名前ですが、スタックは先入れ後出しという処理プロセスにこだわったもので、観点は少しずれていることにも注意してください。
これを言葉としてどのように整理するかです。これは要するに、アレイには、データ構造を示すものとしての意味と、抽象データ型を示すものとしての意味の、二つの意味があると考えればいいでしょう。メモリー上に隣り合わせで縦列された同じ幅で区画されている領域(ハイレベルには、同じ型のデータ格納領域)にデータを格納しておくというデータ構造としてのアレイと、その配置の仕方を利用して高速なデータアクセスを実現するという抽象データ型としてのアレイ、ということですね。Mops/Forthのスタックは現実にはデータ型としてアレイを利用していますが、スタックの概念は、データ型まで指定するわけではなく、先入後出という「構造化データの動的操作」に注目した本来的な抽象データ型概念である、ということになります。なんか、もうだいたいネタばれちゃいましたか？(^^;)。
>ええと、弁解です(^^;;)。アレイの定訳は「配列」なんですが、ここまで、大抵、カタカナで「アレイ」と書いてきました。「配列」はわかりやすい言葉なんで、そう書くべきなんでしょうが、この配列という言葉は、逆に一般的な言葉過ぎて、何の気なしに「配列する」なんて動詞風にも使うんで、文の中に埋もれてしまって、そこでコンピュータのデータ構造の配列の話をしているんだよ、という印がなくなっちゃう気がするんですね。なんか、そのまま読み過ごしちゃうというか。「アレイ」とカタカナで書くと、一応そこだけ目立つんで、自分としてはその方がいいかと思ってるんですが、人によっては、かえって分かりづらいかもしれませんね。すみません。でも、そういうことなので、「アレイ」で通したいと思います。
>ちなみに、「鉄アレイ」の「アレイ」は、このアレイじゃありませんよ。鉄アレイの方は、実は、漢字なんですよ、ええ。「亜鈴」。もとは「唖鈴」ですね。ダンベル(dumbbell)の意訳。つまり、Dumb(唖 )Bell(鈴)。きっと、教会とかで礼拝に使う、柄付きのベル見たいのがあって、それに形が似てたんでしょうね。なんか、日本の密教の道具にもありそう。で、音がしないのでdumb。いやあ一本取られた(^^;;)。ああ、語源の話は空想なんで、信用しないでください。漢字なのはホント。
**抽象データ型としてのリスト、一般名としてのリスト
抽象データ型としてのリスト(List)という観念があります。最古の関数型言語のLISPが、「全てはリストである」という措定の下に設計されているのは有名ですね。LISPはList Processorの略だとかナントカ。もっとも、この場合のリストは、データ構造としてのリストだったようで、データのメモリー上への配置の仕方を特定したもののようです。つまり、リストについても、アレイと同じように、抽象データ型の名前とデータ構造の名前との二つの用法があるわけです。さらに、もっと広くアレイなんかも含めた意味での抽象データ型の一般名としてリストという言い方もあります。こちらには別の名前(シーケンスとか)を与えているものもあるようです。データ構造としてのリストは、後で触れます。
まず、一般名としての広義のリストについて。"リスト(List)"を直訳すると「目録」とかそんな感じですか(ちなみに、"アイテム(Item)"は「項目」と訳せます。)。コンピュータでの概念としては、一列に並べられているものとして互いに関連づけられデータの集まり、というような程度でしょうか。ちょっと、まわりくどいな(^^;;)。観念的には、一列の長さが無限にあってもいいんでしょうが、現実的にはコンピュータは有限のデータしか扱えないわけですから、どこかで切れます。つまり、現実的にはサイズに何らかの人為的制限があります。記憶装置の容量限界までというのも含みますが。
すこし分析的にいうと、まず、複数のデータがあって、それらが関連づけられているんですね。で、その関連づけ方が、一列に並んでいるよ、といわんばかりの関連づけ方である、と(^^;;)。いや、「いわんばかり」じゃなくて、一列にならんでいるんですが。ともかく、「一列に並んでいる」とは、つまり、線状に並んでいるということ、つまり、両端(あれば)以外のアイテムについては左右(上下でもいいけど)両隣関係がそれぞれ1対1で決まっていて、その関係経由でもって全アイテムデータがつながっているということですか。「端がない」リストというのは、つまり、環状に両端がつながっている、ということですね。これもリスト。
じゃあ「隣」関係ってのは何だ、となりますが、これには大別して二つの実現方法があります。
**アレイデータ構造でのリストの実現
ひとつは、まさに文字通り、メモリー上に隣り合わせで並べるという方法があります。つまり、アレイデータ構造。だから、アレイというのはリストの実装方法のひとつなわけです。抽象データ型としていうと、アレイはリストの一特殊類型という関係にあります。ある特定の動作の効率性に特化したのがアレイですね。
アレイは、「特化してる」といいましたが、じゃあ、一般的にはどうなんだということですが、抽象データ型としてリストを考えた場合、その動作としては、リスト内のデータの検索と読み出し/上書き(修正)という、いわば静的な動作と、リストへの新規項目の追加、あるいは逆に既存項目の削除、という動的な動作が考えられます。「静的」というのは、リスト長の変更を伴わないということです。もちろんアレイだってリスト長を変更することができないわけではありません。ただ、アレイデータ構造だと、途中にアイテムを追加したいときには、アイテムの追加操作だけでなく、それよりも後ろにあるデータを全部一個ずつ後ろにずらさなければなりません。また、途中のアイテムを取り除くには、そこより後ろのデータを全部一個ずつ前に詰めないといけません。アイテム数がたくさんある場合には、結構な手間になります。そこで、アイテムの追加/削除はほとんどしないことにして、静的な動作に特化したのが抽象データ型としてのアレイ、ということなわけです。
ただ、すぐに分かるように、アイテムを移動して、列を詰めたり、場所を空けたりする必要があるのは、列の中途に何かしたいときだけです。列の端だけを考えるなら、追加/削除のために他のアイテムを移動させる必要はありません。この事実を利用して、高速な加除を可能にしたもののひとつが、スタックなのです。
**抽象データ型としてのスタック
抽象データ型としてのスタック(stack)もまた、アイテムの追加/削除という動的な操作に特化したリストということがいえます。データ構造としてはアレイである必然性はありませんが、アレイデータ構造であることと先入後出し操作に限定して効率することとは密接に結びついています。端っこだけ操作するという決まりは、必ずしもアレイデータ構造のリストでなくても、加除操作の効率化をもたらします。ですが、より柔軟な、つまり、複雑な機構を伴ったデータ構造には、それ相応の超過負担があるわけで、アレイデータ構造のようにシンプルであれば、それだけより効率化が図れるといえます。つまり、いってしまえば、どうせスタックにするのならデータ構造にわざわざ複雑な機構を使って柔軟性を与える価値はあまりないといえます。
**抽象データ型としてのキュー
端だけ操作することに注目したもうひとつの抽象データ型として、キュー(queue)があります。定訳は「待ち行列」。これは、先入先出(FIFO -- First-In First-Out)法、つまり、突っ込んだ順にしか取り出せないという動作制限をつけて効率化を図った抽象データ構造です。横1列に並べたと考えると、付け足すときは右端、取り出すのは左端から、と決めておけばいいわけです。そして、両端のポインタデータを維持しておけばOKです。使っていくうちにどんどん右に移動していっちゃいますが、限界を設定しておいて、そこに当たったら、突っ込み先のポインタを、ポンと左端に戻せばいいわけです。で、左端から詰めていく。取り出す方も、限界に達したら左端に飛ばす。そうすれば、全体が溢れない限りいつまででも使えますね。
| |BGCOLOR(yellowgreen):使用済み|BGCOLOR(pink):アイテム|BGCOLOR(pink):アイテム|BGCOLOR(pink):アイテム|BGCOLOR(yellow):入力待ち| |
↑ ↑
取出口ポインタ 新規取入口
キューは昔やって来た古いものから順に使っていくわけです。コンピュータでこれがよく使われるのは、イベント処理ですね。つまり、マウスクリックとか、キーボードのタイピングとかすると、その信号が順々にコンピュータに送られていくわけですが、これは、ソフトウェアとしては、イベントとかメッセージとか呼ばれるデータ構造に抽象化されて、キューに突っ込まれるわけです。で、その処理ができる状態になったら一個ずつ順番に処理していくということになります。
ときどき、バッファーという言葉を聞きませんか？キューは、この「バッファー」という言葉の意味に、まったくピタリと適合した動作をします。というか、キューというのはアルゴリスムの観点からの名前、バッファーはハードウエアよりの名前で、働きとしては同じものといっていいような気もしますが。
スタックにしても、キューにしても、アレイデータ構造にする以上、人為的に限界を設定してあるわけで、その限界を超えてアイテムを突っ込むことのないようにしなければなりません。限界を超えることをオーバーフローといいます。まあ、溢れ出し、ですね。逆に、もうアイテムがないのに取り出そうとするのもいけません。それはアンダーフローといいます。
キューもスタックも、その前提からして、そこにデータを溜め込んでおいて使うというものではないように思われます。当座しのぎに取りあえずおいておく場所、というか。この辺は、他のアレイやリストとは違います。「スタックにアイテムをたくさん溜め込むのはよくない」というForth系でよく聞く主張は、その抽象データ型の本質からも正当化できるわけですね。もっとも、加除操作を止めてしまえばただのアレイですが。
キューにもスタックにもバリエーションはあり得ます。例えば、キューの順番でも、単純に入ってきた順序ではなくて、優先順位があって順番が破られ得るものもあります。また、Mops/Forthのスタック操作子は、DROPとDUP以外はトップアイテム以外にもアクセスするので、厳格なスタックの用法には反するといえます。それで、スタック操作には批判も多いのでしょう。もっとも、アレイデータ構造である以上、奥の方のアイテムの読み出しについては効率がいいはずで、効率性の点に関していえば、PICK系(overも含む)は批判される謂れは無いともいえますね。ただ、スタックを操作するのにもう一個スタックアイテムを積むというのは、不格好といえば不格好ですが(自分としてはこの点が引っ掛かってPICKを避けてます(^^;;)。つーか、必要にならないように組めよ、ってことなんですが。)。
「待ち行列」についてなんですが、分かってみれば「なるほど」の訳です。って、もともとが何かを待ってる人の行列って意味のことばが、コンピュータに転用されたんでしょう。でも、始めてこの言葉を見たときには、何のことか全然わかりませんでしたよ(^^;;)。むか～し、よく行ってた本屋に、「応用待ち行列」(今もでてますかね)とかいう題の本があって、そのタイトルだけながめて、応用されるのを待ってる公式かなんか(自然科学系の棚にあったから)が行列をつくってるのをイメージしてましたよ(^^;;)。「応用を待ってるぞ、なんて、妙にキャッチーな題名の公式集だな。受験参考書か？」なんて(^^;;;)。あれがコンピュータアルゴリズムの本だったなんてねえ(遠い目)。
キューってのは、ほら、玉突きの棒もキューですね(スペル違うか？でも意味合いは同じでしょう。)。ギュッと後ろを押すと前からでてくる「ところてん式」(って、ところてん製造機って見たこと無いんですがね。)。あるいは、上からクリームをいれて絞り出してケーキを装飾するやつ(名前忘れた)。<もうぼろぼろだな(||_ _)。イメージはそんな感じ。ともかく、「待ち行列」って言葉にはそういうトラウマがあるので、なんか言葉はあまり使いたくない。すみません。
**データ構造としてのリスト
データ構造としてのリストは、データ構造としてのアレイに対抗するものといえますが、そこでは「相隣関係」が抽象化されています。アレイではまさにメモリー上の隣、なわけですが、リストでは次のアイテムがあるメモリー上の場所を指すポインタをデータと一緒に保管しておくのです。次のアイテムのポインタを保管する分だけ余分なメモリーを使うわけですが、その分だけ柔軟性が得られます。そのことによって、各アイテムはメモリー上のどこにあってもよいことになるからです。端には無効なポインタ(大抵は0)を詰めておくことも、先頭のアイテムのアドレスを入れて環にすることもできます。
次のアイテムのポインタだけを保存しておく場合には、頭から後ろの方向には辿ることができても、逆向きには進むことはできません。そこで、前のアイテムのポインタも保存しておけば、逆向きに辿ることもできます。そのようなものは、双方向リストと呼ぶようです。
#image(liststruct.jpg)
**リストデータ構造の利点 -- 柔軟性
データ構造としてのリストのアレイに対する具体的利点は、第一には、端以外のアイテムの追加/削除が軽くなることです。一方向リストでいうと、途中にアイテムを追加する場合でも、挿入する場所のひとつ手前のアイテムに付属している次アイテムのポインタデータを取って、新しいアイテムの次アイテムのポインタデータとして格納し、続いて、ひとつ手前のアイテムの次アイテムポインタをその新アイテムのポインタに付け替えればいいわけです。双方向だとふたつ分ありますが、ともかく、ポインタデータを付け替えるだけでよく、後ろにあるアイテムの移動は必要ありません。その結果、アイテム数が増えても、アイテム追加操作自体には変動はありません。
#image(addlistitem.jpg)
アイテムの削除のときには、削除するアイテムが保有している次アイテムのポインタを、自分の前のアイテムの次アイテムポインタデータに格納するだけで縁が切れます。
#image(dellistitem.jpg)
第二には、リスト長の限界が事実上無くなるという利点もあります。アレイデータ構造では、アイテムを一列に並べなければならないため、長いリストのためには、広い、連続したメモリー領域を確保しておく必要があり、いきおい、どこかに明確に限界を設定する必要があります。ところが、リストデータ構造では、アイテム自体は、メモリー上の何処にあってもよく、新規アイテムのためには、メモリーにその分の隙間があればそこに突っ込んでおけば充分です。「相隣関係」は、ポインタによる参照だけで定めることができるからです。動的で柔軟性の高いデータ構造であるといえます。
**抽象データ型としての狭義のリスト
上のような見方は、既に、リストデータ構造を、アイテム加除の効率化に注目した抽象データ型としてとらえています。抽象データ型であることに着目するときは狭義のリストということにします。やっぱり、抽象的なリスト概念には別の名前をつけるべきですね。
**リストデータ構造の苦手 -- アイテム探索
さて、長所があれば短所もあるものです。各アイテムがメモリーの何処にあるのか予めはわからないのですから、「何項目」と指定して、すぐにそこに到達することはできません。基本は、頭から、ポインタを辿りながら、項目を数えていって、目的地に到達したところで初めて、必要なデータにアクセスできます。つまり、探索など、各アイテムデータへのアクセスは遅くなるのです。挿入/削除のときにも、どこに挿入/どのアイテムを削除するかを決めるのに場所を探索するとすれば同じことです。
そのようなわけで、リストデータ構造を基礎とする抽象データ型としての狭義のリストは、探索の効率性は捨てて、アイテムの自由な追加削除という操作に注目したものといえます。しかし考えてみると、データアクセスにしても、リストの全体に一様な処理を施したい場合には、アレイデータ構造と比較して特に遅いことはありません(nに比例)。すると、リストの全項目への繰り返し操作(Iteration)もまた、抽象データ型としてのリストが得意な動作といえるでしょう。これは、一列に整列されているということの効果であると考えられます。
**リストデータ構造とメモリ
あと、「弱点」として、もうひとつ挙げておきましょう。これは、リストからのアイテムの削除の図から知ることができます。もっとも、これは柔軟性の裏返しであって、必ずしも弱点ではないともいえますが。
リストアイテムを削除した場合、削除されたアイテムは孤立してしまいます。このアイテムを参照しているアイテムがなくなってしまうからです。この場合、この削除されたアイテムに到達する方法が原理的には失われてしまいます。もはや、このアイテムは要らなくなってしまったわけですが、それでも、人知れずメモリー領域を占拠し続けます。このような状態は、メモリーリークと呼ばれ、非常に見つけにくいバグのひとつです。普通のコンピュータなら、小さいリーク一個で困ることはありませんが、リストへの項目の追加/削除を繰り返しているうちに、要らないデータを格納していながら、他の目的には転用できないメモリー領域がどんどん増大して、システムを圧迫し始めます。
PASCALやC、C++といった「低級」言語では、アイテムを削除するときに、削除されたアイテムを見失う前に、それがあるメモリー領域を解放しないといけません。そうすると、その領域はシステムに返却され、その領域の再利用が可能となります。メモリー領域解放の機能はシステムライブラリ関数として提供されていますから、「複雑な参照関係がない」という前提の下では、これ自体はプログラミング上では大した手間ではありません。
**傍論：ガーベージコレクタ
少し話はそれてきますが、このようなリストアイテム削除を取り巻く状況は、LISPが大昔からガーベージコレクタ(Garbage Collector:ゴミ集め)機構を備えていた理由を説明するものとなっています。関数型言語であるLISPでは、全てのデータ処理は、値を返すことに専念するものである関数によっておこなわれなければなりません。「メモリーを解放する」などという、計算でもない、関数でもない、機械の特殊性にかかわる低水準のことをプログラムの内容として書き込むことは許されないことだったわけです。そういう「醜い」操作は隠してしまいたい。そのようなわけで、リストから削除され、もう必要の無い項目は、取りあえずはそのままにしておくものの、定期的に自動的にそれを探し出してメモリー領域を解放し再利用可能にするという機構が、開発環境に漏れなくついてきたのです。リストから切り離されても、その開発環境の中では、その項目への参照は保持しておくわけですね。ガーベージコレクトのときのガーベージを探し出す、あるいは印をつける技巧(アルゴリズム)は、いくつか知られているようです。もちろん、速やかにゴミを発見して解放するためのアルゴリズムの工夫です。古いLISPでは、ガーベージコレクトのタイミングで、処理が、クククッと遅くなったりしたそうです。今では高級なプログラミング言語にはガーベージコレクトは不可欠の補助機構と見なされており、複雑な参照関係が張り巡らされた柔軟なデータ構造の処理とともに、うんこの後にケツも拭かず(洗わず)放置するプログラミング習慣も支援しています(^^;;)。
**もっと複雑なデータ構造
アレイデータ構造は、複雑にしようとしても限度がありますね。でも、ポインタで関連を付けるデータ構造、つまり、リストデータ構造の応用としては、いくらでも複雑な関連がつくれそうです。アイテムを一列に並べる必要は、全くありませんからね。一般的には、データアイテムを頂点(vertexあるいはnode)で表し、それらの間の参照関係を辺(edge -- 図としては向きがあれば矢印で表す)表すことによって、グラフとして表現できるデータ構造にまで複雑化することができます。
そういった変種の中でも比較的簡単で実用的なのは、Tree(ツリー)構造ですね。「木」とか訳されますが、「木」といわれて、木材というか材木というか、素材としての木を思い浮かべてしまう私は、いかにも日本人なんですかね。「ツリー」とカタカナで書くと、クリスマスツリーという連想経由で、木が生えている状態を想像しますね。やっぱ、ど日本人だわ。まあ、このツリー構造というのは、要は樹形図構造ということなんですが。慣習上、根元を上に、枝の伸びる方向を下に描くようです。「逆木」ですねえ。
ツリーの定義としては、グラフ理論の用語を使うのが普通です。頂点と辺からなる、というわけですが、頂点はアイテム、辺はアイテム間のポインタによる参照関係と思えばいいわけです。ポインタデータを保有している頂点(アイテム)を「親」、そのポインタで参照されている頂点(アイテム)を「子」と呼ぶことがあります。ツリー構造では、どの頂点も、ふたつ以上の親を持つことはできません。これに対して、子は大抵複数になります。データ構造としては根(root)のあるツリーだけで取りあえず充分です。「根」というのは、ひとつの頂点であって、何処からも参照されておらず、逆にそこから参照をたどれば、全ての頂点に至ることができるもののことです。どんなツリーにも根はひとつだけあると考えます。ツリーの定義は再帰的におこなわれます。まず、頂点ひとつだけのものも、ツリーの一種と認めます。次に、ひとつの頂点と、n個のツリーがあって、各ツリーの根に、その頂点から辺をおろしたものもツリーと認めます。これで、ツリーは定義できます。ひとつの頂点を適当に取って、そこからたどることのできる頂点と辺を合わせたものもツリー構造になりますが、これはもとのツリーの部分ツリーといいます。
なぜツリー構造が考えられるに至るのか、というと、リスト構造のアイテム探索が苦手であるという特性を克服しようとしたわけです。リスト構造では、アイテムの探索には、基本的には頭からひとつずつたどっていくしかないので、アイテムの個数nに比例して、探索の手間が増えてしまいます。これに対して、ツリー構造にしておけば、枝分かれしている分だけ、探索していく道が短くなります。大体、nが増えるときには、規模としては平均的にlog nに比例する程度にしか、探索の手間は増大しません。ちなみに、コンピュータ関係でlog nと書くときは、その底は2だそうです。つまり、log2nということですね。ビットで測るってことでしょうか。
基本的なものとしては、Binary Tree(二分枝木)というのと、Balanced Tree (平衡木)くらいは簡単にふれておきましょう。
Binary Treeはその名の通り、枝わかれ(子)が二本(以下)のツリーです。必ず二つというのではなくて、二つ以下ということです。結果として、枝が一本きりのリスト構造も、Binary Treeに属するということになってしまいます。そのため、ツリーの作り方によっては、探索の効率化が望めなくなってしまいます。一番いいのは、できるだけきれいに二分枝を張ることです。そうすれば、階層の深さ、つまり、根から枝の末端(「葉」(leaf)といいます)に至るまでの中間のアイテム数が、全アイテム数nに対してlog n程度になることがわかるでしょう。
という話で気付くかもしれませんが、Binary Treeという名前は、そのデータ構造に着目した名前ということになります。抽象データ型としてみると、アイテムの探索とデータアクセスの効率化です。アレイと比べると劣りますが、狭義のリストよりは性能が上です。
アイテムの加除も、ポインタ参照によるリストデータ構造の応用ですから、ポインタの付け替えだけで済み、効率は悪くありません。ツリーへのアイテムの追加は、何らかの方法でアイテムに順番をつけておいて、その順番にしたがって挿入箇所を決めることが前提とされています。いつもお尻だけを操作するというのでもいいのでしょうが。ただ、一般的には、追加削除を繰り返すうち、枝分かれが減ってリスト構造に近づいてしまい、探索効率が落ちてしまう危険があります。この点を回避しようとするのがBalanced Treeなんですが、むしろ、Binary Treeは、そういった配慮をしない二分枝木であるという形で、Balanced Tree区別されるに過ぎません。
平衡木(Balanced Tree)の「平衡(Balanced)」というのは、枝分かれを平均にして、枝の長さが偏らないように、かつツリー階層の深さができるだけ浅くなるように配慮しつつ、アイテムの追加削除をおこなうという意味です。探索の効率にかかわるのは結局、ツリー階層の深さであることは明らかですね。
その「平衡」は、枝分かれの個数に、上限だけでなく、下限も設定することで実現されます。メモリー上のデータ構造として使い道がありそうと考えられているものに、2-3木というのがあります。これは、枝分かれは、最大3、最低でも2に維持する平衡木です。アイテムの追加とか削除の結果、3本以上の枝わかれが必要になりそうなとき、あるいは、枝が一本に減ってしまいそうなときは、新しく分岐点をつくったり、隣の分岐と合併したりして、枝数を調整します。そして最終的には、根から葉までの距離が全て等しくなるようにします。そうすれば、アイテムの追加/削除を繰り返しても、探索の効率が極端に落ちてしまう構造に変改することを防ぐことができるわけです。
枝のすげ替えによる調整は、ひとつの作業自体はそれなりに手間がかかりますが、全アイテム数nの増大のときには、その割には負担は増えていかないということが知られています(log nの規模)。
2-3木を一般化したものとしてB-Treeという概念があります。これは、最多分枝数をm(3以上)とし、最少分枝数をmの半分より大きい最少の整数として、深さを均一にしたものです。m=3で2-3木になることは容易にわかりますね。ただ、一般のB-Treeは、メモリー上のデータ構造よりも、ファイルとかそういう外部記憶装置に保管するデータ構造に向いているとされています。
>抽象データ型について書こうかと思ったので、公共の図書館からその方面の本を借りて、読んでみました。この種の本を読む(多くは立ち読み...すみません)といつも思うんですが、退屈です。いや、それなりに興味深いことは書いてあるし、大抵はプログラム例が載っていて、本来ならそれなりに面白いはずなんですけど、どうも...。いや著者が悪いとかいうつもりは無いです。多分、汎用アルゴリスム一般なんてのには、普通は関心が向かないからじゃないかと思います(もちろん、人による)。つまり、なにか自分が面白いと思うことをするプログラムを書いていて、その途中で何かうまい手順が必要になったというなら、きっと目を剥いて読むんじゃないでしょうかね。
>喩えていうなら、釘と金槌、のこぎりとかんなでもって木造建築をつくるのはおもしろいとしても、釘や金槌のことばかり延々説明されても、という感じですか。もっとも、釘の打ち方やノコのひきかたをきちんと習得していないと、まともな木造建築などできそうにない、というのも確かなことではあります。
>現実問題、「アルゴリズムとデータ構造」の教科書レベルででてくるアルゴリズムなんてのは、大抵の開発環境には、ライブラリとしてついてきます。ですから、普通のプログラミングでは、そのアルゴリスムを自分で実装するなんて必要は無い。まあ、上の喩えでいえば、釘や金槌などから自作することはないっ、ってことですか。でも、使い方は知らないと、建築はできない。ので、アルゴリズムの名前と、その得失を憶える、というところに集中するんでしょうね。でも、それじゃあ、達成感はあまりない。そんなわけで、入門者にはとりあえずいくつか金槌とか釘とかつくってみましょう、と勧めるわけですね。作ってみて初めて得心がいく、って場合もありますし。それに喜びを見いだせる人はそれでいいんですがねえ。
>Forth系でも、商品版ではついてくるんじゃないかと思います。ライブラリ。Mopsでは、その手のライブラリは薄いですね。リストとしては、ポインタリストとハンドルリストがありますが、どっちも上で説明したような、前後を参照した線形のリストじゃないです(アイテム探索速度はO(n0)てか、O(1)です。ポインタ/ハンドルを伸縮するアレイ(追加はいつもお尻に)で管理してますから。だから、Mopsマニュアルにかいてあるんですね、「アイテムの削除をあまり頻繁にはしないということを前提にしている」って。)。一応、Mopsでも内部的には線形のリストも使われてます。単純なデータ構造なんて、プログラムに必要になったらつくりゃいいんで、理屈がわかりゃあ大した手間じゃないです(つくれないのは、理屈が充分にわかっていないからですね)。というか、ツリーとかなんか、シミュレーション以外にどうしても必要って局面なんかあるんですかね。探索ならハッシュでいいわけだし。構文解析とか、かな？まあ、よくわかりません。
>自分としては「茶道」主義だと思いますね、Mopsは。生け花とか、山水画とか、造園とか、今じゃあ分かれてますけど、そういうのはみんな、お茶室を演出する技巧として茶道から派生したんですよね。茶碗を焼くところから入るんですからね、お茶は。お客様をもてなす心を突き詰めれば、ひとつだにゆるがせにはできない...って、やりすぎだって。ま、自作じゃなくても、良いものを見極めて使えば良い、ということですがね。そういえば、Forthの心は禅の心なんて話もありますが、喫茶の習慣は禅僧から始まったんですよね。ん～、商品化というのは心を喪うことなのでしょうかね(^^;;)。ただ、「お客様をもてなす心(一期一会)」に当たるMops/Forthプログラミングの求心力って、何でしょうねえ ... ？
----
< [[前へ>再帰（Recursion）]] [[次へ>ソート（整列）]] >
[[目次へ>プログラミングへの道]]
[[トップページへ>トップページ]]
----
データの扱い方についての諸観念について、ここで、もうちょっと補完しておくことにします。特に、いつもついでに言及されてきた「抽象データ型」という観念について、もう少し正確に書いておこうかと思います。きちんとやろうとすると本一冊分くらいにはなってしまう題材のようですが、まあ、ごく簡単に。複雑なデータ構造の使い方とか、得失とかにはふれません。また、コードも書きません。って、そういう話を、コードを交えてやるのが、「データ構造とアルゴリスム」とかいう学科の教科書そのものなんで、このページに教科書の一章分を書くなんて大変なことは、わたしにはできません。定評のある教科書を写してもしょうがないし(^^;;)。でも、まあ、汎用の知識ですから、よい教科書はいっぱいあるでしょう。もし後で実際に使う例を見つけられたら、コードも考えてみたいと思います。ここでは、表面を撫で撫で(^^;;)。
抽象データ型という言葉は、ここまでも何回かでてきました。データの並べ方(構造化)と処理手続がパックになったような考え方、これが抽象データ型という言葉で意味されているものだといえます。オブジェクト、というか、クラスという考えは、まさにこの「抽象データ型」という考えに適合しています。構造化された[[データの塊]]と、それに適合した処理手続であるメソッドのパッケージ化。
**アレイ(配列)もスタックも抽象データ型
でも、抽象データ型という考え方は、必ずしもクラスに限られるものではありません。実をいうと、ここまでにも、抽象データ型といえるものをいくつか説明してきました。アレイ(配列)も、スタックも、一種の抽象データ型といえるのです。
というのは、例えば、アレイの説明として、同じ幅のアイテムを縦列し、ポインタのジャンプでもって必要なデータアイテムに到達するというようなことを書いた記憶があります。アレイを、等幅データのメモリー上への縦列として実装するのは、まさにそのような簡単なポインタ計算によるデータの読み出し、あるいは上書きに適合したやりかたであるといえます。このアイテムを隣り合わせで並べていくというのが、アレイのデータ構造(データの構造化方法)であるということができます。そして、アイテムポインタ経由の高速なデータのアクセス(読み出しと上書き)というデータ処理と、アレイのデータ構造はパッケージ化されていると考えることができます。なので、こういったアレイのパターンを用いることは、抽象データ構造の一例と考えることができるわけです。
スタックは、先入後出しという規則を適用することによって、特にデータアイテムの追加/削除を効率化を図ったものです。この規則によって、アイテムの追加/削除にはトップアイテムの所在を管理するポインタだけで済むようになり、アイテムの追加/削除ごとに他のアイテムを移動して順番を詰めたりする必要がなくなるわけです。この観点から、スタックもまたデータ構造とそのアイテムの加除操作を結びつけた抽象データ型としてとらえることができます。
**最初の交通整理
ところで、Mopsや一般のForthのスタックは、1セル幅のアレイ風データ構造で実装されていますが、スタック一般がそうでなければならないわけではありません。例えば、いわゆるスタックフレームなどは、区々の幅の塊がつまれていくようになっています。また、各アイテムを隣り合わせで並置していくことも、スタックには必然ではありません。トップスタックを指すポインタが管理できて、先入後出しのデータ追加/削除をするようになっていれば、それはスタックといえるわけです。アレイは「配列」ということで、メモリー上のデータ配置にこだわった名前ですが、スタックは先入れ後出しという処理プロセスにこだわったもので、観点は少しずれていることにも注意してください。
これを言葉としてどのように整理するかです。これは要するに、アレイには、データ構造を示すものとしての意味と、抽象データ型を示すものとしての意味の、二つの意味があると考えればいいでしょう。メモリー上に隣り合わせで縦列された同じ幅で区画されている領域(ハイレベルには、同じ型のデータ格納領域)にデータを格納しておくというデータ構造としてのアレイと、その配置の仕方を利用して高速なデータアクセスを実現するという抽象データ型としてのアレイ、ということですね。Mops/Forthのスタックは現実にはデータ型としてアレイを利用していますが、スタックの概念は、データ型まで指定するわけではなく、先入後出という「構造化データの動的操作」に注目した本来的な抽象データ型概念である、ということになります。なんか、もうだいたいネタばれちゃいましたか？(^^;)。
>ええと、弁解です(^^;;)。アレイの定訳は「配列」なんですが、ここまで、大抵、カタカナで「アレイ」と書いてきました。「配列」はわかりやすい言葉なんで、そう書くべきなんでしょうが、この配列という言葉は、逆に一般的な言葉過ぎて、何の気なしに「配列する」なんて動詞風にも使うんで、文の中に埋もれてしまって、そこでコンピュータのデータ構造の配列の話をしているんだよ、という印がなくなっちゃう気がするんですね。なんか、そのまま読み過ごしちゃうというか。「アレイ」とカタカナで書くと、一応そこだけ目立つんで、自分としてはその方がいいかと思ってるんですが、人によっては、かえって分かりづらいかもしれませんね。すみません。でも、そういうことなので、「アレイ」で通したいと思います。
>ちなみに、「鉄アレイ」の「アレイ」は、このアレイじゃありませんよ。鉄アレイの方は、実は、漢字なんですよ、ええ。「亜鈴」。もとは「唖鈴」ですね。ダンベル(dumbbell)の意訳。つまり、Dumb(唖 )Bell(鈴)。きっと、教会とかで礼拝に使う、柄付きのベル見たいのがあって、それに形が似てたんでしょうね。なんか、日本の密教の道具にもありそう。で、音がしないのでdumb。いやあ一本取られた(^^;;)。ああ、語源の話は空想なんで、信用しないでください。漢字なのはホント。
**抽象データ型としてのリスト、一般名としてのリスト
抽象データ型としてのリスト(List)という観念があります。最古の関数型言語のLISPが、「全てはリストである」という措定の下に設計されているのは有名ですね。LISPはList Processorの略だとかナントカ。もっとも、この場合のリストは、データ構造としてのリストだったようで、データのメモリー上への配置の仕方を特定したもののようです。つまり、リストについても、アレイと同じように、抽象データ型の名前とデータ構造の名前との二つの用法があるわけです。さらに、もっと広くアレイなんかも含めた意味での抽象データ型の一般名としてリストという言い方もあります。こちらには別の名前(シーケンスとか)を与えているものもあるようです。データ構造としてのリストは、後で触れます。
まず、一般名としての広義のリストについて。"リスト(List)"を直訳すると「目録」とかそんな感じですか(ちなみに、"アイテム(Item)"は「項目」と訳せます。)。コンピュータでの概念としては、一列に並べられているものとして互いに関連づけられデータの集まり、というような程度でしょうか。ちょっと、まわりくどいな(^^;;)。観念的には、一列の長さが無限にあってもいいんでしょうが、現実的にはコンピュータは有限のデータしか扱えないわけですから、どこかで切れます。つまり、現実的にはサイズに何らかの人為的制限があります。記憶装置の容量限界までというのも含みますが。
すこし分析的にいうと、まず、複数のデータがあって、それらが関連づけられているんですね。で、その関連づけ方が、一列に並んでいるよ、といわんばかりの関連づけ方である、と(^^;;)。いや、「いわんばかり」じゃなくて、一列にならんでいるんですが。ともかく、「一列に並んでいる」とは、つまり、線状に並んでいるということ、つまり、両端(あれば)以外のアイテムについては左右(上下でもいいけど)両隣関係がそれぞれ1対1で決まっていて、その関係経由でもって全アイテムデータがつながっているということですか。「端がない」リストというのは、つまり、環状に両端がつながっている、ということですね。これもリスト。
じゃあ「隣」関係ってのは何だ、となりますが、これには大別して二つの実現方法があります。
**アレイデータ構造でのリストの実現
ひとつは、まさに文字通り、メモリー上に隣り合わせで並べるという方法があります。つまり、アレイデータ構造。だから、アレイというのはリストの実装方法のひとつなわけです。抽象データ型としていうと、アレイはリストの一特殊類型という関係にあります。ある特定の動作の効率性に特化したのがアレイですね。
アレイは、「特化してる」といいましたが、じゃあ、一般的にはどうなんだということですが、抽象データ型としてリストを考えた場合、その動作としては、リスト内のデータの検索と読み出し/上書き(修正)という、いわば静的な動作と、リストへの新規項目の追加、あるいは逆に既存項目の削除、という動的な動作が考えられます。「静的」というのは、リスト長の変更を伴わないということです。もちろんアレイだってリスト長を変更することができないわけではありません。ただ、アレイデータ構造だと、途中にアイテムを追加したいときには、アイテムの追加操作だけでなく、それよりも後ろにあるデータを全部一個ずつ後ろにずらさなければなりません。また、途中のアイテムを取り除くには、そこより後ろのデータを全部一個ずつ前に詰めないといけません。アイテム数がたくさんある場合には、結構な手間になります。そこで、アイテムの追加/削除はほとんどしないことにして、静的な動作に特化したのが抽象データ型としてのアレイ、ということなわけです。
ただ、すぐに分かるように、アイテムを移動して、列を詰めたり、場所を空けたりする必要があるのは、列の中途に何かしたいときだけです。列の端だけを考えるなら、追加/削除のために他のアイテムを移動させる必要はありません。この事実を利用して、高速な加除を可能にしたもののひとつが、スタックなのです。
**抽象データ型としてのスタック
抽象データ型としてのスタック(stack)もまた、アイテムの追加/削除という動的な操作に特化したリストということがいえます。データ構造としてはアレイである必然性はありませんが、アレイデータ構造であることと先入後出し操作に限定して効率することとは密接に結びついています。端っこだけ操作するという決まりは、必ずしもアレイデータ構造のリストでなくても、加除操作の効率化をもたらします。ですが、より柔軟な、つまり、複雑な機構を伴ったデータ構造には、それ相応の超過負担があるわけで、アレイデータ構造のようにシンプルであれば、それだけより効率化が図れるといえます。つまり、いってしまえば、どうせスタックにするのならデータ構造にわざわざ複雑な機構を使って柔軟性を与える価値はあまりないといえます。
**抽象データ型としてのキュー
端だけ操作することに注目したもうひとつの抽象データ型として、キュー(queue)があります。定訳は「待ち行列」。これは、先入先出(FIFO -- First-In First-Out)法、つまり、突っ込んだ順にしか取り出せないという動作制限をつけて効率化を図った抽象データ構造です。横1列に並べたと考えると、付け足すときは右端、取り出すのは左端から、と決めておけばいいわけです。そして、両端のポインタデータを維持しておけばOKです。使っていくうちにどんどん右に移動していっちゃいますが、限界を設定しておいて、そこに当たったら、突っ込み先のポインタを、ポンと左端に戻せばいいわけです。で、左端から詰めていく。取り出す方も、限界に達したら左端に飛ばす。そうすれば、全体が溢れない限りいつまででも使えますね。
| |BGCOLOR(yellowgreen):使用済み|BGCOLOR(pink):アイテム|BGCOLOR(pink):アイテム|BGCOLOR(pink):アイテム|BGCOLOR(yellow):入力待ち| |
↑ ↑
取出口ポインタ 新規取入口
キューは昔やって来た古いものから順に使っていくわけです。コンピュータでこれがよく使われるのは、イベント処理ですね。つまり、マウスクリックとか、キーボードのタイピングとかすると、その信号が順々にコンピュータに送られていくわけですが、これは、ソフトウェアとしては、イベントとかメッセージとか呼ばれるデータ構造に抽象化されて、キューに突っ込まれるわけです。で、その処理ができる状態になったら一個ずつ順番に処理していくということになります。
ときどき、バッファーという言葉を聞きませんか？キューは、この「バッファー」という言葉の意味に、まったくピタリと適合した動作をします。というか、キューというのはアルゴリスムの観点からの名前、バッファーはハードウエアよりの名前で、働きとしては同じものといっていいような気もしますが。
スタックにしても、キューにしても、アレイデータ構造にする以上、人為的に限界を設定してあるわけで、その限界を超えてアイテムを突っ込むことのないようにしなければなりません。限界を超えることをオーバーフローといいます。まあ、溢れ出し、ですね。逆に、もうアイテムがないのに取り出そうとするのもいけません。それはアンダーフローといいます。
キューもスタックも、その前提からして、そこにデータを溜め込んでおいて使うというものではないように思われます。当座しのぎに取りあえずおいておく場所、というか。この辺は、他のアレイやリストとは違います。「スタックにアイテムをたくさん溜め込むのはよくない」というForth系でよく聞く主張は、その抽象データ型の本質からも正当化できるわけですね。もっとも、加除操作を止めてしまえばただのアレイですが。
キューにもスタックにもバリエーションはあり得ます。例えば、キューの順番でも、単純に入ってきた順序ではなくて、優先順位があって順番が破られ得るものもあります。また、Mops/Forthの[[スタック操作子]]は、DROPとDUP以外はトップアイテム以外にもアクセスするので、厳格なスタックの用法には反するといえます。それで、スタック操作には批判も多いのでしょう。もっとも、アレイデータ構造である以上、奥の方のアイテムの読み出しについては効率がいいはずで、効率性の点に関していえば、PICK系(overも含む)は批判される謂れは無いともいえますね。ただ、スタックを操作するのにもう一個スタックアイテムを積むというのは、不格好といえば不格好ですが(自分としてはこの点が引っ掛かってPICKを避けてます(^^;;)。つーか、必要にならないように組めよ、ってことなんですが。)。
「待ち行列」についてなんですが、分かってみれば「なるほど」の訳です。って、もともとが何かを待ってる人の行列って意味のことばが、コンピュータに転用されたんでしょう。でも、始めてこの言葉を見たときには、何のことか全然わかりませんでしたよ(^^;;)。むか～し、よく行ってた本屋に、「応用待ち行列」(今もでてますかね)とかいう題の本があって、そのタイトルだけながめて、応用されるのを待ってる公式かなんか(自然科学系の棚にあったから)が行列をつくってるのをイメージしてましたよ(^^;;)。「応用を待ってるぞ、なんて、妙にキャッチーな題名の公式集だな。受験参考書か？」なんて(^^;;;)。あれがコンピュータアルゴリズムの本だったなんてねえ(遠い目)。
キューってのは、ほら、玉突きの棒もキューですね(スペル違うか？でも意味合いは同じでしょう。)。ギュッと後ろを押すと前からでてくる「ところてん式」(って、ところてん製造機って見たこと無いんですがね。)。あるいは、上からクリームをいれて絞り出してケーキを装飾するやつ(名前忘れた)。<もうぼろぼろだな(||_ _)。イメージはそんな感じ。ともかく、「待ち行列」って言葉にはそういうトラウマがあるので、なんか言葉はあまり使いたくない。すみません。
**データ構造としてのリスト
データ構造としてのリストは、データ構造としてのアレイに対抗するものといえますが、そこでは「相隣関係」が抽象化されています。アレイではまさにメモリー上の隣、なわけですが、リストでは次のアイテムがあるメモリー上の場所を指すポインタをデータと一緒に保管しておくのです。次のアイテムのポインタを保管する分だけ余分なメモリーを使うわけですが、その分だけ柔軟性が得られます。そのことによって、各アイテムはメモリー上のどこにあってもよいことになるからです。端には無効なポインタ(大抵は0)を詰めておくことも、先頭のアイテムのアドレスを入れて環にすることもできます。
次のアイテムのポインタだけを保存しておく場合には、頭から後ろの方向には辿ることができても、逆向きには進むことはできません。そこで、前のアイテムのポインタも保存しておけば、逆向きに辿ることもできます。そのようなものは、双方向リストと呼ぶようです。
#image(liststruct.jpg)
**リストデータ構造の利点 -- 柔軟性
データ構造としてのリストのアレイに対する具体的利点は、第一には、端以外のアイテムの追加/削除が軽くなることです。一方向リストでいうと、途中にアイテムを追加する場合でも、挿入する場所のひとつ手前のアイテムに付属している次アイテムのポインタデータを取って、新しいアイテムの次アイテムのポインタデータとして格納し、続いて、ひとつ手前のアイテムの次アイテムポインタをその新アイテムのポインタに付け替えればいいわけです。双方向だとふたつ分ありますが、ともかく、ポインタデータを付け替えるだけでよく、後ろにあるアイテムの移動は必要ありません。その結果、アイテム数が増えても、アイテム追加操作自体には変動はありません。
#image(addlistitem.jpg)
アイテムの削除のときには、削除するアイテムが保有している次アイテムのポインタを、自分の前のアイテムの次アイテムポインタデータに格納するだけで縁が切れます。
#image(dellistitem.jpg)
第二には、リスト長の限界が事実上無くなるという利点もあります。アレイデータ構造では、アイテムを一列に並べなければならないため、長いリストのためには、広い、連続したメモリー領域を確保しておく必要があり、いきおい、どこかに明確に限界を設定する必要があります。ところが、リストデータ構造では、アイテム自体は、メモリー上の何処にあってもよく、新規アイテムのためには、メモリーにその分の隙間があればそこに突っ込んでおけば充分です。「相隣関係」は、ポインタによる参照だけで定めることができるからです。動的で柔軟性の高いデータ構造であるといえます。
**抽象データ型としての狭義のリスト
上のような見方は、既に、リストデータ構造を、アイテム加除の効率化に注目した抽象データ型としてとらえています。抽象データ型であることに着目するときは狭義のリストということにします。やっぱり、抽象的なリスト概念には別の名前をつけるべきですね。
**リストデータ構造の苦手 -- アイテム探索
さて、長所があれば短所もあるものです。各アイテムがメモリーの何処にあるのか予めはわからないのですから、「何項目」と指定して、すぐにそこに到達することはできません。基本は、頭から、ポインタを辿りながら、項目を数えていって、目的地に到達したところで初めて、必要なデータにアクセスできます。つまり、探索など、各アイテムデータへのアクセスは遅くなるのです。挿入/削除のときにも、どこに挿入/どのアイテムを削除するかを決めるのに場所を探索するとすれば同じことです。
そのようなわけで、リストデータ構造を基礎とする抽象データ型としての狭義のリストは、探索の効率性は捨てて、アイテムの自由な追加削除という操作に注目したものといえます。しかし考えてみると、データアクセスにしても、リストの全体に一様な処理を施したい場合には、アレイデータ構造と比較して特に遅いことはありません(nに比例)。すると、リストの全項目への繰り返し操作(Iteration)もまた、抽象データ型としてのリストが得意な動作といえるでしょう。これは、一列に整列されているということの効果であると考えられます。
**リストデータ構造とメモリ
あと、「弱点」として、もうひとつ挙げておきましょう。これは、リストからのアイテムの削除の図から知ることができます。もっとも、これは柔軟性の裏返しであって、必ずしも弱点ではないともいえますが。
リストアイテムを削除した場合、削除されたアイテムは孤立してしまいます。このアイテムを参照しているアイテムがなくなってしまうからです。この場合、この削除されたアイテムに到達する方法が原理的には失われてしまいます。もはや、このアイテムは要らなくなってしまったわけですが、それでも、人知れずメモリー領域を占拠し続けます。このような状態は、メモリーリークと呼ばれ、非常に見つけにくいバグのひとつです。普通のコンピュータなら、小さいリーク一個で困ることはありませんが、リストへの項目の追加/削除を繰り返しているうちに、要らないデータを格納していながら、他の目的には転用できないメモリー領域がどんどん増大して、システムを圧迫し始めます。
PASCALやC、C++といった「低級」言語では、アイテムを削除するときに、削除されたアイテムを見失う前に、それがあるメモリー領域を解放しないといけません。そうすると、その領域はシステムに返却され、その領域の再利用が可能となります。メモリー領域解放の機能はシステムライブラリ関数として提供されていますから、「複雑な参照関係がない」という前提の下では、これ自体はプログラミング上では大した手間ではありません。
**傍論：ガーベージコレクタ
少し話はそれてきますが、このようなリストアイテム削除を取り巻く状況は、LISPが大昔からガーベージコレクタ(Garbage Collector:ゴミ集め)機構を備えていた理由を説明するものとなっています。関数型言語であるLISPでは、全てのデータ処理は、値を返すことに専念するものである関数によっておこなわれなければなりません。「メモリーを解放する」などという、計算でもない、関数でもない、機械の特殊性にかかわる低水準のことをプログラムの内容として書き込むことは許されないことだったわけです。そういう「醜い」操作は隠してしまいたい。そのようなわけで、リストから削除され、もう必要の無い項目は、取りあえずはそのままにしておくものの、定期的に自動的にそれを探し出してメモリー領域を解放し再利用可能にするという機構が、開発環境に漏れなくついてきたのです。リストから切り離されても、その開発環境の中では、その項目への参照は保持しておくわけですね。ガーベージコレクトのときのガーベージを探し出す、あるいは印をつける技巧(アルゴリズム)は、いくつか知られているようです。もちろん、速やかにゴミを発見して解放するためのアルゴリズムの工夫です。古いLISPでは、ガーベージコレクトのタイミングで、処理が、クククッと遅くなったりしたそうです。今では高級なプログラミング言語にはガーベージコレクトは不可欠の補助機構と見なされており、複雑な参照関係が張り巡らされた柔軟なデータ構造の処理とともに、うんこの後にケツも拭かず(洗わず)放置するプログラミング習慣も支援しています(^^;;)。
**もっと複雑なデータ構造
アレイデータ構造は、複雑にしようとしても限度がありますね。でも、ポインタで関連を付けるデータ構造、つまり、リストデータ構造の応用としては、いくらでも複雑な関連がつくれそうです。アイテムを一列に並べる必要は、全くありませんからね。一般的には、データアイテムを頂点(vertexあるいはnode)で表し、それらの間の参照関係を辺(edge -- 図としては向きがあれば矢印で表す)表すことによって、グラフとして表現できるデータ構造にまで複雑化することができます。
そういった変種の中でも比較的簡単で実用的なのは、Tree(ツリー)構造ですね。「木」とか訳されますが、「木」といわれて、木材というか材木というか、素材としての木を思い浮かべてしまう私は、いかにも日本人なんですかね。「ツリー」とカタカナで書くと、クリスマスツリーという連想経由で、木が生えている状態を想像しますね。やっぱ、ど日本人だわ。まあ、このツリー構造というのは、要は樹形図構造ということなんですが。慣習上、根元を上に、枝の伸びる方向を下に描くようです。「逆木」ですねえ。
ツリーの定義としては、グラフ理論の用語を使うのが普通です。頂点と辺からなる、というわけですが、頂点はアイテム、辺はアイテム間のポインタによる参照関係と思えばいいわけです。ポインタデータを保有している頂点(アイテム)を「親」、そのポインタで参照されている頂点(アイテム)を「子」と呼ぶことがあります。ツリー構造では、どの頂点も、ふたつ以上の親を持つことはできません。これに対して、子は大抵複数になります。データ構造としては根(root)のあるツリーだけで取りあえず充分です。「根」というのは、ひとつの頂点であって、何処からも参照されておらず、逆にそこから参照をたどれば、全ての頂点に至ることができるもののことです。どんなツリーにも根はひとつだけあると考えます。ツリーの定義は再帰的におこなわれます。まず、頂点ひとつだけのものも、ツリーの一種と認めます。次に、ひとつの頂点と、n個のツリーがあって、各ツリーの根に、その頂点から辺をおろしたものもツリーと認めます。これで、ツリーは定義できます。ひとつの頂点を適当に取って、そこからたどることのできる頂点と辺を合わせたものもツリー構造になりますが、これはもとのツリーの部分ツリーといいます。
なぜツリー構造が考えられるに至るのか、というと、リスト構造のアイテム探索が苦手であるという特性を克服しようとしたわけです。リスト構造では、アイテムの探索には、基本的には頭からひとつずつたどっていくしかないので、アイテムの個数nに比例して、探索の手間が増えてしまいます。これに対して、ツリー構造にしておけば、枝分かれしている分だけ、探索していく道が短くなります。大体、nが増えるときには、規模としては平均的にlog nに比例する程度にしか、探索の手間は増大しません。ちなみに、コンピュータ関係でlog nと書くときは、その底は2だそうです。つまり、log2nということですね。ビットで測るってことでしょうか。
基本的なものとしては、Binary Tree(二分枝木)というのと、Balanced Tree (平衡木)くらいは簡単にふれておきましょう。
Binary Treeはその名の通り、枝わかれ(子)が二本(以下)のツリーです。必ず二つというのではなくて、二つ以下ということです。結果として、枝が一本きりのリスト構造も、Binary Treeに属するということになってしまいます。そのため、ツリーの作り方によっては、探索の効率化が望めなくなってしまいます。一番いいのは、できるだけきれいに二分枝を張ることです。そうすれば、階層の深さ、つまり、根から枝の末端(「葉」(leaf)といいます)に至るまでの中間のアイテム数が、全アイテム数nに対してlog n程度になることがわかるでしょう。
という話で気付くかもしれませんが、Binary Treeという名前は、そのデータ構造に着目した名前ということになります。抽象データ型としてみると、アイテムの探索とデータアクセスの効率化です。アレイと比べると劣りますが、狭義のリストよりは性能が上です。
アイテムの加除も、ポインタ参照によるリストデータ構造の応用ですから、ポインタの付け替えだけで済み、効率は悪くありません。ツリーへのアイテムの追加は、何らかの方法でアイテムに順番をつけておいて、その順番にしたがって挿入箇所を決めることが前提とされています。いつもお尻だけを操作するというのでもいいのでしょうが。ただ、一般的には、追加削除を繰り返すうち、枝分かれが減ってリスト構造に近づいてしまい、探索効率が落ちてしまう危険があります。この点を回避しようとするのがBalanced Treeなんですが、むしろ、Binary Treeは、そういった配慮をしない二分枝木であるという形で、Balanced Tree区別されるに過ぎません。
平衡木(Balanced Tree)の「平衡(Balanced)」というのは、枝分かれを平均にして、枝の長さが偏らないように、かつツリー階層の深さができるだけ浅くなるように配慮しつつ、アイテムの追加削除をおこなうという意味です。探索の効率にかかわるのは結局、ツリー階層の深さであることは明らかですね。
その「平衡」は、枝分かれの個数に、上限だけでなく、下限も設定することで実現されます。メモリー上のデータ構造として使い道がありそうと考えられているものに、2-3木というのがあります。これは、枝分かれは、最大3、最低でも2に維持する平衡木です。アイテムの追加とか削除の結果、3本以上の枝わかれが必要になりそうなとき、あるいは、枝が一本に減ってしまいそうなときは、新しく分岐点をつくったり、隣の分岐と合併したりして、枝数を調整します。そして最終的には、根から葉までの距離が全て等しくなるようにします。そうすれば、アイテムの追加/削除を繰り返しても、探索の効率が極端に落ちてしまう構造に変改することを防ぐことができるわけです。
枝のすげ替えによる調整は、ひとつの作業自体はそれなりに手間がかかりますが、全アイテム数nの増大のときには、その割には負担は増えていかないということが知られています(log nの規模)。
2-3木を一般化したものとしてB-Treeという概念があります。これは、最多分枝数をm(3以上)とし、最少分枝数をmの半分より大きい最少の整数として、深さを均一にしたものです。m=3で2-3木になることは容易にわかりますね。ただ、一般のB-Treeは、メモリー上のデータ構造よりも、ファイルとかそういう外部記憶装置に保管するデータ構造に向いているとされています。
>抽象データ型について書こうかと思ったので、公共の図書館からその方面の本を借りて、読んでみました。この種の本を読む(多くは立ち読み...すみません)といつも思うんですが、退屈です。いや、それなりに興味深いことは書いてあるし、大抵はプログラム例が載っていて、本来ならそれなりに面白いはずなんですけど、どうも...。いや著者が悪いとかいうつもりは無いです。多分、汎用アルゴリスム一般なんてのには、普通は関心が向かないからじゃないかと思います(もちろん、人による)。つまり、なにか自分が面白いと思うことをするプログラムを書いていて、その途中で何かうまい手順が必要になったというなら、きっと目を剥いて読むんじゃないでしょうかね。
>喩えていうなら、釘と金槌、のこぎりとかんなでもって木造建築をつくるのはおもしろいとしても、釘や金槌のことばかり延々説明されても、という感じですか。もっとも、釘の打ち方やノコのひきかたをきちんと習得していないと、まともな木造建築などできそうにない、というのも確かなことではあります。
>現実問題、「アルゴリズムとデータ構造」の教科書レベルででてくるアルゴリズムなんてのは、大抵の開発環境には、ライブラリとしてついてきます。ですから、普通のプログラミングでは、そのアルゴリスムを自分で実装するなんて必要は無い。まあ、上の喩えでいえば、釘や金槌などから自作することはないっ、ってことですか。でも、使い方は知らないと、建築はできない。ので、アルゴリズムの名前と、その得失を憶える、というところに集中するんでしょうね。でも、それじゃあ、達成感はあまりない。そんなわけで、入門者にはとりあえずいくつか金槌とか釘とかつくってみましょう、と勧めるわけですね。作ってみて初めて得心がいく、って場合もありますし。それに喜びを見いだせる人はそれでいいんですがねえ。
>Forth系でも、商品版ではついてくるんじゃないかと思います。ライブラリ。Mopsでは、その手のライブラリは薄いですね。リストとしては、ポインタリストとハンドルリストがありますが、どっちも上で説明したような、前後を参照した線形のリストじゃないです(アイテム探索速度はO(n0)てか、O(1)です。ポインタ/ハンドルを伸縮するアレイ(追加はいつもお尻に)で管理してますから。だから、Mopsマニュアルにかいてあるんですね、「アイテムの削除をあまり頻繁にはしないということを前提にしている」って。)。一応、Mopsでも内部的には線形のリストも使われてます。単純なデータ構造なんて、プログラムに必要になったらつくりゃいいんで、理屈がわかりゃあ大した手間じゃないです(つくれないのは、理屈が充分にわかっていないからですね)。というか、ツリーとかなんか、シミュレーション以外にどうしても必要って局面なんかあるんですかね。探索ならハッシュでいいわけだし。構文解析とか、かな？まあ、よくわかりません。
>自分としては「茶道」主義だと思いますね、Mopsは。生け花とか、山水画とか、造園とか、今じゃあ分かれてますけど、そういうのはみんな、お茶室を演出する技巧として茶道から派生したんですよね。茶碗を焼くところから入るんですからね、お茶は。お客様をもてなす心を突き詰めれば、ひとつだにゆるがせにはできない...って、やりすぎだって。ま、自作じゃなくても、良いものを見極めて使えば良い、ということですがね。そういえば、Forthの心は禅の心なんて話もありますが、喫茶の習慣は禅僧から始まったんですよね。ん～、商品化というのは心を喪うことなのでしょうかね(^^;;)。ただ、「お客様をもてなす心(一期一会)」に当たるMops/Forthプログラミングの求心力って、何でしょうねえ ... ？
----
< [[前へ>再帰（Recursion）]] [[次へ>ソート（整列）]] >
[[目次へ>プログラミングへの道]]
[[トップページへ>トップページ]]
----
