PR

 プログラムを書いていると,キーと値を組にしてデータを保持する辞書(dictionary,連想コンテナ:associative containerとも言います)のデータ構造を使いたくなることがあります。Haskellではこのようなとき,containersパッケージのData.Mapモジュールに用意されているMap型などの「木を使ったデータ型」をよく使います。今回はMap型を紹介します。

辞書を実現する様々な方法

 Haskellで辞書を実現する方法はいくつか考えられます。それらの方法で実装した辞書が,実際の使用に耐えられるかどうかを検証していきましょう。

 辞書を実現する最も簡単な方法は,キーと値の対を直接保持する連想リストを作成することです。連想リストでは対の1番目の要素がキー,2番目の要素が値になります。

 作成した連想リストから,キーにより値を取り出すには,lookup関数を使います。

lookup           :: (Eq a) => a -> [(a,b)] -> Maybe b
lookup key []    =  Nothing
lookup key ((x,y):xys)
    | key == x   =  Just y
    | otherwise  =  lookup key xys

 lookup関数は,指定したキーが連想リスト内にある場合には,最初に見つかったキーに対応する値をJustに包んで返します。そうでない場合にはNothingを返します。

 連想リストは単純で優れているように見えるかもしれません。しかし,連想リストには性能面で問題があります。lookupを使ってキーに対応する値を参照するには,リストの大きさに比例して線形時間(すなわちO(n))がかかります。また,キーの削除にも同じくリストの大きさに比例して線形時間がかかります。辞書として使うには,このコストはかなり高価です。

 もっとも,連想リストがあらゆる面で不利であるわけではありません。キーの追加は,連想リストの先頭に新しいキーと値の組を加えるだけの定数時間の処理です。またキーに対応する値の更新も,連想リストの先頭に要素を加えるようにすることで定数時間に抑えることができます。lookup関数は最初に見つかった値を返すからです。あとから加えたキー/値に頻繁にアクセスするようなプログラムでは,連想リストも選択肢になり得ます。

 次に第19回で説明した配列を使う方法を考えてみましょう。Haskellの配列は,要素を参照するための添え字としてIxクラスのインスタンスを使います。添え字をキーとみなせば,辞書として利用できるように思えます。

 しかし,配列には大きな弱点があります。それは「配列の更新操作のコストが高いこと」です。キーを使った参照は定数時間すなわちO(1)で済みますが,配列の更新には線形時間が必要です。

 配列の更新コストが高いのは,配列の更新にはその配列の再作成が必要であるためです。配列を使用する場所を制限し,STモナドやIOモナドの中でMArrayクラスのインスタンスを配列として使うようにすれば,配列を再作成する必要がないため,配列の更新コストを多少下げられます。しかし,すべての場面で配列の再作成を回避できるわけではありません。配列に対して新たなキーを追加しようとすると,性能の問題が発生する可能性があります。配列は固定範囲の添え字を扱うデータ構造であり,あらかじめ指定した範囲のキーしか持てません。指定した範囲の外にあるキーを利用するには配列を作り直す必要があります。この場合には配列を再作成する必要があるので,更新操作にかかるコストは線形時間になってしまいます。

 このように,配列はキーを使った参照に関しては優秀な反面,要素を更新したりキーを追加したりするのにはあまり適していません。要素の更新やキーの追加を行う辞書には向いていません。

 連想リストも配列も辞書としては不適切だということがわかりました。では,どのようなデータ構造が辞書に適しているのでしょうか?

 他の言語では,辞書を作成したい場合にハッシュ・テーブル(Hash Table)をよく使います。HaskellでもData.HashTableモジュールでハッシュ・テーブルが提供されています。ただし,二つの大きな弱点があるため,あまり利用されません。

 一つ目の弱点は,ハッシュ・テーブルをIOモナドの中でしか使えないことです。ハッシュ・テーブルというデータ構造は,更新操作に副作用を伴います。このため,ハッシュ・テーブルを操作する関数はIOを返すように定義されています。

Prelude Data.HashTable> :t insert
insert :: HashTable key val -> key -> val -> IO ()
Prelude Data.HashTable> :t update
update :: HashTable key val -> key -> val -> IO Bool
Prelude Data.HashTable> :t delete
delete :: HashTable key val -> key -> IO ()
Prelude Data.HashTable> :t Data.HashTable.lookup
Data.HashTable.lookup :: HashTable key val -> key -> IO (Maybe val)

 HashTableに新しいキーを追加するinsert,キーに対応する値の更新を行うupdate,キーの削除を行うdelete,キーを使った参照を行うlookupはいずれもIOを返す関数になっています。

 二つ目の弱点はハッシュ・テーブルの性能です。ハッシュ・テーブルに対する参照・追加・更新・削除はおおむね定数時間の処理であり,比較的少ないキーと値を保持する場合には,Haskellのハッシュ・テーブルは期待通りの性能を発揮します。しかし,何らかの理由で異なるキーから同じハッシュ値が作成される「ハッシュ値の衝突(hash collision)」が頻繁に起こるときには性能が劣化します(詳しく知りたい方は,Wikipediaのハッシュ・テーブルおよびハッシュ関数の項目を読んでください)。

 さらにHaskellの場合には,Data.HashTableの実装とガーベジ・コレクション(GC)が原因の性能劣化もあります。

 ハッシュ・テーブルに要素を加えていくと,やがてハッシュ値の衝突が頻繁に発生するようになります。Data.HashTableではこの問題を避けるため,ハッシュ・テーブルに格納されている要素数が,あらかじめ決められている閾値を超える度に,より大きいハッシュ・テーブルを新たに作成します。そして,古いハッシュ・テーブルの要素を新しいハッシュ・テーブルに移しかえることで,ハッシュ・テーブルを拡張します(参考リンク)。

 ところが,ハッシュ・テーブルのこうした拡張が新たな問題を引き起こします。GHCが提供するHaslellの実行時システムは,デフォルトでは小さなヒープ・メモリーしか確保していません(参考リンク)。ヒープ・メモリーは,ハッシュ・テーブルの拡張に伴ってどんどん消費されます。そこで実行時システムは,ヒープ・メモリーの十分な空きを保つために,不必要な古いハッシュ・テーブルを保持しているメモリーを頻繁にGCします。こうした頻繁なGCが,ハッシュ・テーブル使用時の性能を大きく劣化させてしまうのです(参考リンク1参考リンク2)。

なぜ木を使うのか?

 こうした理由から,Haskellではハッシュ・テーブルはあまり使われません。代わりに木を使ったデータ構造をよく使います。

 木は再帰的なデータ構造なので,木に対する要素の参照,追加,削除に副作用はありません。このため,木であれば,Haskellプログラムのどこでも利用できます。また,ハッシュ・テーブルとは異なり,格納されるキーと値が多くなっても,性能が極端に劣化することはありません(参考リンク)。ハッシュ・テーブルとは異なり,木に格納される要素が多くなっても,拡張のために木を作り直す必要はないからです。

 このような理由から,Haskellでは辞書として木をよく使います。

 ただし,参照・追加・更新・削除のそれぞれの操作は,ハッシュ・テーブルに比べて多少コストが高くなります。比較的少ない要素数を扱う場合や,GCがなるべく行われないように実行時システムのオプションで多くのヒープ・メモリーを確保した場合には,ハッシュ・テーブルのほうが性能が良くなることもあります。ハッシュ・テーブルを使うか木を使うかは,実際に性能を測定して決める必要があります。