目次
文書の過去の版を表示しています。
コレクション ジェネリック クラス の性能比較
O-記法と計算量/速度の関係
| 速度 | 高速 | < | 低速 | ||
|---|---|---|---|---|---|
| 計算量 | 少ない | < | 多い | ||
| 記法 | O(1) | O(log n) | O(n) | O(n log n) | O(n2) |
| 名称関数 | 定数 | 対数 | 線形 | 準線形、線形対数 | 二乗 |
O-記法については ランダウの記号 - Wikipedia を参照のこと。
System.Collections.Generic 名前空間
Dictionary<TKey, TValue>
| 処理 | 計算量 |
|---|---|
| メソッド | |
| Add | Count ⇐ 容量 O(1)に近い Count > 容量 O(n) - 自動拡張の為 |
| Clear | O(n) |
| ContainsKey | O(1)に近い |
| ContainsValue | O(n) |
| Remove | O(1)に近い |
| プロパティ | |
| Count | O(1) |
| Item | O(1)に近い |
HashSet<T>
| 処理 | 計算量 |
|---|---|
| メソッド | |
| Add | Count ⇐ 容量 O(1)に近い Count > 容量 O(n) - 自動拡張の為 |
| Clear | O(n) |
| Contains | O(1) |
| Remove | O(1) |
| プロパティ | |
| Count | O(1) |
LinkedList<T>
| 処理 | 計算量 |
|---|---|
| メソッド | |
| AddAfter、AddBefore、AddFirst、AddLast | O(1) |
| Clear | O(n) |
| Contains | O(n) |
| Find | O(n) |
| FindLast | O(n) |
| Remove | O(n) |
| RemoveFirst、RemoveLast | O(1) |
| プロパティ | |
| Count、First、Last | O(1) |
List<T>
| 処理 | 計算量 |
|---|---|
| メソッド | |
| Add | Count ⇐ 容量 O(1) Count > 容量 O(n) - 自動拡張の為 |
| AddRange | Count ⇐ 容量 O(n) Count > 容量 O(n + m) - 自動拡張の為 |
| Clear | O(n) |
| Contains | O(n) |
| Exists | O(n) |
| Find、FindAll、FindIndex、FindIndex、FindLastIndex | O(n) |
| GetRange | O(n) |
| IndexOf | O(n) |
| Insert | O(n) |
| InsertRange | O(n + m) |
| LastIndexOf | O(n) |
| Remove、RemoveAll、RemoveAt、RemoveRange | O(n) |
| Reverse | O(n) |
| Sort | O(n log n) |
| プロパティ | |
| Count | O(1) |
| Item | O(1) |
Queue<T>
| 処理 | 計算量 |
|---|---|
| メソッド | |
| Clear | O(n) |
| Contains | O(n) |
| Dequeue | O(1) |
| Enqueue | O(n) |
| Peek | O(1) |
| TrimExcess | O(n) |
| プロパティ | |
| Count | O(1) |
SortedDictionary<TKey,TValue>
| 処理 | 計算量 |
|---|---|
| メソッド | |
| Add | O(log n) |
| Clear | O(1) |
| ContainsKey | O(log n) |
| ContainsValue | O(n) |
| Remove | O(log n) |
| TryGetValue | O(log n) |
| プロパティ | |
| Count | O(1) |
| Item | 取得: O(log n) 設定: O(log n) |
SortedList<TKey,TValue>
| 処理 | 計算量 |
|---|---|
| メソッド | |
| Add | 未ソートデータ追加: O(n) ソートデータ追加: O(log n) Count > 容量: O(n) - 自動拡張の為 |
| Clear | O(n) |
| ContainsKey | O(log n) |
| ContainsValue | O(n) |
| IndexOfKey | O(log n) |
| IndexOfValue | O(n) |
| Remove | O(n) |
| RemoveAt | O(n) |
| TrimExcess | O(n) |
| TryGetValue | O(log n) |
| プロパティ | |
| Count | O(1) |
| Item | 取得: O(log n) 設定: O(log n) 未ソートデータ追加: O(n) ソートデータ追加: O(log n) Count > 容量(追加): O(n) - 自動拡張の為 |
Stack<T>
| 処理 | 計算量 |
|---|---|
| メソッド | |
| Clear | O(n) |
| Contains | O(n) |
| Peek | O(1) |
| Pop | O(1) |
| Push | O(1) |
| TrimExcess | O(n) |
| プロパティ | |
| Count | O(1) |