ImmutableListとImmutableArray

本日のお品書き

ImmutableArray<T>と､ImmutableList<T>の違いを検証しつつ､その差異と､使いどころを探ってみようかなと｡

出来ることから見た差異

機能性の差異は全く無い｡なにせどっちも同じ､IImutableListインターフェース持ってるくらいだし｡また､ImmutableArrayと言う語感から､Addやら､RemoveやらModifyやらが出来ないように感じられるけど､実際操作用のメソッドは用意されている｡

ListとArrayが存在するわけ

じゃあ､何故こんなに多様なモノが二つも必要だったのかと言えば､パフォーマンス上､結構な差異が出てくる｡
Please welcome ImmutableArray<T>によれば､Arrayは素のArrayを包む非常に薄いラッパであり､Listは線形構造では無く､木構造を持った実装になっている｡

このことは､操作に対する計算量の差異となる｡以下は参考文献より抜粋｡

Operation	ImmutableArray<T>	ImmutableList<T>
Create()	O(n)	O(n)
this[]	O(1)	O(log n)
Add()	O(n)	O(log n)

Createの操作量はどちらにせよO(n)になるので､変わらないとして､インデックスアクセスと､操作系メソッドの操作量に差異が出ている｡Arrayの場合は､変更系のメソッドの実行にコストがかかる反面､インデックスアクセスが定数で終了できる｡他方､Listは変更系のメソッド呼び出しも､インデックスアクセスもその計算量はO(log n)となり､バランスしてる感じ｡

なので､どっちを使うかは､その特性に合わせて利用することが必要なのかなと｡ちなみに､Please welcome ImmutableArray<T>のガイドラインとして､以下のようになっていた｡

Arrayを使うべき理由

• データの変更がまれであるか又は､要素の総量がとても小さい(概ね16以下)｡
• 要素のイテレーションを効率よく行う必要がある場合｡
• Immutableのコレクションのインスタンスを多数持つ必要があり､なおかつそのデータツリーを保持する余裕を持つことが出来ないとき ¹ ｡

Listを使うべき理由

• データの変更が一般的に発生するかまたは､データの要素数が小さくは無い｡
• コレクションの変更のパフォーマンスの方がコレクションの内容のイテレーションするパフォーマンスより重要な場合｡

IImmutableListに関して

実行時に効率が良い方を選択して利用するようなシナリオの場合､ImmutableListも､ImmutableArrayもIImmutableListを実装しているので､この辺を旨く使えば､より柔軟な実装が可能なんじゃないかなと｡また先に述べたとおり､どちらも機能性の差異はないので､コンシューマが気にすることはあんまり無いし､有りだと思う｡けどその反面､切り替わりの条件付けやら､切り替え時のオーバーヘッドの見積もりをよくよく考えておかないと､オーバーヘッドコストばかりかかってしまって本末転倒な結果にもなりかねないので､その辺は注意しなきゃまずいんじゃないかとは思う｡

まとめ

概ねの使い方としては､List<T>とT[]の関係に近いモノがあるとは思う｡けど､それ以上の差異があったり､そもそもの実装が結構違ったりなので､目的と用法を見越した上で使い分ける必要があるのでは無いかなと思ったり思わなかったり｡

また､恐らく､変更された結果をどのように表現するかも大きく違っていて､Arrayの方は要素をすべてコピー､Listの方は変更の差分を保持している形なので､この辺も検討項目に入れておく必要があるんじゃ無いかなと｡

参考文献

Please welcome ImmutableArray
.NETのコレクション概要とImmutable Collectionsについて

---

1. この文脈からおいらは､ImmutableListの特定のVersionのスナップショットを取得して､他のVersionの状態を保持する必要が無くても､Tree全体を保持する必要があるので､その辺の考慮はしてねってニュアンスなのかなと思った｡ ↩