しかし、私はデータ構造の知識があまり無いもので、「これ何？」というようなデータ構造がとても多いのです。
今回、SortedDictionary<TKey, TValue>とSortedList<TKey, TValue>の違いを調べたので記事に書きます。
SortedDictionaryは辞書ですから、
辞書→連想配列→ハッシュテーブルかな、
と思ってしまいますが、内部実装は平衡二分探索木だそうです。
ちなみに、Sortedじゃない普通のDictionary<TKey, TValue>はハッシュテーブルで実装されています。
まぁ、ハッシュテーブルにソートという概念はありませんからね～。
(厳密にいうとツリーにもソートはありませんが)
というわけで、SortedDictionary<TKey, TValue>はどういうデータ構造かというと、
キーの大小比較による(平衡)二分探索木です。
辞書自体に順番はありませんが、リストに変換するとき整列されるのです。
二分探索木ですから、リストに変換するときに簡単に整列させられるわけですね。
さて、続いてSortedList<TKey, TValue>ですが、こちらもSortedDictionaryと同じインターフェースを持っています。
要するに辞書ですね。
SortedListもSortedDictionaryも辞書の実装なのです。
SortedListはどのような実装なのかというと、ソート済み配列リストを使っています。
配列リストというのはC++でいうvectorです。
SortedListでは要素を追加するときに配列リストに入るわけですが、キーに基づいた大小の順番を保つように挿入されます。
実体が配列ですから、挿入や削除にはかなりの時間を要しますね。
そして、キーを検索するときは二分探索を行います。
また、SortedDictionaryと比較して内部が配列ですので、インデックスによるアクセスが可能です。
辞書にインデックスでアクセスするというのは謎行為ではありますが…、値を列挙するときは便利です。
まぁあと、配列リストに簡単に変換できるのはメリットですね。
SortedDictionaryを配列リストに変換するのにはツリーの探索を行わなければなりませんが、
SortedListはそもそも配列リストなので、コピーするだけです。
というわけで、SortedList<TKey, TValue>はどういうデータ構造かというと、ソート済み配列リストと二分探索を用いた辞書です。
SortedDictionaryとSortedListは互いに一長一短…？
私は総合的に見てSortedDictionaryのほうが圧倒的に便利だと思うのですが、学がないだけかもしれません。
おまけ
HashSet<T>とSortedSet<T>というものがあります。
これらは辞書ではなくセットと言います。
数学でいう集合を表しているみたいです。
Valueがない辞書といえるそうです。
というか、辞書のValueを要素が存在しているかどうか調べるためだけに使う、という感じかな。
ですが、数学の集合をイメージしたほうが分かりやすいですね。
HashSet<T>はハッシュテーブルで実装しています。
対してSortedSet<T>は二分探索木で実装しています。
コレクション | C#たんっ！
http://csharptan.wordpress.com/2011/12/12/%E3%82%B3%E3%83%AC%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3/
上のページには、SortedDictionaryは平衡二分探索木(赤黒木)で実装されていると書いてあるのですが、
SortedSetは二分探索木での実装と書いてあるだけで、平衡二分探索木かどうかは分かりません。
多分、平衡二分探索木だとは思います。
ハッシュテーブルのHashSet<T>と、二分探索木のSortedSet<T>、うまく使いわけようという話でした。
しかし、このセットという物は使いどころあるんですかね…。
tag: