前回は,様々な型のキーを使用できるMap型を辞書として紹介しました。特定の型だけをキーとして使うなら,Map型の代わりに特定の型に最適化された別のデータ型を辞書として利用できます。contaniersパッケージのData.IntMapモジュールは,Int型のキーに特化したデータ型である「IntMap型」を提供しています。今回はIntMap型を紹介します。

キーをInt型に限定して高速化

 前回は,Haskellでは辞書として主に木を利用することを説明しました。木の探索は,「キーと節のラベルを比較する」「比較結果を基に部分木をたどる」という2種類の操作で行います。これらの操作のコストを下げれば,木に対する操作全体のコストを下げられます。

 Map型の定義に使われている平衡2分木は,部分木をたどる操作のコストを下げることに重点を置いたデータ構造です。こまめに木の平衡化を行うことで,一方向の分岐を防ぎ,部分木をたどるコストを低く保ちます。

 一方,キーとラベルを比較するコストを下げるほうが有効な場合もあります。ある程度以上の大きさを持つデータをキーとして使う場合には,キーとラベルを比較する処理がボトルネックになるかもしれません。あるいは,個々のキーを比較する処理のコストはそれほど高くなくても,回数が多いとボトルネックになる可能性もあります。

 キーとラベルを比較するコストは,どうすれば下げられるでしょうか。

 これまでは,キーを不可分なものとして扱ってきました。しかし,文字列のように個々の要素に分解できるものもあります。キーが「Hello」という文字列であれば,「H」「e」「l」「l」「o」と1文字ずつに分解できます。また,Int(整数)のような数値型でも,その値を表現するマシン表現を取り出して「01110」のようなビット列として扱えば,「0」「1」「1」「1」「0」と1ビットずつに分解できます。ビットごとに分ければ,高速なビット演算を比較操作に利用できます。

 個々の要素に分解できるキーであれば,キー全体ではなくキーの一部をラベルと比較して木をたどるように工夫できます。

 そうした工夫を取り入れたデータ構造に「トライ木(Trie)」があります(参考リンク1参考リンク2)。トライ木は,キーの一部を個々の節のラベルにすることで,キーの一部だけで探索できるようにした木のことです。文字列のような可変長のデータをキーとして利用する場合によく使われます。また,DNAのように大きなデータをキーとして検索を行う場合にも,トライ木やトライ木を改良したデータ構造が使われます(参考リンク)。Trieという名前は,キーを使った値の検索を意味する「retrieval」という単語に由来します。

 ただし,単純なトライ木には,大きな欠点があります。使用するキーに偏りがある場合,多くの一方向分岐が発生し,木が無駄に大きくなるのです。例えば,16(2進数では000010000)と254(2進数では011111110)をキーとする木があった場合,以下のような無駄な節と一方向分岐が発生します。

      +--254(011111110)
      |
   +--+
   |
+--+
|
*
|
+--16(000010000)

 無駄な節を省いて木を圧縮するには,それぞれの節で比較に使うキーを可変長にして,一方向分岐を多く含む経路を短縮するという工夫が有効です。このような経路短縮の工夫をトライ木に加えたデータ構造が「パトリシア木(Patricia)」です。Patriciaは「Practical Algorithm To Retrieve Information Coded In Alphanumeric(英数字で符号化された情報を検索するための実用的なアルゴリズム)」の略です。パトリシア木では多くの場合,木の探索にビット列を使うことから「基数木(radix tree)」とも呼びます(参考リンク)。Data.IntMapモジュールのIntMap型はパトリシア木として実装されています。

 では,IntMap型の定義を見てみましょう。

data IntMap a = Nil
              | Tip {-# UNPACK #-} !Key a
              | Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !(IntMap a) !(IntMap a) 
type Prefix = Int
type Mask   = Int
type Key    = Int

 IntMapで使用するInt型には,使用意図を表した「Key」「Mask」「Prefix」という三つの別名が与えられています。Keyはキーのビット列,Maskはビット・マスク,Prefixはキーの接頭辞(prefix)になるビット列の一部です。

 IntMapのNilやTipは,末端である節を表現するのに使います。Nilは空の節,Tipは要素を持つ節であることを表します。

 IntMapがNilデータ構成子だけを持つ場合には,Nilは空の木を意味します。

empty :: IntMap a
empty
  = Nil

 IntMapがTipデータ構成子だけを持つ場合には,1個の要素を持つ木になります。

-- | /O(1)/. A map of one element.
--
-- > singleton 1 'a'        == fromList [(1, 'a')]
-- > size (singleton 1 'a') == 1
singleton :: Key -> a -> IntMap a
singleton k x
  = Tip k x

 singleton関数の定義からわかるように,TipのKeyには探索に使うInt型のキー,a型には要素を格納します。

 Binは木の分岐になる節を表すのに使います。Map型とは異なり,IntMap型の分岐は要素を保持しません。BinのPrefixには,後に続くビット列の最上位ビットである1ビット,または「一方向分岐の経路を短縮した数ビット」をキーの接頭辞として保持します。Maskには,次にたどる節をキーから求めるためのビット・マスクを保持します。

 Prefixが保持するビットは固定長でないことに注意してください。先に説明したように,IntMap型のデータ構造であるパトリシア木では,無駄な一方向分岐を防ぐために経路の短縮を行います。このような短縮を行うには,短縮する経路の長さに応じてPrefixに格納されるビットの長さを変えなければなりません。例えば,短縮すべき経路が「111」である場合にはPrefixに格納するのは3ビット,経路が「101011」の場合にはPrefixに格納するのは6ビットになります。

 このように,IntMapが二つ以上の要素を持つ木である場合には,IntMap型のPrefixとKeyにビット列が格納されます。末端に到達するまでにたどったPrefixと末端のKeyを合わせたものが,全体のキーになります。すなわち,IntMapは「Int型の値を表現するビット列の一部」と「節のラベルが保持するInt型の値のビット列」を比較して探索を行うデータ構造なのです。

 IntMap型を実際に使ってみましょう。Data.IntMapモジュールはIntMap型に対し,Data.MapモジュールのMap型を操作する関数と同じ名前の関数を提供しています。

 Map型と同様に,キーを使って要素を参照するにはlookup関数,新たなキーと要素を追加するにはinsert関数,キーに対応する要素を削除するにはdelete関数を使います。それぞれの関数の型は以下の通りです。

Prelude Data.IntMap> :t Data.IntMap.lookup
Data.IntMap.lookup :: Key -> IntMap a -> Maybe a
Prelude Data.IntMap> :t insert
insert :: Key -> a -> IntMap a -> IntMap a
Prelude Data.IntMap> :t delete
delete :: Key -> IntMap a -> IntMap a

 これらの関数は,キーがInt型の別名であるKeyに限定されることを除けば,Map型と同じように利用できます。

Prelude Data.IntMap> Data.IntMap.lookup 4 $ empty
Nothing
Prelude Data.IntMap> Data.IntMap.lookup 4 $ singleton 4 "d"
Just "d"
Prelude Data.IntMap> Data.IntMap.lookup 5 $ singleton 4 "d"
Nothing
Prelude Data.IntMap> singleton "d" 4

<interactive>:1:10:
    Couldn't match expected type `Int' against inferred type `[Char]'
      Expected type: Key
      Inferred type: [Char]
    In the first argument of `singleton', namely `"d"'
    In the expression: singleton "d" 4
Prelude Data.IntMap> Data.IntMap.lookup ("d", True) $ empty

<interactive>:1:19:
    Couldn't match expected type `Key'
           against inferred type `([Char], Bool)'
    In the first argument of `Data.IntMap.lookup', namely `("d", True)'
    In the first argument of `($)', namely
        `Data.IntMap.lookup ("d", True)'
    In the expression: Data.IntMap.lookup ("d", True) $ empty

Prelude Data.IntMap> delete 4 $ insert 4 "d" empty
fromList []
Prelude Data.IntMap> insert 4 "d" empty
fromList [(4,"d")]
Prelude Data.IntMap> insert 5 "e" $ insert 4 "d" empty
fromList [(4,"d"),(5,"e")]
Prelude Data.IntMap> delete 4 $ insert 4 "d" empty
fromList []
Prelude Data.IntMap> let t = insert 5 "e" $ singleton 4 "d"
Prelude Data.IntMap> delete 4 t
fromList [(5,"e")]
Prelude Data.IntMap> insert 3 "c" t
fromList [(3,"c"),(4,"d"),(5,"e")]

 Int型以外のキーを使おうとすると型エラーが発生しています。きちんとInt型のキーを使った場合には,Map型と同様に利用できていることがわかります。

 ただし,Map型と同じようには利用できない関数もあります。showTreeWith関数です。showTreeWith関数は,Map型の同名の関数よりも引数が1個少なくなっています。

Prelude Data.IntMap> :t showTreeWith
showTreeWith :: (Show a) => Bool -> Bool -> IntMap a -> String
Prelude Data.IntMap> :t Data.Map.showTreeWith
Data.Map.showTreeWith
  :: (k -> a -> String) -> Bool -> Bool -> Data.Map.Map k a -> String

 IntMap型のshowTreeWithには,ラベルと要素を持つ節の表示方法を変える手段は用意されていません。この点を除けば,IntMap型に対するshowTreeWithはMap型に対するshowTreeWithと同様に振る舞います。第1引数で木構造の出力形式,第2引数で木の節と節の間にスペースを空けるかどうかを指定します。

Prelude Data.IntMap> let showTree'' t = putStr $ showTreeWith True False t
Prelude Data.IntMap> showTree'' $ insert 3 "c" t
*
+-- 3:="c"
+--*
   +-- 4:="d"
   +-- 5:="e"
Prelude Data.IntMap> let showTree''' t = putStr $ showTreeWith True True t
Prelude Data.IntMap> showTree''' $ insert 3 "c" t
*
|
+-- 3:="c"
|
+--*
   |
   +-- 4:="d"
   |
   +-- 5:="e"
Prelude Data.IntMap> let showTree'''' t = putStr $ showTreeWith False True t
Prelude Data.IntMap> showTree'''' $ insert 3 "c" t
   +-- 5:="e"
   |
+--*
|  |
|  +-- 4:="d"
|
*
|
+-- 3:="c"

 第1引数にTrueを与えたshowTree''とshowTree'''では,親の木に部分木がぶらさがる形で木構造が表示されます。一方,第1引数にFalseを与えたshowTree''''では,木を右に倒した形で木構造が表示されます。左部分木は分岐の下,右部分木は分岐の上に表示されます。

 第2引数にFalseを与えたshowTree''では,節と節の間が詰まった形で表示されています。一方,第2引数にTrueを与えたshowTree'''とshowTree''''では,節と節の間が空いた形で表示されています。