BT

最新技術を追い求めるデベロッパのための情報コミュニティ

寄稿

Topics

地域を選ぶ

InfoQ ホームページ ニュース 更に.NETの不変コレクションについて

更に.NETの不変コレクションについて

原文(投稿日:2013/04/19)へのリンク

 

1月に不変コレクションについて報告してから、APIも進化し、内部の仕組みについて多くのことがわかってきた。最初に最も最近のリリースにおける変更点の要約:

コンストラクタ

不変のコレクションは、まだコンス トラクターを提供しないが、空のオブジェクトの使用は、もはや不要である。以前は、このようなコードだった。

var list = ImmutableList<int>.Empty.Add(1, 2, 3);

新リリースには、Createという静的なファクトリーメソッドが提供され、汎用的な型推論を使うことができ、式が短くなる。

var list = ImmutableList.Create(1, 2, 3);

互換性

熱く議論されたトピックがIList<T> interfaceの実装である。インターフェイスの支持者は、それが IReadOnlyList<T>の導入以前のライブラリとの相互運用に必要だ、という。批評する人は、同じレガシーライブラリは、必ずしも値を変更する前にIList.IsReadOnly が false かどうかをチェックしない、と文句を言う。

最後に、BCL チーム レガシ問題に頭を下げ、IList<T>を実装した。誰もが もしIList.IsReadOnly が存在しなければ、ずっとよかろうだろう、と言うものの、現時点ではその背後にあまりにも大きな勢いが存在する。

不変クラスとそれらが公開するinterfaceの完全なリストは、互換性表を参照して欲しい。

等価性のセマンティクス

他のコレクション型と同様に、不変コレクションは参照等価性しかサポートしない。 BCL チームが書いている,

コレクションの値等価性は、計算するのがかなり高価であり、ImmutableDictionary<string, ImmutableList<string>>のような入れ子になったコレクションに対して等価性を比較することは、定義するのがもっと難しい。 最後に顧客が指摘しているように、この機能を提供すると、違う比較関数が入ってくるともっと多くの問題の原因になってしまう。

以前、コレクションは、Object.Equalsをオーバーライドしたが、op_equalsはしなかった。

IStructuralEquatableのサポートを聞いてくる人がいた。“一般化が難しい”のでそのインターフェースをサポートしないことにした。例えば、あるシナリオでは、コレクション内のアイテム(例えばパーサー内のホワイトスペースノード)をとばすのが適切かもしれない。それが非固有の実装である可能性はないだろう。

不幸にして不変クラスの設計は、それを見えないようにする必要があり、継承の使わせずに、その後にIStructuralEquatableを追加する。

プラットフォームのサポート

不変コレクション ライブラリは、.NET 4.5 以降用に設計されている。新しい読み取り専用インターフェイスを利用するように設計されており、開発者は古いライブラリの個別バージョンを保守することに興味がない。またWindows 8 と「ポータブル net45 + win 8」プロファイルでも利用できる。

シリアライズ

Serializable 属性を使用したレガシのシリアル化設計は、不変コレクションではサポートされない。現時点では、DataContractSerializer のような他のシリアル化設計をサポートするかどうかについて何も話がない。

内部

不変コレクション(スタックとキューを除いて)は、AVL ツリーをベースにしているので、ツリー全体を最コピーすることなく、リストの頭、中間、あるいは最後尾に挿入できる。ウィキペディアの永続的データ構造に関する記事のツリー部分 にそのようなインサートが説明されている。

不変ハッシュテーブルもAVL木を使用している。ハッシュコードでモジュール操作を実行する、通常のハッシュテーブルのバケット設計ではなく、これらは、実際に生のハッシュコードに基づいてツリーを並べ替える。つまり検索はO(log n)の平均検索時間によるバイナリ検索を必要とする。

マルチスレッド動作を使用するときにビッグ-O表記が誤解を招くことに留意すること。不変コレクションの代わりは、スレッドの安全性を確保するために高価な内部ロックを必要とする、並列コレクションである。

不変コレクションの興味深い特徴は、その内部ノードは不変ではないことだ。コレクションの構築中に作成されたゴミの量を低減するために、各ノードが編集可能な状態で始まる。このために、コンストラクタとしては、既存のAVLツリーに変更を加えることができる。なので廃棄して、それを再作成するのではなく、ノードを追加する。一旦構築が完了すると、不変のラッパーは、さらなる変更を防止するために、フリーズとマークされたノードを返す。

別の意外な設計上の決定は、列挙子が使用するオブジェクトプールだ。.NETでは、列挙子の多くは、アロケーションしないように設計されている。もし IList<T> から列挙子を得ると2つのアロケーションが必要である。List<T>では、列挙子は構造体であり、アロケーションは不要である。

同様に、不変コレクションは、列挙子に構造体を使用している。しかし、内部構造がツリーであるので、列挙子は、それがバックトラックできるように以前に訪問したノードのスタックを含めるためにスタックを必要とする。アロケーションを低減するために、これらのスタックのセットは、単一のロックによって保護されたオブジェクトプール(実際はスタック)に格納されている。実際、これは全不変コレクションライブラリ中の唯一のロックだ。列挙子でdisposeが呼び出されるのは、重要である。さもないと、スタックはオブジェクトプールに戻されない。

詳細については、Inner Workings of Immutable CollectionsというタイトルのChannel 9のビデオを参照して欲しい。

使用法の推奨

不変コレクションを作成するとき、Create関数を使用して一度にすべてのコレクションを作成するのが最善だ。これによって、ツリーを事前にアロケートし、直接ノードを配置することができる。次善の方法は、ToImmutableを呼び出すまでのノードをフリーズしないビルダーを使用することである。

不変コレクション内のアイテムを列挙する場合は、必ずforeachループを使ったほうが良い。内部のツリー構造のため、これはforループよりもはるかに高速である。(サイドノート:.NET 2.0以来、通常のリストさえ、forよりforeachのほうが速く読む込むことができる。)

コレクションが作成された後に変更されることがないなら、不変コレクションは読み取り専用のラッパーによって保護され、通常のコレクションよりもパフォーマンスが劣っている。別のコレクションよりも少し異なっている、新しいコレクションを効率的に作成したいときに、不変コレクションが優れている。

 

この記事に星をつける

おすすめ度
スタイル

BT