Go to Qiita Advent Calendar 2024 Top
LoginSignup
15
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@Takuto168(Takutooo 168)

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

Last updated at Posted at 2020-07-20

##動機
List<T>は配列と違い、動的に要素を追加したり削除したりできることは誰でも知るところだろう。筆者のようなC#初心者は、恥ずかしながら今までのその仕組みを考えたことは一度もなく、ただ何となく便利なコレクションクラスとして使っていたわけだが、あるときList<T>についてちゃんと調べようと思って、Microsoft.Docsを読んでいたら、以外と単純な仕組みで実装されていることを知ったので、簡単な検証を行ってみた。

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

List<T>.Capacity プロパティ

C#
public int Capacity { get; set; }

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

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

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

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がどのように変更されるかを観測するため、以下のメソッドを用意した。

観測用メソッド
/// <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() 空で、既定の初期量を備えた、List<T>クラスの新しいインスタンスを初期化します。
2. List(IEnumerable<T> collection) 指定したコレクションからコピーした要素を格納し、コピーされる要素の数を格納できるだけの容量を備えた、List<T>クラスの新しいインスタンスを初期化します。
3. List(int capacity) 空で、指定した初期量を備えた、List<T>クラスの新しいインスタンスを初期化します。

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

  • 特に何も考えず初期化した場合を観測してみる。
実行処理1-1
ViewCapacity(new List<int>(), 1000);
実行結果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)

  • 初期化時に要素数を与えた場合を観測してみる。
実行処理2-1
ViewCapacity(new List<string>(Enumerable.Repeat(string.Empty, 100)), 1000 - 100);
実行結果2-1
 Count      | Capacity
 100 -  128 |  128
 129 -  256 |  256
 257 -  512 |  512
 513 - 1000 | 1024
実行処理2-2
ViewCapacity(new List<string>(Enumerable.Repeat(string.Empty, 128)), 1000 - 128);
実行結果2-2
 Count      | Capacity
 128 -  128 |  128
 129 -  256 |  256
 257 -  512 |  512
 513 - 1000 | 1024
実行処理2-3
ViewCapacity(new List<string>(Enumerable.Repeat(string.Empty, 129)), 1000 - 129);
実行結果2-3
 Count      | Capacity
 129 -  256 |  256
 257 -  512 |  512
 513 - 1000 | 1024
  • 観測メモ
    • 初期化された状態のとき、Countに応じてCapacityが自動でセットされる。
    • Capacityの値と増加方法は、空のコンストラクタで初期化した場合と同じ。

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

  • 最後に、初期化時にCapacityを指定するとどうなるのか試してみる。
実行処理3-1
ViewCapacity(new List<int>(3), 1000);
実行結果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
実行処理3-2
ViewCapacity(new List<int>(100), 1000);
実行結果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メソッドを繰り返した時の処理速度がどのくらい変わるか比較するため、下記のメソッドを用意した。

計測用メソッド
/// <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}");
    }
}
筆者のポンコツ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
筆者のポンコツ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 氏から教わりましたが、リファレンスソースでList<T>の内部実装を確認しました。随所で下記メソッドが呼ばれ、二倍量のCapacityが確保されていると分かりますね。情報ありがとうございました！

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;
   }
}
15
9
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
15
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?