一般に、キーと値を関連付けて格納するデータ構造を「連想配列」といいます。連想配列は多くのプログラミング言語でサポートされていて、プログラミング言語によっては、ハッシュ (hash), 辞書 (dictonary), マップ (map) などと呼ばれています。拙作のページ「レキシカルスコープとクロージャ」で簡単に説明した「連想リスト」も連想配列のひとつです。
Perl, Python, Ruby など連想配列をサポートしているスクリプト言語がありますが、その実装には「ハッシュ法」が使われています。Perl や Ruby などで連想配列をハッシュと呼ぶのは、アルゴリズムの名称からきているのです。
F# の場合、標準ライブラリに平衡二分木をベースにしたマップ Map<'a, 'b> が用意されています。'a はキーの型、'b は値の型を表します。関数型言語らしく Map は immutable なデータ構造です。また、.NET の標準ライブラリ System.Collections.Generic には辞書 Dictionary<'a, 'b> が用意されているので、それを利用することもできます。Dictionary は mutable なデータ構造です。今回は Map と Dictionary の基本的な使い方について簡単に説明します。
マップはコンストラクタ Map で生成します。
Map sequence => table
引数 sequence はシーケンスの他にリストや一次元配列でもかまいません。要素はキーと値を格納したタプルです。ようするに、連想リストからマップを生成するわけです。なお、キーとなる型には制約 comparison を満たす必要があります。
たとえば、キーが文字列で値が整数の場合、マップは次のように生成します。
> let a = Map [("foo", 1); ("bar", 2); ("baz", 3)];;
val a: Map<string,int> = map [("bar", 2); ("baz", 3); ("foo", 1)]
キーの有無はメソッド ContainsKey で調べることができます。
this.ContainsKey(key) => bool
> a.ContainsKey("foo");;
val it: bool = true
> a.ContainsKey("Foo");;
val it: bool = false
キーに対応する値は、配列のように角カッコを使って求めることができます。ただし、キーが見つからない場合はエラーが送出されます。メソッド TryFind はキーに対応する値を option 型に包んで返します。
this.[key] => value this.TryFind(key) => option
> a.["bar"];;
val it: int = 2
> a.["Bar"];;
=> エラー
> a.TryFind("bar");;
val it: int option = Some 2
> a.TryFind("Bar");;
val it: int option = None
マップに新しいキーと値を追加するにはメソッド Add を使います。マップからキーと対応する値を削除するにはメソッド Remove を使います。
this.Add (key, value) => new_table this.Remove key => new_table
> let b = a.Add("oops", 4);;
val b: Map<string,int> = map [("bar", 2); ("baz", 3); ("foo", 1); ("oops", 4)]
> a;;
val it: Map<string,int> = map [("bar", 2); ("baz", 3); ("foo", 1)]
> let c = a.Remove("foo");;
val c: Map<string,int> = map [("bar", 2); ("baz", 3)]
> a;;
val it: Map<string,int> = map [("bar", 2); ("baz", 3); ("foo", 1)]
Add と Remove は新しいマップを返すことに注意してください。
メソッド Change は指定したキーの値を更新した新しいマップを返します。
this.Change(key, func) => new_table
値は関数 func で更新します。func の型を示します。
'b option -> 'b option
key が見つからない場合、func には None が渡されます。このとき、Some value を返すと Add と同じ動作になります。func が None を返す場合、キーがあれば Remove と同じ動作になります。
> a;;
val it: Map<string,int> = map [("bar", 2); ("baz", 3); ("foo", 1)]
> a.Change("foo", fun _ -> Some 10);;
val it: Map<string,int> = map [("bar", 2); ("baz", 3); ("foo", 10)]
> a.Change("oops", fun _ -> Some 10);;
val it: Map<string,int> =
map [("bar", 2); ("baz", 3); ("foo", 1); ("oops", 10)]
> a.Change("oops", fun _ -> None);;
val it: Map<string,int> = map [("bar", 2); ("baz", 3); ("foo", 1)]
> a.Change("foo", fun _ -> None);;
val it: Map<string,int> = map [("bar", 2); ("baz", 3)]
プロパティ Keys はマップのキーを格納したシーケンスを返します。Values はマップの値を格納したシーケンスを返します。
> a.Keys;; val it: System.Collections.Generic.ICollection<string> = seq ["bar"; "baz"; "foo"] > for x in a.Keys do printfn "%s" x;; bar baz foo val it: unit = () > a.Values;; val it: System.Collections.Generic.ICollection<int> = seq [2; 3; 1] > for x in a.Values do printfn "%d" x;; 2 3 1 val it: unit = ()
プロパティ IsEmpty はマップが空であれば真となります。Count はマップに格納されたデータ数を表します。
> a.IsEmpty;; val it: bool = false > a.Count;; val it: int = 3
この他にも、マップを操作する関数がモジュール Map に用意されています。メソッドに対応する関数を以下に示します。
Map.empty => empty_table Map.isEmpty table => bool Map.count talbe => int Map.add key value table => new_table Map.remove key table => new_table Map.change key func table => new_table Map.containsKey key table => bool Map.find key table => value Map.tryFind key table => value option Map.keys table => sequence Map.values table => sequence
Map にはマップ用の高階関数が用意されています。
> Map.map;;
val it: (('a -> 'b -> 'c) -> Map<'a,'b> -> Map<'a,'c>) when 'a: comparison
> Map.filter;;
val it: (('a -> 'b -> bool) -> Map<'a,'b> -> Map<'a,'b>) when 'a: comparison
> Map.fold;;
val it: (('a -> 'b -> 'c -> 'a) -> 'a -> Map<'b,'c> -> 'a) when 'b: comparison
> Map.foldBack;;
val it: (('a -> 'b -> 'c -> 'c) -> Map<'a,'b> -> 'c -> 'c) when 'a: comparison
> Map.iter;;
val it: (('a -> 'b -> unit) -> Map<'a,'b> -> unit) when 'a: comparison
map, filter, fold, foldBack, iter は今までに説明した高階関数のマップバージョンです。関数にはキーと値が渡されることに注意してください。簡単な使用例を示しましょう。
> Map.iter (fun k v -> printfn "%s, %d" k v) a;;
bar, 20
baz, 30
foo, 10
oops, 40
val it: unit = ()
> Map.map (fun _ v -> v * 10) a;;
val it: Map<string,int> =
map [("bar", 200); ("baz", 300); ("foo", 100); ("oops", 400)]
> Map.map (fun _ v -> string v) a;;
val it: Map<string,string> =
map [("bar", "20"); ("baz", "30"); ("foo", "10"); ("oops", "40")]
> Map.filter (fun _ v -> v > 20) a;;
val it: Map<string,int> = map [("baz", 30); ("oops", 40)]
> Map.filter (fun (k: string) v -> k.[0] = 'b') a;;
val it: Map<string,int> = map [("bar", 20); ("baz", 30)]
> Map.fold (fun a k v -> (k, v)::a) [] a;;
val it: (string * int) list =
[("oops", 40); ("foo", 10); ("baz", 30); ("bar", 20)]
> Map.fold (fun a _ v -> a + v) 0 a;;
val it: int = 100
述語 pred を満たすキーがあるか調べるには Map.exists を使います。Map.forall はすべてのキーが pred を満たせば真を返します。関数 findKey は pred を満たすキーを求めます。option 型で返す関数 tryFindKey もあります。
Map.exists pred table => bool Map.forall pred table => bool Map.findKey pred table => key Map.tryFindKey pred table => key option
pred の型は 'a -> 'b -> bool です。
> let a = Map.empty |> Map.add 1 10 |> Map.add 3 30 |> Map.add 5 50;; val a: Map<int,int> = map [(1, 10); (3, 30); (5, 50)] > Map.exists (fun k _ -> k % 2 <> 0) a;; val it: bool = true > Map.exists (fun k _ -> k % 2 = 0) a;; val it: bool = false > Map.forall (fun k _ -> k % 2 <> 0) a;; val it: bool = true > Map.forall (fun k _ -> k % 2 <> 0) (Map.add 2 20 a);; val it: bool = false > Map.findKey (fun k _ -> k % 2 = 0) a;; => エラー > Map.tryFindKey (fun k _ -> k % 2 <> 0) a;; val it: int option = Some 1 > Map.tryFindKey (fun k _ -> k % 2 = 0) a;; val it: int option = None
Map にはマップをリスト、配列、シーケンスに変換する関数や、その逆関数が用意されています。
> Map.toList;;
val it: (Map<'a,'b> -> ('a * 'b) list) when 'a: comparison
> Map.toArray;;
val it: (Map<'a,'b> -> ('a * 'b)[]) when 'a: comparison
> Map.toSeq;;
val it: (Map<'a,'b> -> seq<'a * 'b>) when 'a: comparison
> Map.ofList;;
val it: (('a * 'b) list -> Map<'a,'b>) when 'a: comparison
> Map.ofArray;;
val it: (('a * 'b)[] -> Map<'a,'b>) when 'a: comparison
> Map.ofSeq;;
val it: (seq<'a * 'b> -> Map<'a,'b>) when 'a: comparison
簡単な使用例を示しましょう。
> Map.toList a;;
val it: (string * int) list =
[("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)]
> Map.toArray a;;
val it: (string * int)[] =
[|("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)|]
> Map.toSeq a;;
val it: seq<string * int> =
seq [("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)]
> Map.ofList [("foo", 10); ("bar", 20); ("baz", 30); ("oops", 40)];;
val it: Map<string,int> =
map [("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)]
> Map.ofArray [|("foo", 10); ("bar", 20); ("baz", 30); ("oops", 40)|];;
val it: Map<string,int> =
map [("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)]
> seq {("foo", 10); ("bar", 20); ("baz", 30); ("oops", 40)} |> Map.ofSeq;;
val it: Map<string,int> =
map [("bar", 20); ("baz", 30); ("foo", 10); ("oops", 40)]
このほかにも Map には便利な関数が用意されています。詳細は F# のリファレンス Map Module をお読みください。
ここでハッシュ法について簡単に説明しておきましょう。ハッシュ法は「ハッシュ表 (hash table)」と呼ばれるデータを格納する配列と、データを数値に変換する「ハッシュ関数 (hash function)」を用意します。
たとえば、ハッシュ表の大きさを n とすると、ハッシュ関数はデータを 0 から n - 1 までの整数値に変換するように作ります。この値を「ハッシュ値 (hash value)」と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。
ハッシュ法で不特定多数のデータを取り扱う場合、異なるデータでも同じハッシュ値が生成されることがあります。これをハッシュ値の「衝突(collision)」といいます。つまり、データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。
ひとつは、ハッシュ表に複数のデータを格納することです。配列にはひとつのデータしか格納できないので、複数個のデータをまとめて格納しておく工夫が必要になります。このときによく利用されるデータ構造がリストです。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されているリストの中からデータを探索します。これを「チェイン法 (chaining)」といいます。
この方法ではハッシュ値の衝突が頻繁に発生すると、データを格納するリストが長くなるため、探索時間が余分にかかってしまいます。効率よく探索を行うには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。
第 2 の方法は空いている場所を探して、そこにデータを入れる方法です。この場合、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。この処理を空いている場所が見つかるまで繰り返します。この方法を「オープンアドレス法 (open addressing)」といいます。
この場合、データの最大数はハッシュ表の大きさに制限されます。また、ハッシュ表の空きが少なくなると、探索効率も極端に低下してしまいます。このため、ハッシュ表の空きが少なくなったら、ハッシュ表のサイズを大きくして、ハッシュ表を作り直す作業を行うのがふつうです。これを「リハッシュ (rehash)」といいます。そのあと探索効率は良くなるので、リハッシュにかけた時間のもとは十分にとれます。
ハッシュ法を実装する場合、どちらの方法でも等値の判定処理とハッシュ関数が必要になります。.NET の場合、クラス System.Object のメソッド Equals をオーバーライドすることで、等値演算子を定義することができます。このとき、メソッド GetHashCode もオーバーライドしないとワーニングが表示されますが、この GetHashCode がハッシュ関数になります。
.NET の辞書 (Dictionary) はハッシュ法を使っています。既存のデータ型は Equals と GetHashCode をオーバーライドしているので、F# でも辞書を使うのは簡単です。ただし、参照型をキーにするときは等値判定とハッシュ値に注意してください。たとえば、クラスのインスタンスはアドレスを使って等値判定を行うので、要素が同じでも等しいと判定されないことがあります。また、配列は要素の値で等値判定を行いますが、要素が同じでもハッシュ値が異なることがあります。
> type Foo(a: int) = - let x = a;; type Foo = new: a: int -> Foo > Foo(1) = Foo(1);; val it: bool = false > [|1;2;3|] = [|1;2;3|];; val it: bool = true > [|1;2;3|].GetHashCode();; val it: int = 4825033 > [|1;2;3|].GetHashCode();; val it: int = 55283354 > [|1;2;3|].GetHashCode();; val it: int = 48766684 > [1;2;3] = [1;2;3];; val it: bool = true > [1;2;3].GetHashCode();; val it: int = 1956583134 > [1;2;3].GetHashCode();; val it: int = 1956583134 > (1,2,3) = (1,2,3);; val it: bool = true > (1,2,3).GetHashCode();; val it: int = 1152 > (1,2,3).GetHashCode();; val it: int = 1152
リストは要素の値で等値判定とハッシュ値の計算を行っているようです。タプルは値型なので、要素の値を使って処理されています。辞書 (ハッシュ) を使う場合、キーには値型を選ぶ、もしくは Equals と GetHashCode をオーバーライドすることをお勧めします。
次は辞書について説明します。クラス Dictionary<'a, 'b> は .NET のライブラリ System.Collections.Generic にあります。F# から利用する場合は型略称を使うとよいでしょう。
> type dict<'a, 'b> = System.Collections.Generic.Dictionary<'a, 'b>;; type dict<'a,'b> = System.Collections.Generic.Dictionary<'a,'b>
本ページでは辞書の別名として dict を使うことにします。
辞書はコンストラクタ Dictionary で生成します。
Dictionary<'a, 'b>() => empty_table
型略称を使うと、次のようになります。
> let a = dict<string,int>();; val a: dict<string,int> = dict []
F# のタプル (連想リスト) で辞書を初期化することはできません。ご注意くださいませ。
要素は配列のように角カッコでアクセスすることができます。
1. dic.[key] // リード 2. dic.[key] <- value // ライト
1 でキーが見つからない場合はエラーになります。2 は key の値を value に更新します。key が見つからない場合は key と value が辞書に登録されます。メソッド Add(key, value) でも辞書に登録することができます。Map とは違って辞書は mutable なデータ構造なので、キーに対応する値は破壊的に修正されることに注意してください。
> a.["foo"] <- 10;;
val it: unit = ()
> a.["bar"] <- 20;;
val it: unit = ()
> a.Add("baz", 30);;
val it: unit = ()
> a;;
val it: dict<string,int> = dict [("foo", 10); ("bar", 20); ("baz", 30)]
> a.["foo"];;
val it: int = 10
> a.["bar"];;
val it: int = 20
> a.["baz"];;
val it: int = 30
> a.["oops"];;
=> エラー
辞書からキーと値を削除するにはメソッド Remove を使います。
dic.Remove(key) => bool
削除できた場合は true, キーが見つからない場合は false を返します。
> a.["oops"] <- 40;;
val it: unit = ()
> a.["oops"];;
val it: int = 40
> a.Remove("oops");;
val it: bool = true
> a.["oops"];;
=> エラー
メソッド Clear は辞書を空にします。
> a.Clear();; val it: unit = () > a;; val it: dict<string,int> = dict []
キーの有無はメソッド ContainsKey で、値の有無はメソッド ContanisValue で調べることができます。
dic.ContainsKey(key) => bool dic.ContainsValue(value) => bool
> a;;
val it: dict<string,int> = dict [("foo", 100); ("bar", 20); ("baz", 30)]
> a.ContainsKey("foo");;
val it: bool = true
> a.ContainsKey("oops");;
val it: bool = false
> a.ContainsValue(20);;
val it: bool = true
> a.ContainsValue(50);;
val it: bool = false
辞書にはプロパティが用意されています。基本的なプロパティを以下に示します。
> a;;
val it: dict<string,int> = dict [("foo", 10); ("bar", 20); ("baz", 30)]
> a.Count;;
val it: int = 3
> a.Keys;;
val it: System.Collections.Generic.Dictionary`2.KeyCollection<string,int> =
seq ["foo"; "bar"; "baz"]
> a.Values;;
val it: System.Collections.Generic.Dictionary`2.ValueCollection<string,int> =
seq [10; 20; 30]
それでは簡単な例題として、3 次元空間の異なる点 (x, y, z) を n 個作る関数を作ります。要素 x, y, z は 0 から 99 までの整数値とし、乱数で生成することにします。生成する点が少なければ、マップや辞書を使わなくても線形探索で十分ですが、数が多くなると線形探索では時間がかかるようになります。
プログラムは次のようになります。
リスト : n 個の異なる点を作る
open System
// 型略称
type dict<'a, 'b> = Collections.Generic.Dictionary<'a, 'b>
// 点 (x, y, z) を作る
let makePoint (gen: Random) =
(gen.Next(100), gen.Next(100), gen.Next(100))
// 異なる点を N 個作る (線形探索)
let makeData n =
let gen = Random()
let rec iter i xs =
if i = n then xs
else
let p = makePoint gen
if List.contains p xs then iter i xs
else iter (i + 1) (p::xs)
iter 0 []
// マップ
let makeData1 n =
let gen = Random()
let rec iter i (table: Map<(int*int*int),bool>) =
if i = n then table
else
let p = makePoint gen
if table.ContainsKey(p) then iter i table
else table.Add(p, true) |> iter (i + 1)
Map.empty |> iter 0
// 辞書 (ハッシュ)
let makeData2 n =
let gen = Random()
let table = dict<(int*int*int),bool>()
let rec iter i =
if i = n then table
else
let p = makePoint gen
if table.ContainsKey(p) then iter i
else (
table.[p] <- true
iter (i + 1)
)
iter 0
点はタプルで表します。関数 makeData は makePoint で点をひとつ生成し、それが今まで生成した点と異なることを関数 List.contains でチェックします。List.contains は線形探索なので、点が増えると時間がかかるようになります。
関数 makeData1 は生成したデータのチェックにマップを使います。マップは immutable なデータ構造なので、局所関数 iter の引数に渡して、iter を再帰呼び出しするときに更新します。関数 makeData2 は辞書を使ってチェックします。辞書は mutable なデータ構造なので、iter の中でデータを追加しています。
実際に 2000, 4000, 8000, 16000, 32000 個の点を作ったときの実行時間を示します。
| 2000 | 4000 | 8000 | 16000 | 32000 | |
|---|---|---|---|---|---|
| 線形探索 | 0.042 | 0.134 | 0.177 | 0.721 | 2.966 |
| マップ | 0.013 | 0.024 | 0.073 | 0.101 | 0.263 |
| 辞書 | 0.041 | 0.005 | 0.012 | 0.029 | 0.014 |
生成するデータ数が増えると、線形探索よりもマップや辞書の方が圧倒的に速くなります。マップと辞書を比べると、辞書 (ハッシュ) の方が速くなりました。一般に、データの探索だけならばハッシュのほうが速くなるようです。興味のある方はいろいろ試してみてください。