[C#] List<T>の正体とは

##動機
`List<T>`は配列と違い、動的に要素を追加したり削除したりできることは誰でも知るところだろう。筆者のようなC#初心者は、恥ずかしながら今までのその仕組みを考えたことは一度もなく、ただ何となく便利なコレクションクラスとして使っていたわけだが、あるとき`List<T>`についてちゃんと調べようと思って、[Microsoft.Docs](https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.list-1?view=netcore-3.1)を読んでいたら、以外と単純な仕組みで実装されていることを知ったので、簡単な検証を行ってみた。

##前提
Microsoft.Docsを読めばクラスの全機能が分かるし、ご丁寧にコードサンプルまで書いてあるので非常にありがたい~~のだが、如何せん書き方が小難しくて敵わないし、表現に統一性がないのはどうにかならないのだろうか~~。まずは下記プロパティを見てほしい。

>**List\<T>.Capacity プロパティ**

>```C#:C#
>public int Capacity { get; set; }
>```

>内部データ構造体がサイズ変更せずに格納できる要素の合計数を取得または設定します。
>`Capacity`は、サイズ変更が必要になる前に`List<T>`が格納できる要素の数であり、`Count`は実際に`List<T>`内にある要素の数です。
>`Capacity`は、常に`Count`以上です。要素の追加中に`Count`が`Capacity`を超えた場合は、古い要素をコピーして新しい要素を追加する前に、内部配列が自動的に再割り当てされ、容量が増加します。

すなわち、`List<T>`は内部的に要素数の固定された配列をラップしていて、アイテムの追加で限界値`Capacity`を超えそうになったら、自動的に要素数の大きい配列を作り直して元データをコピーしているということらしい。
さらに、下記メソッドの注釈部分を見てみる。

>**List\<T>.Add(T) メソッド**

>```C#:C#
>public void Add (T item);
>```

>`Count`が既に`Capacity`に等しい場合は、内部配列が自動的に再割り当てされ、既存の要素が新しい配列にコピーされてから、新しい要素が追加されるまで、`List<T>`の容量が増加します。
>`Count`が`Capacity`より小さい場合、このメソッドは $O(1)$ 操作になります。 新しい要素に対応するために容量を増やす必要がある場合、このメソッドは $O(n)$ 操作になります。ここで、$n$ は`Count`です。

つまり、通常の値の追加であれば、既に確保されたメモリへの書き込みなので $O(1)$ 操作で済むが、`Capacity`が足りなくなったら配列の作成とコピーの手間が発生するので、$O(n)$ 操作になるということらしい。

ここで、実際どのようにサイズ変更が行われているのか検証してみたいと思う。

##観測

`List<T>`に対して`Add`メソッドを繰り返したときに、`Capacity`がどのように変更されるかを観測するため、以下のメソッドを用意した。

```C#:観測用メソッド
/// <summary>
/// List<T> の Capacity がどのように変動するか観測します。
/// </summary>
/// <param name="list">List<T>。</param>
/// <param name="length">探索する長さ。</param>
private static void ViewCapacity<T>(List<T> list, int length)
{
    var result = new List<(int Start, int Last, int Capacity)>();
    (int Count, int Capacity) current = (list.Count, list.Capacity);
    for (int i = 0; i < length; i++)
    {
        list.Add(default(T));
        if (list.Capacity > current.Capacity)
        {
            // Capacityに変化があった場合は記録
            result.Add((current.Count, list.Count - 1, current.Capacity));
            current = (list.Count, list.Capacity);
        }
    }
    result.Add((current.Count, list.Count, list.Capacity));
    Console.WriteLine(" Count      | Capacity");
    result.ForEach(r => Console.WriteLine($"{r.Start.ToString().PadLeft(4)} - {r.Last.ToString().PadLeft(4)} | {r.Capacity.ToString().PadLeft(4)}"));
}
```

`List<T>`には下記のコンストラクタが用意されているので、各パターンで`Capacity`の変化を観測する。

|パターン|コンストラクタ|説明|
|:---:|:---|:---|
|1.|[List()](https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.list-1.-ctor?view=netcore-3.1#System_Collections_Generic_List_1__ctor)|空で、既定の初期量を備えた、`List<T>`クラスの新しいインスタンスを初期化します。|
|2.|[List(IEnumerable\<T> collection)](https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.list-1.-ctor?view=netcore-3.1#System_Collections_Generic_List_1__ctor_System_Collections_Generic_IEnumerable__0__)|指定したコレクションからコピーした要素を格納し、コピーされる要素の数を格納できるだけの容量を備えた、`List<T>`クラスの新しいインスタンスを初期化します。|
|3.|[List(int capacity)](https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.list-1.-ctor?view=netcore-3.1#System_Collections_Generic_List_1__ctor_System_Int32_)|空で、指定した初期量を備えた、`List<T>`クラスの新しいインスタンスを初期化します。|

###パターン1. `List()`

- 特に何も考えず初期化した場合を観測してみる。

```C#:実行処理1-1
ViewCapacity(new List<int>(), 1000);
```
```C#:実行結果1-1
 Count      | Capacity
   0 -    0 |    0
   1 -    4 |    4
   5 -    8 |    8
   9 -   16 |   16
  17 -   32 |   32
  33 -   64 |   64
  65 -  128 |  128
 129 -  256 |  256
 257 -  512 |  512
 513 - 1000 | 1024
```

- 観測メモ
    - 初期化された状態のとき、`Capacity`は`0`になっている。
    - 初めて項目を追加したときに、`Capacity`は`4`が設定される。
    - 以降、`Count`が`Capacity`を超えようとすると、`Capacity`は**2倍**になる。

###パターン2. `List(IEnumerable<T> collection)`

- 初期化時に要素数を与えた場合を観測してみる。

```C#:実行処理2-1
ViewCapacity(new List<string>(Enumerable.Repeat(string.Empty, 100)), 1000 - 100);
```
```C#:実行結果2-1
 Count      | Capacity
 100 -  128 |  128
 129 -  256 |  256
 257 -  512 |  512
 513 - 1000 | 1024
```

```C#:実行処理2-2
ViewCapacity(new List<string>(Enumerable.Repeat(string.Empty, 128)), 1000 - 128);
```
```C#:実行結果2-2
 Count      | Capacity
 128 -  128 |  128
 129 -  256 |  256
 257 -  512 |  512
 513 - 1000 | 1024
```

```C#:実行処理2-3
ViewCapacity(new List<string>(Enumerable.Repeat(string.Empty, 129)), 1000 - 129);
```
```C#:実行結果2-3
 Count      | Capacity
 129 -  256 |  256
 257 -  512 |  512
 513 - 1000 | 1024
```

- 観測メモ
    - 初期化された状態のとき、`Count`に応じて`Capacity`が自動でセットされる。
    - `Capacity`の値と増加方法は、空のコンストラクタで初期化した場合と同じ。

###パターン3. `List(int capacity)`

 - 最後に、初期化時に`Capacity`を指定するとどうなるのか試してみる。

```C#:実行処理3-1
ViewCapacity(new List<int>(3), 1000);
```
```C#:実行結果3-1
 Count      | Capacity
   0 -   3  |    3
   4 -   6  |    6
   7 -   12 |   12
  13 -   24 |   24
  25 -   48 |   48
  49 -   96 |   96
  97 -  192 |  192
 193 -  384 |  384
 385 -  768 |  768
 769 - 1000 | 1536
```

```C#:実行処理3-2
ViewCapacity(new List<int>(100), 1000);
```
```C#:実行結果3-2
 Count      | Capacity
   0 -  100 |  100
 101 -  200 |  200
 201 -  400 |  400
 401 -  800 |  800
 801 - 1000 | 1600
```

- 観測メモ
    - 初期化時に与えられた`Capacity`が設定される。
    - 以降、`Count`が`Capacity`を超えようとすると、`Capacity`は**2倍**になる。

以上の観測から、サイズが最初から判明している場合は、明示的に`Capacity`を指定した方が内部的再定義の時間を短縮できるのでは、という推測が浮かんでくる。

##計測

通常の初期化と明示的に`Capacity`を指定した初期化で、その後`Add`メソッドを繰り返した時の処理速度がどのくらい変わるか比較するため、下記のメソッドを用意した。

```C#:計測用メソッド
/// <summary>
/// List<T> と List<T>(capacity) で Add() メソッドを繰り返したときの処理速度を比較します。
/// </summary>
private static void CompareTime()
{
    Console.WriteLine("Count | WithOut[ms] | With[ms]    | percentage[%]");
    for (var i = 0; i < 9; i++)
    {
        // 要素数は1, 10, 100, ..., 100000000 のパターンを試す
        var length = (int)Math.Pow(10, i);
        double Test(List<int> list)
        {
            var watch = new Stopwatch();
            watch.Start();
            for (int k = 0; k < length; k++) list.Add(0);
            watch.Stop();
            return watch.Elapsed.TotalMilliseconds;
        }

        var timeSpans = (new List<double>(), new List<double>());
        for (int j = 0; j < 10; j++)    // 試行回数：10回
        {
            timeSpans.Item1.Add(Test(new List<int>()));
            timeSpans.Item2.Add(Test(new List<int>(length)));
        }

        // それぞれの平均処理速度と速度改善率を計算
        var ave1 = timeSpans.Item1.Average();
        var ave2 = timeSpans.Item2.Average();
        Console.WriteLine($"10^{i}  | {ave1:000.0000000} | {ave2:000.0000000} | {((ave2 * 100) / ave1):00.00}");
    }
}
```
```C#:筆者のポンコツPCで計測[1回目]
Count | WithOut[ms] | With[ms]    | percentage[%]
10^0  | 000.0003400 | 000.0000900 | 26.47
10^1  | 000.0002200 | 000.0000700 | 31.82
10^2  | 000.0021600 | 000.0002900 | 13.43
10^3  | 000.0174000 | 000.0025900 | 14.89
10^4  | 000.0923000 | 000.0220400 | 23.88
10^5  | 000.4015200 | 000.2589700 | 64.50
10^6  | 005.6044200 | 003.2822300 | 58.57
10^7  | 064.1446900 | 033.7847300 | 52.67
10^8  | 544.1132700 | 300.4292300 | 55.21
```
```C#:筆者のポンコツPCで計測[2回目]
Count | WithOut[ms] | With[ms]    | percentage[%]
10^0  | 000.0003300 | 000.0000800 | 24.24
10^1  | 000.0002000 | 000.0001100 | 55.00
10^2  | 000.0016800 | 000.0003000 | 17.86
10^3  | 000.0052400 | 000.0022200 | 42.37
10^4  | 000.0699700 | 000.0215700 | 30.83
10^5  | 000.3693000 | 000.2578000 | 69.81
10^6  | 005.8541300 | 003.1537400 | 53.87
10^7  | 067.5346200 | 031.0078600 | 45.91
10^8  | 542.6710200 | 300.1461600 | 55.31
```

今回の計測だけで言えば、やはり明示的に`Capacity`を指定した方が処理速度は速くなることが分かった。

##終わりに

闇に包まれていた`List<T>`の真の姿が見えてきて、少し親近感が湧いた気がする、、
処理速度計測はPCのスペックにもよるところなので、各々試されたい。
また他の言語、例えばc++でいう`Vector`の内部構造はどのようになっているのかも興味深いところである。

##追記
**2020.07.22**
@koturn 氏から教わりましたが、[リファレンスソース](https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,cf7f4095e4de7646)で`List<T>`の内部実装を確認しました。随所で下記メソッドが呼ばれ、二倍量の`Capacity`が確保されていると分かりますね。情報ありがとうございました！
>```C#:list.cs
>// Ensures that the capacity of this list is at least the given minimum
>// value. If the currect capacity of the list is less than min, the
>// capacity is increased to twice the current capacity or to min,
>// whichever is larger.
>private void EnsureCapacity(int min) {
>    if (_items.Length < min) {
>        int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
>        // Allow the list to grow to maximum possible capacity (~2G elements) before encountering >overflow.
>        // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
>        if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
>        if (newCapacity < min) newCapacity = min;
>        Capacity = newCapacity;
>    }
>}
>```