|
|
|
新しい集合やマップの参入 | 目次 |
二つ目の具体例として新しい種類のマップをコレクションフレームワークに参入させる方法を見てみよう。概要としては、「パトリシアトライ (Patricia trie)」1のキーの型を String とした可変マップを実装したい。 Patricia は "Practical Algorithm to Retrieve Information Coded in Alphanumeric" （英数字で符号化された情報を検索するための実用的アルゴリズム）の頭文字をとった略だ。基本的な考え方としては、集合やマップを、検索キーの次の文字が一意的に子ノードを決定する木構造で格納するというものだ。例えば、"abc"、"abd"、"al"、"all"、"xy" の五つの文字列を格納するパトリシアトライは以下のようになる:
このトライの中から文字列 "abc" に対応するノードを検索したければ、単に "a" とラベル付けされた子ノードに注目し、次に "b" の子ノードに移動し、最後に "c" とラベル付された子ノードに到着する。パトリシアトライがマップとして使われていたならば、キーに関連付けられた値は、キーによって得られるノードに格納される。もし集合ならば、このノードが集合に存在するというマーカを格納するだけでいい。
| import collection._ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| class PrefixMap[T] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| extends mutable.Map[String, T] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| with mutable.MapLike[String, T, PrefixMap[T]] { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| var value: Option[T] = None | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def get(s: String): Option[T] = | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| if (s.isEmpty) value | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| else suffixes get (s(0)) flatMap (_.get(s substring 1)) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def withPrefix(s: String): PrefixMap[T] = | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| if (s.isEmpty) this | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } else { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| val leading = s(0) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| suffixes get leading match { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| case None => | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| suffixes = suffixes + (leading -> empty) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| case | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| suffixes(leading) withPrefix (s substring 1) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| override def update(s: String, elem: T) = | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| withPrefix(s).value = Some(elem) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| override def remove(s: String): Option[T] = | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| if (s.isEmpty) { val prev = value; value = None; prev } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| else suffixes get (s(0)) flatMap (_.remove(s substring 1)) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def iterator: Iterator[(String, T)] = | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (for (v <- value.iterator) yield ("", v)) ++ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (for ((chr, m) <- suffixes.iterator; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (s, v) <- m.iterator) yield (chr +: s, v)) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def += (kv: (String, T)): this.type = { update(kv._1, kv._2); this } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def -= (s: String): this.type = { remove(s); this } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| override def empty = new PrefixMap[T] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
パトリシアトライは非常に効率的な検索と更新をサポートする。もう一つの便利な機能はプレフィックス (prefix) による部分コレクションの選択をサポートすることだ。例えば上記のパトリシアトライでは、木のルートから "a" のリンクをたどることでキーが "a" から始まる部分コレクションを取得することができる。
このような考え方に基づき、パトリシアトライとして実装されるマップの実装を見てみよう。このマップは、任意のプレフィックスから始まる全てのキーの部分マップを返す withPrefix メソッドを提供するため、 PrefixMap と呼ぶことにする。以下のキー具体例でプレフィックスマップを定義してみよう:
| scala> val m = PrefixMap("abc" -> 0, "abd" -> 1, "al" -> 2, | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| "all" -> 3, "xy" -> 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| m: PrefixMap[Int] = Map((abc,0), (abd,1), (al,2), (all,3), | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (xy,4)) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
m に対して withPrefix を呼び出すと別のプレフィックスマップが返ってくる:
| scala> m withPrefix "a" | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| res14: PrefixMap[Int] = Map((bc,0), (bd,1), (l,2), (ll,3)) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
前述のコードは PrefixMap の定義を示す。 このクラスは関連付けされる値の型 T においてパラメータ化され、mutable.Map[String, T] と mutable.MapLike[String, T, PrefixMap[T]] を継承する。このパターンは RNA鎖で見たとおり、MapLike のような実装トレイトを継承することで filter のような変換で正しい戻り値型を得ることができる。
プレフィックスマップのノードには、suffixes と value の二つの可変フィールドがある。value はノードに関連付けられた値があれば、それを含み、None に初期化される。suffixes フィールドには文字から PrefixMap 値へのマップを含み、空のマップに初期化される。
suffixes の実装型としてなぜ不変マップを選んだのかと疑問に思うかもしれない。PrefixMap そのものが可変であるため、可変マップにした方が標準的ではないだろうか。答は、不変マップが少ない数の要素しか含まない場合にそのメモリ空間と実行時間の両方において非常に効率的だというものがある。例えば、5個未満の要素を含むマップは単一のオブジェクトとして表現される。それに対して、標準の可変マップである HashMap は、空であっても普通約 80 バイトのメモリを占める。そのため、小さいコレクションが一般的な場合は、可変よりも不変マップを選んだほうがいいのだ。パトリシアトライの場合は、最上位のノード以外のほとんどのノードが数個の子ノードしか持たないだろうことが予想される。そのため、子ノードを不変マップとして格納するほうが効率的なのだ。
ここでマップの実装に必要な最初のメソッド get を見てみる。 以下のようなアルゴリズムで動作する。空文字に関連付けられた値をプレフィックスマップから取得するには、木のルートノードの value のオプション値を選択する。キーの文字列が空でない場合、文字列の先頭の文字に対応する部分マップを選択する。それがマップを返せば、キー文字列の先頭以外の残りについても同様に検索を進める。もし選択に失敗した場合は、キーはマップに格納されていないため None を返す。オプション値の選択の組み合わせは flatMap によって簡潔に表現されている。オプション値 ov と、オプション値を返すクロージャ f に適用された場合、ov flatMap f は ov と f の両方が定義値を返す場合のみ成功する。それ以外の場合、ov flatMap f は None を返す。
可変マップの実装に必要な次の二つのメソッドは += と -= だ。PrefixMap の実装では、これらは update と remove という二つのメソッドに基づいて定義されている。
remove メソッドは、関連付けられた値を返す前にその値に None がセットされる以外は、get に非常に似ている。update メソッドは、まず withPrefix を呼び出して更新すべきノードを探し出し、value フィールドを渡された値にセットする。withPrefix メソッドは、木構造の中に無いプレフィックス文字があれば部分マップを作成しながら探索を進める。
可変マップの実装に必要な最後の抽象メソッドは iterator だ。 このメソッドはマップ内の全てのキー/値ペアを返すイテレータを作成する必要がある。どのプレフィックスマップに対しても、イテレータは以下のパーツから構成される。第一に、マップのルートノードの value フィールドに定義値 Some(x) を含む場合は、イテレータが最初に返す要素は ("", x) だ。さらに、イテレータは、suffixes フィールドに格納される全ての部分マップのイテレータも探索しなければいけないが、それらのイテレータが返すキー文字列の先頭に一文字追加する必要がある。より正確に言うと、ルートノードから chr を用いて到達した部分マップを m として、m.iterator が返す要素が (s, v) だと仮定すると、ルートノードのイテレータは (chr +: s, v) を代わりに返す。PrefixMap クラスの iterator メソッドの実装では、二つの for 式を連結することでこのロジックは簡潔に実装されている。最初の for 式は value.iterator を周回する。これは、Option が、オプション値が None であれば要素を返さず、オプション値が Some(x) であれば単一の要素 x を返すイテレータメソッドを定義していることを利用している。
| import scala.collection.mutable.{Builder, MapBuilder} | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| import scala.collection.generic.CanBuildFrom | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| object PrefixMap extends { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def empty[T] = new PrefixMap[T] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def apply[T](kvs: (String, T)*): PrefixMap[T] = { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| val m: PrefixMap[T] = empty | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| for (kv <- kvs) m += kv | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| m | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def newBuilder[T]: Builder[(String, T), PrefixMap[T]] = | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| new MapBuilder[String, T, PrefixMap[T]](empty) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| implicit def canBuildFrom[T] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| : CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] = | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| new CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def apply(from: PrefixMap[_]) = newBuilder[T] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def apply() = newBuilder[T] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
PrefixMap に newBuilder メソッドが無いことに注意してほしい。これはマップと集合には MapBuilder クラスのインスタンスがデフォルトのビルダとして付いてくるため、その必要がないためだ。可変マップのデフォルトビルダは空のマップから始まり、後続の要素をマップの += を用いて追加していく。可変集合も同様に振る舞う。不変マップと不変集合のデフォルトビルダは、+= の代わりに非破壊的な加算メソッドである + を用いる。
しかし、どちらの場合においても、正しい種類の集合やマップを構築するには適切な種類の空の集合やマップが必要となる。これは、PrefixMap クラス で最後に定義されるメソッドである empty メソッドによって提供される。このメソッドは単に新しい PrefixMap を返す。
次に、コンパニオンオブジェクト PrefixMap に注目する。実は、PrefixMap クラスは単体でも十分やっていけるのでコンパニオンオブジェクトの定義は正確には必要ない。PrefixMap オブジェクトの主な目的は便宜のためにファクトリメソッドをいくつか定義することにある。また、暗黙の値 CanBuildFrom を定義することで型付けが向上する。
便宜のためのメソッドとしては、empty と apply の二つがある。 Scala コレクションフレームワークの全てのコレクションにおいて同じメソッドがあるので、ここでも定義しておくのが妥当だろう。この二つをメソッドを用いて、PrefixMap を他のコレクションと同じ記法で表記できる:
| scala> PrefixMap("hello" -> 5, "hi" -> 2) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| res0: PrefixMap[Int] = Map((hello,5), (hi,2)) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| scala> PrefixMap.empty[String] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| res2: PrefixMap[String] = Map() | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
PrefixMap オブジェクトのもう一つのメンバは暗黙の値 CanBuildFrom のインスタンスだ。これは、map のようなメソッドが最適な型を返すという前のセクションで見た CanBuildFrom の定義と同じ目的を持つ。例えば、PrefixMap のキー/値ペアについて関数を map すると仮定する。その関数が文字列と何らかの型のペアを返す限り、戻り値のコレクションは再び PrefixMap である。次に具体例で説明する。
| scala> res0 map { case (k, v) => (k + "!", "x" * v) } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| res8: PrefixMap[String] = Map((hello!,xxxxx), (hi!,xx)) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
渡された関数の引数は、プレフィックスマップ res0 のキー/値のペアを取り、文字列のペアを返す。map の戻り値は、値の型として Int の代わりに String を持つ PrefixMap だ。PrefixMap に暗黙の値 canBuildFrom が無ければ、この戻り値はプレフィックスマップではなく一般可変マップになっていただろう。
続いては、まとめ
|
|
|
新しい集合やマップの参入 | 目次 |
