ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

[GoF] データ構造に関するパターン解説

またGoFデザインパターンの記事を書こうと思います。

前回のGoFの記事「Factory MethodとAbstract Factoryの違いを考える」では、
Template Method、Factory Method、Abstract Factoryについて書きましたが、

今回はデータ構造に関するデザインパターンについて解説していきます。

Iteratorパターン、Compositeパターン、Visitorパターンです。


本当は“データ構造に関するデザインパターン”なんてカテゴリはなくて、これらは別のカテゴリになっているんですが、
私はこの三つをデータ構造に関するパターンと言っていいんじゃないかなと思いますね。

特にIteratorとVisitorは一般に、比較されるようです。





Iterator

これはデータ構造を走査する作業を抽象化するためのパターンです。
.NETやJavaでもこのパターンを普通に使っていますね。


データ構造というと、配列やら連結リストやらツリーやらとあって、それぞれ要素へのアクセスの手順も異なるわけですが、

これらを走査する場合、走査というのは要素をひとつずつ取り出すということで、どのデータ構造でも同じことです。

問題は、走査の方法がデータ構造によって異なるということです。
目的は同じなのにです。


そのため、あるデータ構造を走査する処理を書いたときに、もしデータ構造が別の種類に変更になってしまうと、走査の処理もすべて書き換えないといけないわけです。

それが嫌なら、データ構造のほうで自身を配列などの統一的なデータ構造に変換させて返すという手段もありますが、パフォーマンス的な問題があります。

また、データ構造が自己再帰的になっていることがたまにありますが、そのような構造から配列を作ろうとしたら配列長が無限大になってしまいます。


そこで、Iteratorパターンではデータ構造を表すクラスに対して、そのクラスへ子分のようにくっついているIteratorというクラスを作ります。

Iteratorは、親分のデータ構造の要素をひとつずつ列挙していくという役目を担います。

Iteratorの役目をデータ構造のクラスそのものに担わせてもいいじゃないかという気がしますが、クラスが肥大化するというのと、

なによりIteratorは要素の列挙の進捗状況に応じた状態を持っているので、列挙というタスクひとつに対してひとつのIteratorのインスタンスを生成するほうが便利ですね。


さて、Iteratorは親分がどんなデータ構造なのか知っていますが、データ構造を列挙させたい側にしてみたら、
自分はどんな種類のデータ構造を扱っているのか知らなくてもIteratorに任せれば列挙できるということになります。

もちろん、上のようなことを実現するには、本当は具体的なクラスだけじゃなくて、抽象クラスとかインターフェースで、
データ構造のクラスとIteratorのクラスを、それぞれまとめないといけないわけですが、まあ難しいことではないので省略します。


Iteratorを作成するのは、データ構造のクラスです。

自分のタイプに合ったIteratorを作成しないといけないわけで、自分のタイプを知っているのはここでは自分だけですからね。

この関係を実際は抽象化することになるので、ここはFactory Methodパターンになっていると言えます。




Composite

Compositeパターンは簡単ですね。

ファイルを表すクラスとフォルダを表すクラス、FileクラスとFolderクラスを作ったとします。

FileクラスとFolderクラスは木構造になっていて、Fileは葉のノードを表すクラスでFolderは枝のノードを表すクラスであるといえます。

このとき、アプリケーションで開くという処理はFileにしかありえないのでFileクラスにしか書かないし、
フォルダに要素を追加するという処理はFolderにしかありえないのでFolderクラスにしか書きません。


しかし一方、この2つを統一的に使用したい場合もあるはずです。

第一に、Folderクラスの子要素はどうするのでしょうか。
子要素をFile型にするのは、フォルダの中にフォルダが入ってることもありえるのに、それはおかしいですね。

また、名前の取得・変更だとか、サイズを取得するだとかいう処理はFileでもFolderでも変わりません。

そこで、この2つを統一的に扱えるようにするためのインターフェースなり抽象クラスなりをひとつ定義する(Componentクラスとします)というだけのことが、Compositeパターンです。


名前の取得・変更の処理はComponentに名前のフィールドを持たせて、Componentに書けばいいかもしれませんが、

サイズを取得する処理は、Fileなら自身のサイズを取得するのに対して、Folderは自分の子要素のサイズの和をとってかえさなければならないので、違う処理になりますね。

それも、FolderがComponentのメソッドをオーバーライドすることで対応できます。

また、Folderが子要素のサイズの和を取るために、子要素すべてに、これまたサイズを取得するように要請します。

各子要素がFileなのかFolderなのか、親のFolderは知りません。

もしFolderなら、そのFolderもまた子要素にサイズを取得するようにしていて…となっていますが、親はまったくそれを気にする必要はないということです。




Visitor

VisitorパターンはGoFデザインパターンの中でも一番、難しいんじゃないかと思いました。

Iteratorパターンで扱うデータ構造は、それぞれの要素は同じ型でした。
Compositeパターンも、違う型の要素を同じように扱うというパターンでした。


しかしVisitorパターンは、違う型の要素を同じように扱うことは諦めて、逆に型の種類によって異なる処理をしてやろうというパターンです。


Visitorパターンは複雑で、具体例抜きで説明していくのはあまりにもイミフなことになってしまうので、まずは具体例を定義しておきましょう。

今回もなんちゃってC#を使います。


まず、あるホテルを表すデータ構造のクラス、Hotelクラスを定義します。

ここではHotelクラスはRoomの集合体であります。

Roomといっても、安い部屋もあれば、ウルトラデラックスなVIPルームもあると思うので、部屋の種類に応じてクラスを定義するとしましょう。

ただ、とりあえず、それらの親となるRoom抽象クラスだけで話を進めます。


ホテルは部屋の集合なので、HotelクラスにRoomクラスの配列を持たせます。


class Hotel {
  Room[] Rooms;
}

abstract class Room {
}


ホテルの定義は終わったので、適当に三種類の客室を定義します。

・StandardRoom
・GoodRoom
・VIPRoom

コードは書きませんが、これらはRoomクラスの子です。


さて、このときHotelの各部屋をなんらかの方法でいじるという迷惑な客を表すPranksterクラスを定義します。

class Prankster {
  void MessUpHotel(Hotel hotel) {
    foreach(Room room in hotel.Rooms) {
      this.MessUpRoom(room);
    }  }

  void MessUpRoom(Room room) {
    // 部屋をいじる
  }
}



しかし、同じような処理をするのではなく、部屋の種類に応じて別のことをしたいとします。


たとえば、それぞれの種類の部屋のクラスがその種類の部屋専用のメソッドを持っているとしましょう。

部屋の種類とその部屋専用のメソッドのリストを下に挙げます。


・StandardRoom … OpenDoor(ドアを開ける)
・GoodRoom … DeliverMeal(食事を運んでくる)
・VIPRoom … CallMassagist(マッサージ師を呼ぶ)

主語がバラバラなのと、どの部屋でもドアぐらい開くだろというのは無視してください。


このそれぞれのメソッドはなんらかの理由で、共通化できそうもありません。

なので、Pranksterは部屋の種類を判断して、種類に応じたメソッドを呼ぶしかないのでしょうか。

しかし、部屋の種類はどのように判断すればいいのでしょうか、Roomクラスに部屋の種類を表すTypeフィールドを持たせて、いちいちキャストするでしょうか。


class Prankster {
  void MessUpRoom(Room room) {
    if(room.Type == Standard)
      { ((StandardRoom)room).OpenDoor(); }
    else if(room.Type == Good)
      { ((GoodRoom)room).DeliverMeal(); }
    else if(room.Type == VIP)
      { ((VIPRoom)room).CallMassagist(); }
  }
}


しかし、残念ながらこういうのをクソコードと呼ぶわけです。
switch文にするとかそういうレベルの話じゃなくてです。

キャストしてるのも汚いですし、
それ以前にRoomにタイプを表すフィールドを持たせるということは、Room自身がどのような種類の部屋があるのかを把握してしまうということです。


本来ならRoomは部屋の種類を把握していなくてもよかったのに、これではRoomに関するコードを書くときも全体を気にしなければならないということです。

拡張性がなくなったり、バグの原因になったりします。


では別の方法として、処理をそれぞれのRoomの子クラスに書くのはどうでしょうか。

それもおかしいです。
Roomをいじるという処理は明らかに外部からやって来る処理であって、Roomの内部に書くべきではありません。

なので、Roomの外部に処理を書きたいわけです。

それも、Roomの種類に応じた処理を個別に色々な所に書いているとよくわからなくなるので、できればPranksterクラスにまとめて書きたいところです。


さて、いよいよ本題ですが、こんな状況に対してVisitorパターンはある提案をするわけです。

Visitorパターンの肝はダブルディスパッチであると私は思います。
ダブルディスパッチとは何か、まずシングルディスパッチの話をしますが、

抽象クラスのメソッドMethodを呼ぶ処理を書いたとして、この時点で具体的にどんなメソッドが呼ばれるのかはわかりません。
しかし、実際に抽象クラスを継承する具体的なクラスが決まることにより、呼ばれるメソッドも決まります。

これは、ひとつのオブジェクトが決まることで呼び出されるメソッドが決まるのでシングルディスパッチです。

対してダブルディスパッチは、二つのオブジェクトが決まることで呼び出されるメソッドが決まる方法だということです。


こんなことを言っていてもよくわからないので実際にVisitorパターンを適用してみましょう。

まず、Pranksterクラスを編集します。

class Prankster {
  void MessUpHotel(Hotel hotel) {
    foreach(Room room in hotel.Rooms) {
      this.MessUpRoom(room);
    }  }

  void MessUpRoom(Room room) {
    room.Accept(this);
  }

  void MessUpStandard(StandardRoom room) {
    room.OpenDoor();
  }

  void MessUpGood(GoodRoom room) {
    room.DeliverMeal();
  }

  void MessUpVIP(VIPRoom room) {
    room.CallMassagist();
  }
}



なんということでしょう。
部屋の種類ごとに処理のメソッドが分かれました。

まあこれは、Pranksterクラスは部屋の種類を把握する必要があることを意味しますけどね。

しかしRoomが部屋の種類を把握する必要はありません。

(今からRoomはPranksterのメソッドを把握することになるので、部屋の種類を把握しているということになるのかも知れませんが…それはRoomが部屋の種類を気にした処理を書かなければならないという意味にはなりません)


また、MessUpRoomメソッドではroom.Accept(this);という謎のコードが書かれています。
つまりRoomクラス側にAcceptメソッドを今から定義します。


abstract class Room {
  abstract void Accept(Prankster visitor);
}

class StandardRoom {
  void Accept(Prankster visitor) {
    visitor.MessUpStandard();
  } }

class GoodRoom {
  void Accept(Prankster visitor) {
    visitor.MessUpGood();
  } }

class VIPRoom {
  void Accept(Prankster visitor) {
    visitor.MessUpGood();
  } }


Room群を書き直しました。

これはどういうことかというと、Pranksterはとりあえず種類のわからないRoomに対して、MessUpさせてくださいというメッセージを送る(Acceptメソッド)わけですね。

そして、各Roomがそれを許可して、PranksterにMessUpせよというメッセージを送るわけです。


PranksterがRoomのAcceptメソッドを呼んだときに、オーバーライドによってRoomの種類に応じたAcceptメソッドが呼ばれます。

つまりこの時点でオーバーライドのおかげで部屋の種類がわかってしまうのです。

そのAcceptメソッドが、Pranksterクラスのメソッド群から、自分のためのメソッドを呼ぶことで、Pranksterは部屋の種類に応じた処理ができるというわけです。


Visitorパターンにおいて、
RoomはAcceptする側のクラスなのでAcceptorと呼びます。

また、コード中でAccept(Prankster visitor)と書いていましたが、PranksterはVisitorと呼びます。


Visitorパターンにおいて本当はVisitor側のクラスも抽象化しておくべきなのです。

ビジターには部屋にいたずらをするビジター以外にも、普通の客みたいなビジターもいて、それもAcceptの対象とされるはずなのですが、面倒くさいのでVisitorは固定にしてしまいました。


…これは本当はVisitorパターンの説明においてありえないことだと思いますね。

Visitorパターンの肝はダブルディスパッチであると言ったくせに、
これではVisitorのオブジェクトは毎回固定で、AcceptorすなわちRoomが何であるかだけが問題になるのでこれではシングルディスパッチです。


本当のVisitorパターンではVisitorが誰であるかも不確定であり、VisitorとAcceptorの決定により呼び出されるメソッドが決まるので、ダブルディスパッチになっています。

まあ、私が今書いたようなVisitorが固定されたパターンも、見たらわかるように無価値ではないと思いますけどね~。


というわけで、要素の種類に応じた処理の分岐を美しく書けるようにするパターンがVisitorパターンであると言えるでしょう。




Visitorパターンの説明だけ長くなりましたが、まあVisitorパターンは難しいですからね。


今回はデータ構造に関する三つのGoFデザインパターンをまとめました。


しかし、説明するときにサンプルコードを書かないとよくわからないというのはしんどいジャンルですね。

tag: プログラミング オブジェクト指向 GoF デザインパターン データ構造 イテレータ ツリー ディスパッチ

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/441-2e374a4d
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。