コレクションを選ぶ
トレードオフとパフォーマンスを学びます。
「コレクションを選ぶ」はCoddyKit上の無料C# Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC# Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C# Academyコースには全4レッスンが含まれています。
まず考えるべき 1 つの質問
コレクションを選ぶときは、まず 1 つの質問から始めます。データにどのようにアクセスするでしょうか。位置でアクセスするのか、キーでアクセスするのか、それともメンバーシップだけを確認するのか、ということです。
List、Dictionary、HashSet は、それぞれ異なるアクセスパターンに対応します。パターンに合ったツールを選べば、コードは高速でわかりやすくなります。
位置でアクセスする: List
順序が重要で、インデックスで項目にアクセスする場合は、List<T> を選んでください。挿入順序を保持し、インデックスによるアクセスを O(1) で行えます。
たとえば、手順のキュー、表示順の行、または先頭から末尾まで反復処理する任意のシーケンスに適しています。重複も許可されます。
var steps = new List<string> { "mix", "bake", "cool" };
string first = steps[0]; // O(1) by indexキーでアクセスする: Dictionary
一意な識別子で検索する場合は、Dictionary<K,V> を選んでください。キーから値へのマッピングを平均 O(1) で行えます。
たとえば、ユーザー ID からユーザー、国コードから国名、単語からその出現回数への対応付けに使えます。キーが「どれか」を示し、値がデータを保持します。
var users = new Dictionary<int, string> {
[101] = "Ann",
[102] = "Bob"
};
string name = users[101];メンバーシップと一意性: HashSet
値が存在するかどうかだけを確認したい場合、または重複を拒否する必要がある場合は、HashSet<T> を選んでください。Contains は平均 O(1) です。
たとえば、アクセス済みの URL、許可された権限、一意なタグなどに使えます。値は紐付かず、要素が存在するかどうかだけを表します。
var visited = new HashSet<string>();
if (visited.Add(url)) {
// first time seeing this url
}コスト一覧
平均的なコストは次のとおりです。List のインデックスアクセスは O(1) ですが、Contains は O(n) です。Dictionary と HashSet の検索は O(1) です。
末尾への List.Add は償却 O(1) ですが、途中への挿入や途中からの削除は O(n) です。Dictionary と HashSet の追加と削除は平均 O(1) です。
// List: index O(1), Contains O(n)
// Dictionary: by-key O(1), no index
// HashSet: Contains O(1), no value, no indexList.Contains は要注意
ループ内で list.Contains を繰り返し呼び出すと、O(n²) になる落とし穴があります。各確認でリスト全体が走査されるためです。
メンバーシップの確認が処理の大部分を占める場合は、HashSet に切り替えてください。この 1 回の変更で、大きなデータに対する遅いループを瞬時に終わる処理へ変えられることがあります。
using System;
using System.Collections.Generic;
class Program {
static void Main() {
var allow = new HashSet<int> { 2, 4, 6 };
foreach (int n in new[] { 1, 2, 3, 4 })
if (allow.Contains(n)) Console.Write(n + " ");
}
}キーと順序の両方が必要な場合
キーによる検索と、予測可能な順序の両方が必要ですか。標準の Dictionary は順序を保証しません。
順序の管理には List を、検索には Dictionary を併用することを検討してください。または、キーをソート順で保持する SortedDictionary<K,V> を使用する方法もあります。ただし、コストは O(log n) です。
var sorted = new SortedDictionary<string, int>();
sorted["b"] = 2;
sorted["a"] = 1;
// enumerates a then b, in key orderメモリとのトレードオフ
ハッシュベースのコレクションは、速度と引き換えにメモリを使用します。Dictionary と HashSet は内部バケットを保持するため、要素が密に並んだ List や配列より多くのメモリを使用します。
数個程度の小さなコレクションでは、List を走査するほうが実際には十分で、メモリ使用量も少なくて済む場合があります。ハッシュ化の効果が発揮されるのは、大規模なデータです。
インターフェイスに対してプログラミングする
メソッドのシグネチャでは、動作する中で最も具体性の低い型を要求するべきです。読み取りには IEnumerable<T>、インデックスによる読み取りには IReadOnlyList<T>、キーによるアクセスには IDictionary<K,V> を受け取るようにします。
これにより、呼び出し元が具体的な実装に依存しなくなり、後からシグネチャを壊さずに実装を交換できます。
int Sum(IEnumerable<int> values) {
int total = 0;
foreach (int v in values) total += v;
return total;
}実践例
テキスト内の一意な単語を数えるには、2 つのコレクションを組み合わせます。HashSet で確認済みの単語を追跡し、Dictionary で出現回数を集計します。
それぞれが 1 つの役割をうまく担います。set は一意性を保証し、dictionary は単語を出現頻度に対応付けます。どちらも各操作の平均計算量は O(1) です。
using System;
using System.Collections.Generic;
class Program {
static void Main() {
var counts = new Dictionary<string, int>();
foreach (var w in "a b a c b a".Split(' '))
counts[w] = counts.GetValueOrDefault(w) + 1;
Console.WriteLine(counts["a"]); // 3
}
}選択のチェックリスト
次の順番で考えてください。キーから値へのマップが必要ですか。その場合は Dictionary を使用します。一意性またはメンバーシップだけが必要ですか。その場合は HashSet を使用します。
どちらでもない場合、順序とインデックスによるアクセスが必要で、重複も許可しますか。その場合は List を使用します。この短いチェックリストで、日常的なケースのほとんどに対応できます。
確認問題
具体的な要件に選択のチェックリストを適用してください。
まとめ
アクセスパターンに応じて選びます。順序付きでインデックスアクセスが必要なシーケンスには List、キーから値を検索するには Dictionary、一意性とメンバーシップには HashSet を使用します。
Big-O に注意してください。負荷の高いループ内での List.Contains を避け、O(1) のハッシュ検索を活用し、インターフェイスに対してプログラミングすることで、選択の柔軟性を保てます。
AI チューターと学ぶ C# — 無料
ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。
- コース
- 93
- レッスン
- 346
よくある質問
「コレクションを選ぶ」レッスンは無料ですか？
はい。「コレクションを選ぶ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C# Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C# Academyコースには全4レッスンが含まれています。
「コレクションを選ぶ」で何を学びますか？
トレードオフとパフォーマンスを学びます。 ブラウザで直接実行するハンズオンコードでC# Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C# Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC# Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「コレクションを選ぶ」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC# Academyレッスンでコードを書いて実行できますか？
はい。すべてのC# Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- Listを実践する
- Dictionaryの検索
- HashSetと一意性
- コレクションを選ぶ