Arc.Collection
Arc.Collectionは各種コレクションを実装した高速なC#ライブラリーです。
本家はGitHub archi-Doc/Arc.Collection にあります。
| コレクション | 説明 |
|---|---|
UnorderedList<T> ( List<T>と同等) |
Indexアクセスが可能な、オブジェクトのリスト。 |
UnorderedLinkedList<T>( LinkedList<T>と同等) |
双方向リストで、Node による操作が可能です。 |
OrderedList<T> |
ソート済みでIndexアクセスが可能な、オブジェクトのリスト。IComparable<T> または IComparer<T> が必要。 |
OrderedKeyValueList<TKey, TValue> ( SortedList<TKey,TValue>) |
ソート済みでIndexアクセスが可能な、Key/Valueのリスト。IComparable<TKey> または IComparer<TKey> が必要。 |
OrderedMap<TKey, TValue>( SortedDictionary<TKey, TValue>) |
Keyでソート済み（Red-Black Tree）のKey/Value コレクション。 SortedDictionary<TKey, TValue> との違いは、Nodeアクセスが可能なこと、TKeyがnullも可ということです。IComparable<TKey> または IComparer<TKey> が必要。 |
OrderedSet<T>( SortedSet<T>) |
ソート済み（Red-Black Tree）のコレクション。 OrderedSet<T> は OrderedMap<TKey, TValue> のサブセットで、実際は OrderedMap<T, int> です（TValue は int で、使用されません)。 |
OrderedMultiMap<TKey, TValue> |
Keyでソート済み（Red-Black Tree）のKey/Value コレクション。 重複キーを使用可能です。 |
OrderedMultiSet<T> |
ソート済み（Red-Black Tree）のコレクション。重複オブジェクトも可。 |
UnorderedMap<TKey, TValue>( Dictionary<TKey, TValue>) |
Hash tableで管理されるKey/Value コレクション。UnorderedMap<TKey, TValue> は Dictionary<TKey, TValue> より少し遅いですが、UnorderedMap<TKey, TValue> はNode index操作が可能で、TKeyがnullも可です。 |
UnorderedSet<T> |
UnorderedMap<TKey, TValue> のサブセットで、実際は UnorderedMap<T, int> です（TValue は int で、使用されません)。 |
UnorderedMultiMap<TKey, TValue> |
Hash tableで管理されるKey/Value コレクション。重複キーを使用可能です。 |
UnorderedMultiSet<T> |
UnorderedMap<TKey, TValue> のサブセットで、実際は UnorderedMap<T, int> です（TValue は int で、使用されません)。 |
フツーにジェネリックコレクションがあるのに・・・
車輪の再発明と言うほかありませんが、CrossLink に必要だったため作ってしまいました。実装作業は結構楽しかった。
Quick Start
Package Manager Consoleでインストールします。
Install-Package Arc.Collection
サンプルコード。フツーのコレクションと同じノリで使用できます。
using Arc.Collection;
var array = new int[] { 2, 1, 3, };
var os = new OrderedSet<int>(array);
ConsoleWriteIEnumerable("Array:", array); // 2, 1, 3
ConsoleWriteIEnumerable("OrderedSet:", os); // 1, 2, 3
Console.WriteLine("Add 4, 0");
os.Add(4);
os.Add(0);
ConsoleWriteIEnumerable("OrderedSet:", os); // 0, 1, 2, 3, 4
static void ConsoleWriteIEnumerable<T>(string header, IEnumerable<T> e)
{
Console.WriteLine(string.Format("{0,-12}", header) + string.Join(", ", e));
}
Performance
OrderedSet<T> は SortedSet<T> と同様に、データ構造に赤黒木を使用しています。違いは、OrderedSet<T> は内部的に親ノードへのリンクを持つこと、そしてノードアクセスが可能なことです。
SortedSet<T> より高速に動作します。フツーに使っても速いし、Nodeを使ったアクセスは断然速いです。
Reference: System.Collections.Generic.SortedSet<T>
| Method | Length | Mean | Error | StdDev | Median | Gen 0 | Allocated |
|---|---|---|---|---|---|---|---|
| NewAndAdd_SortedSet | 100 | 4,160.11 ns | 16.214 ns | 22.730 ns | 4,157.33 ns | 1.0223 | 4288 B |
| NewAndAdd_OrderedSet | 100 | 3,384.44 ns | 8.101 ns | 12.126 ns | 3,384.49 ns | 1.4381 | 6024 B |
| NewAndAdd2_SortedSet | 100 | 8,709.41 ns | 151.310 ns | 221.788 ns | 8,551.29 ns | 1.8463 | 7776 B |
| NewAndAdd2_OrderedSet | 100 | 8,042.45 ns | 53.162 ns | 79.570 ns | 8,043.79 ns | 2.0599 | 8664 B |
| AddRemove_SortedSet | 100 | 422.21 ns | 0.637 ns | 0.934 ns | 421.94 ns | 0.0381 | 160 B |
| AddRemove_OrderedSet | 100 | 172.03 ns | 0.423 ns | 0.593 ns | 171.93 ns | 0.0534 | 224 B |
| AddRemoveNode_OrderedSet | 100 | 128.04 ns | 0.327 ns | 0.469 ns | 127.89 ns | 0.0534 | 224 B |
| AddRemoveReuse_OrderedSet | 100 | 118.24 ns | 0.239 ns | 0.335 ns | 118.13 ns | - | - |
| AddRemoveReplace_OrderedSet | 100 | 11.76 ns | 0.211 ns | 0.289 ns | 11.54 ns | - | - |
| Enumerate_SortedSet | 100 | 1,664.30 ns | 17.294 ns | 25.349 ns | 1,682.97 ns | 0.0401 | 168 B |
| Enumerate_OrderedSet | 100 | 1,218.03 ns | 4.344 ns | 6.230 ns | 1,219.51 ns | 0.0114 | 48 B |
Collections
各コレクションの特徴です。うまく使い分けてください。
| Name | Structure | Access | Add | Remove | Search | Sort | Enum. |
|---|---|---|---|---|---|---|---|
UnorderedList<T> |
Array | Index | O(1) | O(n) | O(n) | O(n log n) | O(1) |
UnorderedLinkedList<T> |
Linked list | Node | O(1) | O(1) | O(n) | O(n log n) | O(1) |
OrderedList<T> |
Array | Index | O(n) | O(n) | O(log n) | Sorted | O(1) |
OrderedKeyValueList<V> |
Array | Index | O(n) | O(n) | O(log n) | Sorted | O(1) |
OrderedMap<K, V> |
RB Tree | Node | O(log n) | O(log n) | O(log n) | Sorted | O(log n) |
OrderedSet<T> |
RB Tree | Node | O(log n) | O(log n) | O(log n) | Sorted | O(log n) |
OrderedMultiMap<K, V> |
RB Tree | Node | O(log n) | O(log n) | O(log n) | Sorted | O(log n) |
OrderedMultiSet<T> |
RB Tree | Node | O(log n) | O(log n) | O(log n) | Sorted | O(log n) |
UnorderedMap<K, V> |
Hash table | Node | O(1) | O(1) | O(1) | - | O(1) |
UnorderedSet<T> |
Hash table | Node | O(1) | O(1) | O(1) | - | O(1) |
UnorderedMultiMap<K, V> |
Hash table | Node | O(1) | O(1) | O(1) | - | O(1) |
UnorderedMultiSet<T> |
Hash table | Node | O(1) | O(1) | O(1) | - | O(1) |
-
Orderedコレクションはオブジェクトをソートするため、IComparable<T>またはIComparer<T>が必要です。 - Hash tableを使用するコレクション（
UnorderedMap<TKey, TValue>とか）は適切なIEquatable<T>/GetHashCode()またはIEqualityComparer<T>が必要です。 -
Multiがついたコレクションは、重複キーを使用可能です。 -
OrderedMap<TKey, TValue>は赤黒木（Red-black trees）を使用し、OrderedKeyValueList<TKey, TValue>よりもほとんどのシチュエーションで高速です。絶対にIndexアクセスが必要な場面以外は、OrderedMap<TKey, TValue>の使用をお勧めします。