コレクションの内部実装

13 12月

昨日に引き続きコレクションの話なの、とC#たんはC#たんは前振りしてみる。

今日はコレクションの中身がどうなっているか、実装についてです、とC#たんはC#たんは説明してみたり。

配列リスト

個数不定のデータを持つための一番手っ取り早い方法は、事前に配列を確保しておいて、状況に応じて確保しなおす方法です。

List<T>Stack<T>で内部的にやってることはほぼこれだけです。その他のコレクションでも、この手の仕組みはよく使います。

要は、配列と、実際に何個目まで要素が詰まっているかを表す変数countを持ちます。

要素を追加するたびに、countを増やします。

配列がいっぱいになったら、新しい配列を確保して要素をコピーします。

要素のコピーはそれなりに高負荷なので、要素の最大数がだいたいわかってる場合は、事前に確保する配列の長さをコンストラクターに渡しておきます(capacity引数)。

循環バッファー

循環バッファー(circular buffer)は、Queue<T>の内部的な仕組みです。

配列リストとほぼ同じなんですが、要素数countの代わりに、どこから(first)どこまで(last)要素が入っているかを表す変数を持ちます。

要素をインデックスで取り出す際には、dataの長さで剰余を取ることで、配列の両端をつないだかのように扱います。

配列の長さが足りなくなったら再確保するのは配列リストと同じです。

連結リスト

連結リスト(linked list)は、LinkedList<T>の内部的な仕組みです。

以下のように、ノード(node: 節)をつないでリストを作ります。

要素が増えるたびに必要な分だけメモリを確保します。しかし、インデックスを使ったアクセスはできなくなります(前から順に数えていく効率の悪いやり方しかできない)。

ハッシュ テーブル

Dictionary<TKey, TValue>HashSet<T>の内部ではハッシュ テーブル(hash table)を使っています。

ハッシュ値

キーに対応する何らかの整数値を作れれば、普通の配列を使って辞書を実現できます。その「何らかの整数値」というのがハッシュ値(hash value: 直訳だと「ごちゃまぜにした値」)です。

.NETの場合、object型がGetHashCodeという、ハッシュ値を得るためのメソッドを持っています。ハッシュ テーブルのキーにしたい型は、このGetHashCodeを"適切に"実装する必要があります。

ハッシュ テーブルの原理

さて、問題は2点:

  • 通常、ハッシュ値は被ります。
    • int型よりも広い範囲になるものを、int型に落とし込んで一意になるはずがありません
  • int.MaxValueの長さの配列を確保するのは、無条件にやるには大きすぎます

そこで、以下のような手法を使います。

  • ハッシュ値を、確保した配列(バケツ(bucket)と呼びます)の長さで割った余りを使う
  • 被っていた場合、他の空いている場所を使うルール(たとえば順次隣を見ていくとか、バケツの末尾から見ていくとか)を設ける

もちろん、被れば被るほど、検索性能が落ちます。"適切な"GetHashCode実装が必要と言ったのはこのためで、可能な限り被りが起きなくなるように実装する必要があります。

(例えば、たまたま、bucket.Lengthの倍数しか生成しないような実装になっていた場合、100%ハッシュ値が被ることになります。なので、.NETのDictionary実装では、bucket.Lengthを常に素数(たまたまで倍数になりくい)にしているようです。まあ、GetHashCodeが定数を返すようなよっぽどダメな実装をしない限りはたいてい大丈夫です。)

また、確保するバケツのサイズは十分大きくなければいけません。事前に大き目の領域を取れない場合、被りやすくなり、性能を落とします。

二分探索ツリー

SortedDictionary<TKey, TValue>SortedSet<T>の内部では、二分探索ツリー(binary search tree)というものを使っています。

ツリー

ツリーは、連結リストと同じように、ノードを作ってつないで作ります。ただし、連結リストとは違って、以下のようなつなぎ方をします。

二分探索ツリー

二分探索ツリーは、要素に以下のようなルールを設けたツリー構造です。

  • 左側の子孫ノードには、必ず自分より小さい値を入れる
  • 右側の子孫ノードには、必ず自分より大きい値を入れる

この構造を保つために、要素の挿入にも以下のルールを設けます。

  • 現在のノードの値より小さければ左側の子をたどる
  • 現在のノードの値より大きければ右側の子をたどる
  • 末端まで来たら、そこに新しいノードを作る

このルールを使って、例えば、整数の二分探索ツリーに対して、3, 6, 7, 2, 4, 1, 8, 5の順で値を挿入したとします。すると、以下のようなツリーになるはずです。

col-binary-tree1

ルールがはっきりしているので、要素の検索が容易です。

検索にかかる時間はおおむねツリーの高さに比例しますが、平均的には、要素数nに対して、ツリーの高さはlog2 nになります。つまり、O(log n)での検索ができます。

平衡ツリー

上記の例はかなり良い例で、実はうまくツリーの高さがlog nにならない場合があります。例えば、1, 2, 3, 4, 5の順で要素を挿入すると、以下のような偏りが生じて、ツリーの高さがnになります。

このような偏りを避けるため、挿入時に適宜ツリーを組み替えるアルゴリズムがいくつか知られています。このような仕組みを平衡化(barancing)と呼び、平衡化した二分探索ツリーを平衡ツリー(baranced tree)と呼びます。

ここでは詳細は割愛しますが、.NETのSortedSet<T>などは、赤黒ツリー(red black tree: 2色に塗り分けるというニュアンスしかないです。日本人的な感覚でいうと白黒や紅白と表現すべきかも)という平衡化アルゴリズムを使っています。

整列済み配列

配列を整列済みに保っておけば、二分探索という高速な検索アルゴリズムが使えます。これを応用したのがSortedList<TKey, TValue>です。

二分探索

整列済みの配列に対して、以下のような手順で、要素の検索を高速に行えます。

  • ど真ん中を見る
  • 探したい値が、ど真ん中の値よりも大きければ右を、小さければ左を見る
  • そのさらにど真ん中(1/4のところか3/4のところ)というように、繰り返し調べる

この方法を使えば、最悪でもlog2 n回の繰り返しで検索できます。

これを使って辞書を作る場合、以下のようなことが言えます。

  • 検索は極めて高速です
  • 要素の挿入時には、整列済みになるように、中途半端な位置に要素を入れる必要があるので、O(n)かかります
  • 削除時も同様
  • 要は配列リストなので、確保した配列で足りなくなった場合、再確保とコピーが必要です
広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。