.NETのCollection(コレクション)について

あちこちから調べてきた知識を自分用メモとして…

格納するデータの数が決まっている場合は配列を使用できるが、そうでない場合はCollectionが使用できる。

ジェネリックコレクションは非常に便利な機能で、使用すると以下のようなメリットを得ることができる。

• コレクションに特定の型のみが格納されていることが保証される。取り出した要素に対していちいち型の判断をしなくて済む。
• コレクションに間違った型のオブジェクトを格納しようとした場合、コンパイルエラーになり、実行時に例外が発生する可能性を抑えられる。
• コードエディタがコレクションの要素の型を認識し、インテリセンスでその型のメソッドやプロパティを参照できるようになる。
• 要素に対する型変換の回数が減ることにより、実行速度が向上する。

Collectionはネームスペース「System.Collections.Generic」に含まれており、使用する場合はusingで宣言が必要となる。

歴史的な背景から.NETのCollectionには2系統のものが存在する。

#<非ジェネリック>

1. System.Collection名前空間直下にあるクラス

• (BitArrayを除いて).NET1.0時代の遺物
• コレクションの要素のアクセス時に毎回キャストが必要。(例えばArrayListクラスを使用した場合、内部では要素をObject型として取り扱っている。文字列型のオブジェクトを格納しても、それを取り出すときには全てObject型となってしまう。これを元に戻すためにキャストが必要となる。)
  
  なので、
  1. 重い(asを使うと高速になるが変換できない時にそのまま例外を投げてくれるキャストと比べて使いにくい)
  2. コンパイル時にチェックされず実行時にチェックされる
     (何が問題か？ :
     
     ・テスト実行時にすべての行が実行されるとは限らず、実行されなかった行のキャストの妥当性チェックはされない(テスト支援ツールでガバレッジ率100%なら解決？)
     ・実行時にありうる全ての値に対してキャストが妥当かがチェックされない (例えば文字列ばかり入れたつもりのコレクションに誤ったオブジェクトを入れて、取り出すときに文字列型へのキャストを行おうとして失敗し、実行時エラーになる可能性がある))

#<ジェネリック>

1. System.Collection.Jeneric名前空間以下にあるクラス

• NET 2.0/C# 2.0でジェネリックに対応したときに同時に追加された非ジェネリック版は互換性のためだけに残されているので、通常は使用するメリットが全くない。以下対比の表。
  (Queue,SortedList,Stackは同名だが、名前空間が異なる全く別のクラス)

非ジェネリック版	ジェネリック版
ArrayList	List＜T＞
Stack	LinkedList＜T＞
Queue	Queue＜T＞
HashTable	Dictionary＜TKey, TValue＞
なし	SortedDictionary＜TKey, TValue＞
SortedList	SortedList＜TKey, Tvalue＞
なし	HastSet＜T＞
なし	SortedSet＜T＞

計算量の優劣：O(1)＞O(log n)＞O(n)＞O(n log n)＞O(n2)

コレクションの内部の実装は以下のサイトが参考になる。
https://csharptan.wordpress.com/2011/12/13/%E3%82%B3%E3%83%AC%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3-2/

##<リスト系>

挿入した順序に意味がある場合に使うコレクション。

###List＜T＞

####概要

型の指定をしてインスタンス化する。値を呼び出して使用する際キャストが不要。
あらかじめ大きめの配列を確保しておき、足りなくなったら配列を確保し直す。
インデックスを使って要素を読み書きする場合に使う(特にランダムアクセスが必要な場合)
C++でいうとvector。

####計算量

・インデックスを使った読み書きはO(1)
・末尾以外への要素の挿入はO(n)

###LinkedList

####概要

データの要素をリンクリストに繋げていく構造(双方向連結リスト)。
事前に大きめの領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使用。
{値、前のノードへの参照、後ろのノードへの参照}という情報を持つ「ノード」をつないで作る。
インデックスによる参照ができないため、ランダムなアクセスが苦手(先頭から順に、あるいは末尾から逆順にしかアクセスできない)

####計算量

・特定のノードの後ろに要素を追加したいというような、位置が事前に分かっている場合の挿入や削除はどこでもO(1)。
・ノード検索自体はO(n)。

両者を比較した場合挿入処理はLinkedListが圧倒的に早いが、メモリ消費量はListの方が圧倒的に少ない。

###Stack

####概要

LIFO - last in first out 後入れ先出しコレクション。
内部実装はListと同じ。
プログラムの実行中に他の関数を呼び出すときなどに使われている。

####計算量

・要素の出し入れ(末尾にしかできない)はO(1)

###Queue

####概要

FIFO - First in First Out 待ち行列。後ろに要素を足して、先頭から出ていく。
Queueに格納される要素は格納された順に並べられ、そのあとは順序が変更できない。
また、ランダムアクセスはできない。
キューに要素を追加することをEnqueue(エンキュー)、キューから要素を取り出すことをDequeue(デキュー)という。
循環バッファーであり、再確保する仕組み自体は配列リストと同じ。
ディスクの入出力やOSのタスク実行などで使われている。

####計算量

・要素の出し入れ(末尾への挿入、先頭の削除)はO(1)

##<辞書系>
###Dictionary

####概要

メモリに余裕がある場合には最も高速な辞書。
要素の型はGetHashCodeメソッドを正しく定義している必要がある。
キーの順序は保たれないので必ずしも追加した順で列挙されるとは限らない。内部実装はハッシュテーブルとなる。
辞書系の中では一番のパフォーマンスだが、値でのソートは独自に実装する必要があり。

####計算量

・事前に大きな領域を確保できれば、ほぼO(1)で挿入・検索・削除が可能
・逆に最悪の場合O(n)となる。

※使い方は以下を参考
http://takachan.hatenablog.com/entry/2015/06/23/160515

###SortedDictionary

####概要

事前に大きめの領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使う。
要素が追加される時点でキーに基づいて自動的に要素の並べ替えが行われる。なのでキーの順序通りに要素を列挙できる。
内部実装は二分探索(赤黒ツリー)。ランダムアクセスは不可。

####計算量

・要素の挿入・検索・削除はO(log n)

###SortedList

####概要

要素の挿入・削除よりも検索の方が圧倒的に多い場合に使う。
ソート済みの配列に対する二分探索を使っている。配列は、配列リスト同様の再確保を行う。
Listと似た特徴を持ち、インデックスを指定してキーや値を取得したり、逆にキーや値からインデックスを検索したりすることができる。
ただし、Listのように格納した順にインデックスが割り振られるのではなく、SortedListに格納される要素に割り振られるインデックスはあくまでも書く要素を並べ替えた時の順序となる。

####計算量

・要素の挿入・削除はO(n)、検索はO(log n)

##<セット系>

一方のコレクションが他方のコレクションと重複する部分を持つか、

あるいは完全に異なるか、他方を内包するかといったコレクション同士の包含関係を調べることができる。

また、コレクション同士の和(OR)を求めて二つのコレクションをマージしたり、積(AND)を求めて共通する要素だけを残すことができる。

要素は重複することなく格納される。Listなどとは異なりすでに追加されている要素を追加しようとしても重複されて格納されることなく

常に単一の要素として扱われる。そのため、このセットはキーだけを扱う一種のDictionaryのようなコレクションと見ることもできる。

###HashSet

####概要

Dictionaryのセット版。
使い分けはDictionaryと同じ。ハッシュテーブルである。

####計算量

・事前に大きな領域を確保できれば、ほぼO(1)で挿入・検索・削除が可能
・逆に最悪の場合O(n)となる。

###SortedSet

####概要

SortedDictionaryのセット版。
使い分けはSortedDictionaryと同じ。二分探索ツリーである。

####計算量

・要素の挿入・検索・削除はO(log n)

##<その他>
###BitArray

ビット値の小型の配列を管理するクラス。インデクサも使える。
bool型に特化したコレクションなのでジェネリックである必要がない。
bool型を一覧で扱う場合、AND(&演算子)やOR(|演算子)などの論理演算を使ったほうがメモリ利用効率的に良いので専用のコレクションが用意されている。

###同時実行(concurrent)系

通常のコレクションはスレッド安全ではない。複数のスレッドから同時に読み書きする場合にはロックが必要になる。
一方、用途がハッキリしている場合、例えば大半のスレッドからは読み取り専用で、ある１つのスレッドからだけ書き込みがあるようなコレクションならlockステートメントを使ってロックをかけるよりも効率のいい同時実行のやり方がある。
そういう用途に応じた同時実行の仕組みを持った５つの新しいコレクション型があって、.NET4以降、System.Collections.Concurrent名前空間に定義されている。

※詳しくは以下を参考
https://msdn.microsoft.com/ja-jp/library/dd997373(v=vs.110).aspx