Mapとdict

対応表

hash table、dictionary、map、呼び名はいろいろありますが、漢字で表現すれば対応表です。

Map

F#ではOCaml由来のMapモジュールが提供されています。Map型は内部実装として二分木を採用しています。OCamlと同等の操作ができる反面、項目１つ１つが参照型なため、項目数が多くなるとGCコストが増加しパフォーマンスが低下します。

dict

F#ではMapとは別にdict関数も提供されています。返されるオブジェクトはIDictionary<'Key, 'Value>インターフェースを実装しますが、実体としてはDictionary<'Key, 'Value>型になります。Dictionary<'Key, 'Value>型はいわゆるhash tableで他の.NET言語でも広く使われるため、パフォーマンスの最適化が期待できます。
ちなみにreadOnlyDict関数もあります。実体はdictと同一で、IReadOnlyDictionary<'Key, 'Value>インターフェースを名乗るだけの違いとなります。

なお、F#には.NET型標準とは異なる振る舞いを持たせている型があります。例えば配列型は単純なEquals()ではなく配列の各要素の一致で判断されます。これを実現するためにHashIdentityモジュールが用意されており、dict関数もこれを使用したdictionaryが作られます。

更なるパフォーマンス向上

Dictionary<'Key, 'Value>型は広く使われているためパフォーマンスが最適化されていますが、それでも最善ではありません。というのも仕様として要素の変更を認めています。変更され得るということはenumerate最中に要素が追加・削除され得るということになります。そのままでは暴走してしまいます。これを防ぐためにDictionary<'Key, 'Value>型では状態をバージョン管理しており、enumerate最中はバージョン更新を検出しています。F#のようなimmutableを前提とする言語では更新検出は無駄になります。

.NET 8ではこの問題を解消したFrozenDictionary<'Key,'Value>型が導入されました。しかしF#ランタイムは.NET 8に依存するわけにはいかないためこの型は使われていません。利用したい場合は、readOnlyDict関数を自分で上書き定義する必要があります。

完全には一致しませんが、雑に上書きするならこれぐらいでもいいんじゃないでしょうか。

open System.Collections.Frozen

let readOnlyDict (keyValuePairs: seq<'Key * 'T>) : IReadOnlyDictionary<'Key, 'T> =
    keyValuePairs.ToFrozenDictionary(fst, snd, HashIdentity.Structural)