ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

SortedListとSortedDictionaryの違い

C#ではSystem.Collections.Generics名前空間にて様々なデータ構造が提供されています。

しかし、私はデータ構造の知識があまり無いもので、「これ何?」というようなデータ構造がとても多いのです。

今回、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:

コメント

競技プログラミングでの話しか分かりませんが、
Setには同じ値を入れても重複しないので
(例えば1,1,2,2,3,3が1,2,3になる)
重複なく値が何個あるかかぞえるのに使えたとおもいます。

数学的な集合かは微妙ですが...。
(当たり前ながら偶数の集合など、無限集合は扱えませんね)


  • 2014/02/14(金) 23:17:45 |
  • URL |
  • div9851 #-
  • [ 編集 ]

Re: div9851

ああ、なるほど、そういう使い方ができますね。
とても地味ではありますが…。

たしかに数学の集合と完璧に同じというわけではないですね。
あくまでも有限集合、それもコンピュータが処理できる範囲しか扱えません。

そういう使い方も糞もそういう構造だから

  • 2014/03/02(日) 02:47:30 |
  • URL |
  • 表記なし #-
  • [ 編集 ]

Re: 表記なし

同じ値を入れても重複しない → セットの構造 (仕様?)
重複なく値が何個あるのか数えるのに使う → セットの使い方

よって“使い方”と言うのが適していると思いますが…。

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/324-9bab7b17
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。