Zenn
👋

【C#データ構造】SortedSet と SortedDictionary と SortedListの違い

2024/11/11に公開
C#
コーディング
tech

はじめに

C#にはSortedSet、SortedDictionary、SortedListがあり違いが気になったので調べました。それぞれコレクションをソートされた状態で保持するデータ構造ですが、用途や内部の実装が異なります。これらの違いについて詳しく説明します。

1. SortedSet

特徴:

  • 重複を許さない（ユニークな要素のみを保持）。
  • 自動的にソートされた順序で要素を保持。
  • 内部的にはバランスの取れた二分探索木（Red-Black Tree）で実装されているため、要素の追加、削除、検索の時間計算量は O(log n)。

用途:

  • 重複を排除し、かつソートされたデータが必要な場合に適しています。

例:

using System;
using System.Collections.Generic;

var sortedSet = new SortedSet<int> { 3, 1, 4, 1, 2 };
foreach (var item in sortedSet)
{
    Console.WriteLine(item); // 出力: 1, 2, 3, 4
}

2. SortedDictionary

特徴:

  • キーと値のペア（キーは一意） としてデータを保持。
  • キーを基準にして自動的にソートされた状態で保持。
  • 内部的にはバランスの取れた二分探索木（Red-Black Tree） で実装されており、追加、削除、検索の時間計算量は O(log n)。

用途:

  • キーを基準にしてソートされた辞書が必要な場合に適しています。

例:

using System;
using System.Collections.Generic;

var sortedDict = new SortedDictionary<string, int>
{
    { "banana", 2 },
    { "apple", 1 },
    { "cherry", 3 }
};

foreach (var kvp in sortedDict)
{
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
    // 出力:
    // apple: 1
    // banana: 2
    // cherry: 3
}

3. SortedList

特徴:

  • キーと値のペア（キーは一意） としてデータを保持。
  • キーを基準にして自動的にソートされた状態で保持。
  • 内部的には動的配列（List<T>） に似た構造で実装されており、キーをソートして保持します。
  • 検索やアクセスの時間計算量は O(log n)　ですが、挿入や削除は O(n) になる場合があります（動的配列のため、挿入・削除時にシフトが必要になることがある）。

用途:

  • メモリ使用量が少ない（DictionaryやSortedDictionaryよりも）ため、キーと値のペアが少なく、頻繁にアクセスするが、挿入や削除はあまり行わない場合に適しています。

例:

using System;
using System.Collections.Generic;

var sortedList = new SortedList<string, int>
{
    { "banana", 2 },
    { "apple", 1 },
    { "cherry", 3 }
};

foreach (var kvp in sortedList)
{
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
    // 出力:
    // apple: 1
    // banana: 2
    // cherry: 3
}

まとめ：違いの比較表

特徴 SortedSet SortedDictionary SortedList
重複の許可 ❌（重複不可） ❌（キーは一意） ❌（キーは一意）
データ構造 バランス木（Red-Black Tree） バランス木（Red-Black Tree） 動的配列
ソート基準 値 キー キー
アクセス速度 O(log n) O(log n) O(log n)
挿入・削除の速度 O(log n) O(log n) O(n)
メモリ使用量 中程度 高い 低い
用途 ユニークなソート済み要素 ソートされた辞書 少数のソートされた辞書

選び方のガイド

  • SortedSet を使うべきケース:
    • 重複しないソートされた集合が必要な場合（例: ユニークなIDのリスト）。
  • SortedDictionary を使うべきケース:
    • キーでソートされた辞書を使いたい場合（例: ソートされた連絡先リスト）。
  • SortedList を使うべきケース:
    • データ数が少なく、頻繁にアクセスするが、挿入・削除があまり行われない場合（例: 設定や固定データのキャッシュ）。

それぞれのコレクションの特性を理解して、用途に応じた最適なデータ構造を選ぶことが重要です。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

Discussion