C# - Array.Resize() と List.Add() + List.ToArray() の内部処理の比較

最近見つけたコードでArray.Resizeを覚えたので使っていたが、List.Addとの違いや、処理効率がどうなのか気になったので調べた。

先に結論

可変長の配列を扱いたい場合、
Array.Resizeで1要素ずつ増やすよりは、List.AddとToArrayの組み合わせのほうが効率的。
（ここでは、最終的に余分要素のない配列[]を作りたい場合を想定している。
AddするたびにToArrayしたい場合はこの結論の限りではない。）

調査環境

Windows10でILSpyでソースを調べて机上で検討した。処理時間の実測はしていない。
ILSpy上の表示は C#7.3 / VS2017.7 となっている。

List<T>のAddとToArray

Listクラス内部コード - Addメソッド

System.Collections.Generic.Listクラス内

public void Add(T item)
{
    if (_size == _items.Length)
    {
        EnsureCapacity(_size + 1);
    }
    _items[_size++] = item;
    _version++;
}

System.Collections.Generic.Listクラス内

private void EnsureCapacity(int min)
{
    if (_items.Length < min)
    {
        int num = (_items.Length == 0) ? 4 : (_items.Length * 2);
        if ((uint)num > 2146435071u)
        {
            num = 2146435071;
        }
        if (num < min)
        {
            num = min;
        }
        Capacity = num;
    }
}

System.Collections.Generic.Listクラス内

public int Capacity
{
    [__DynamicallyInvokable]
    get
    {
        return _items.Length;
    }
    [__DynamicallyInvokable]
    set
    {
        if (value < _size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        }
        if (value == _items.Length)
        {
            return;
        }
        if (value > 0)
        {
            T[] array = new T[value];
            if (_size > 0)
            {
                Array.Copy(_items, 0, array, 0, _size);
            }
            _items = array;
        }
        else
        {
            _items = _emptyArray;
        }
    }
}

Addメソッドが間接的にCapacityプロパティにsetアクセスして、内部のフィールド_items(T[]型)をリサイズ(new T[リサイズ後の要素数]してArray.Copy)しています。
Capacityプロパティのコードをみると、初期値は4で、リサイズするときは2倍ずつ確保しているようです。

Listクラス内部コード - ToArrayメソッド

System.Collections.Generic.Listクラス内

public T[] ToArray()
{
    T[] array = new T[_size];
    Array.Copy(_items, 0, array, 0, _size);
    return array;
}

Array.Resize

使い方

Array.Resize(ref 配列[], 新たなサイズ);
Microsoft docs

Arrayクラス内部コード

System.Arrayクラス内

public static void Resize<T>(ref T[] array, int newSize)
{
    if (newSize < 0)
    {
        throw new ArgumentOutOfRangeException("newSize", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
    }
    T[] array2 = array;
    if (array2 == null)
    {
        array = new T[newSize];
    }
    else if (array2.Length != newSize)
    {
        T[] array3 = new T[newSize];
        Copy(array2, 0, array3, 0, (array2.Length > newSize) ? newSize : array2.Length);
        array = array3;
    }
}

サイズが変わると、増減によらずnew T[]してArray.Copyを呼んでいます。
単純にArray.Copyの計算量が要素数nに比例する（仮にnとおく）とすると、
1要素ずつResizeメソッドで要素を1からnまで増やすと、計算量は1+2+3+...+n = n*(n+1)/2となるので計算量はn^2に比例します。

List.Addの場合のArray.Copyの発生コストを単純計算で考えると、1,2,4,8,16,32,...,n/4,n/2,nのときにArray.Sizeが呼ばれるので¹、その和は2n-1となり、計算量はnに比例するはず（細かいことは考えていないのでちょっと怪しいが）。

結論 (計算量の観点)

1要素ずつ要素数をnまで増やした場合について、単純計算で考えると

• Array.Resizeでは、要素数nの２乗に比例する計算量となる。
• List.Add(と1回のToArray)では、要素数nに比例する計算量となる。

そのため、Listを使うほうが計算量的には優位と判断できる。

■計算量のオーダーついての注意：
実用上のnの範囲では、単純にオーダーだけでは議論できない場合がある。²

1. nが2の指数とし、細かいことは考えない。 ↩

2. マージソート(n*log(n))と挿入ソート(n^2)では、nが小さい場合は挿入ソートのほうが高速とか、多項式時間の素数判定アルゴリズムは現時点の実用上の範囲では遅いとか。（話がそれますが、多項式時間で素数判定できるアルゴリズムが発表されたのは、計算量の理論においては結構有名なできごとだった気がします。） ↩