アーカイブ | 17:51

コレクション

12 12月

ちょっといったんTIPS系に話を戻しましょうか、とC#たんは心境を述べてみます。

本日のテーマはコレクションについて。どういうコレクションがあって、どういう場面に使うのか、とC#たんは本日の説明を開始します。

明日、内部的な実装に踏み込んでみましょうか、とC#たんは考えています。

.NETのコレクション

C#というか、.NETには、標準でいろんなコレクションが用意されています。今回はこれらの紹介と、内部的なアルゴリズムについて簡単に説明していきます。

ジェネリック版と非ジェネリック版

歴史的な背景から、.NETのコレクションには2系統のものが存在します。

  • 非ジェネリック版
    • System.Collection名前空間直下にあるクラスです
    • BitArrayを除いて).NET 1.0時代の遺物、というか、黒歴史です
  • ジェネリック版
    • System.Collection.Generic名前空間以下にあるクラスです
    • .NET 2.0/C# 2.0でジェネリックに対応したときに同時に追加されました

非ジェネリック版を「黒歴史」とかひどいこと書きましたが、実際、BitArrayを除けば、使うメリットが全くありません。互換性のためだけに残されています。そして、Silverlightや、Windows 8のMetroアプリでは、そもそもは削除されています。

当然、ここでも、ジェネリック版しか説明しません。

分類

  • リスト系
    • 挿入した順序に意味がある場合に使うコレクションです
    • List<T>, LinkedList<T>, Stack<T>, Queue<T>
  • 辞書系
    • キーを指定して要素の検索が必要な場合に使うコレクションです
    • Dictionary<TKey, TValue>, SortedDictionary<TKey, TValue>, SortedList<TKey, TValue>
  • セット系(set: 数学の意味での集合)
    • 要素があるかどうかだけが重要な場合に使うコレクションで、キーのみの辞書のようなものです
      • Dictionary<TKey, bool>などでも代用可能です
    • HashSet<T>, SortedSet<T>

凡例

以下の形式で書いていこうかと思います。

型名

  • 用途
  • 計算量
  • 内部実装

ちなみに、計算量の説明でO(1)と出てきたら「要素数によらず常に一定のとある時間かかる処理」、O(n)は「要素数に比例したある時間かかる処理」だと思ってください。nを要素数として、O(n2)(二乗に比例)やO(log n)(対数(桁数)に比例)もありえます。

おおまかに、

O(1)>O(log n)>O(n)>O(n log n)>O(n2)

で、左ほど優秀(高速)だと思ってください。

List<T>

  • 用途
    • インデックスを使って要素を読み書きする場合に使います
      • 特に、ランダム アクセスが必要な場合
  • 計算量
    • インデックスを使った読み書きはO(1)
    • 末尾以外への要素の挿入や削除はO(n)
  • 内部実装
    • いわゆる配列リストです
      • C++から来た人は名前で混乱しがちですが、C++でいうとvectorです
    • あらかじめ大き目の配列を確保しておきます
    • 要素が増えて、サイズが足りなくなったらより大きな配列を確保しなおします

LinkedList<T>

連結リスト(linked list)。

  • 用途
    • 事前に大き目の領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使います
  • 計算量
    • このノードの後ろに要素を追加したいというような、位置が事前にわかっている場合の挿入や削除はどこでもO(1)
  • 内部実装
    • 双方向連結リストです
    • {値、前のノードへの参照、後ろのノードへの参照} という情報を持つ「ノード」(node: 節)をつないで作ります

Stack<T>

スタック(stack: 積み荷)。要素を上に積み上げていく感じ。

  • 用途
    • いわゆるLIFO(last in first out)
      • 後に入れた要素ほど先に出す
  • 計算量
    • 要素の出し入れ(末尾にしかできません)はO(1)
  • 内部実装
    • List<T>と同じ配列リストです

Queue<T>

キュー(queue: 待ち行列)。後ろに並んで、前から出ていく感じ。

  • 用途
    • FIFO(fist in first out)
      • 先に入れた要素ほど先に出す
  • 計算量
    • 要素の出し入れ(末尾への挿入、先頭の削除)はO(1)
  • 内部実装
    • いわゆる循環バッファー(明日説明)です
    • 事前に配列を確保しておいて、状況に応じて再確保しなおす仕組みは配列リストと同様です

Dictionary<TKey, TValue>

辞書(dictionary)の代表格。後述のSortedDictionaryやSortedListと、辞書という意味では同じですが、内部的な挙動が異なります。

  • 用途
    • メモリに余裕がある場合にはもっとも高速な辞書です
    • 要素の型は、GetHashCodeメソッドを正しく定義している必要があります
    • キーの順序は保たれません
  • 計算量
    • 事前に大きな領域を確保できれば、ほぼO(1)で挿入・検索・削除可能
    • 逆に最悪の場合、O(n)になります
  • 内部実装
    • ハッシュ テーブル(明日説明)です

SortedDictionary<TKey, TValue>

  • 用途
    • 事前に大き目の領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使います
    • キーの順序通りに要素を列挙できます
  • 計算量
    • 要素の挿入・検索・削除はO(log n)です
  • 内部実装
    • 二分探索ツリー(赤黒ツリー)です

SortedList<TKey, TValue>

  • 用途
    • 要素の挿入・削除よりも、検索の方が圧倒的に多い場合に使います
  • 計算量
    • 要素の挿入・削除はO(n)、検索はO(log n)
  • 内部実装
    • ソート済みの配列に対する二分探索を使っています
    • 配列は、配列リスト同様の再確保を行います

HashSet<T>

いわば、Dictionary<TKey, TValue>のセット(値が必要ない、キーだけの辞書)版です。

  • 用途
    • 他のセットとの使いわけとしてはDictionary<TKey, TValue>と同じ
  • 計算量
    • 事前に大きな領域を確保できれば、ほぼO(1)で挿入・検索・削除可能
    • 逆に最悪の場合、O(n)になります
  • 内部実装
    • ハッシュ テーブルです

SortedSet<T>

いわば、SortedDictionary<TKey, TValue>のセット版です。

  • 用途
    • 他のセットとの使いわけとしてはSortedDictionary<TKey, TValue>と同じ
  • 計算量
    • 要素の挿入・検索・削除はO(log n)です
  • 内部実装
    • 二分探索ツリーです

その他、補足

System.Collections.Generic名前空間以外のコレクションについても少しだけ補足を。

BitArray

System.Collections名前空間直下の唯一の生き残りです。BitArrayは、もともと、bool型に特化したコレクションなので、ジェネリックである必要がありません。

bool型を一覧で扱う場合、AND(& 演算子)やOR(| 演算子)などの論理演算を使った方がメモリ利用効率的に良いので、専用のコレクションが用意されています。

同時実行(concurrent)系

通常のコレクションはスレッド安全ではありません。複数のスレッドから同時に読み書きする場合には、ロックが必要になります。

一方、用途がはっきりしている場合、たとえば、大半のスレッドからは読み取り専用で、ある1つのスレッドからだけ書き込みがあるようなコレクションなら、lockステートメントを使ってロックを書けるよりも効率のいい同時実行のやり方があります。

そういう、用途に応じた同時実行の仕組みを持ったコレクションがあって、System.Collections.Concurrent名前空間に定義されています(.NET 4での追加)。