【C#】ループの最適化手法 ②List<T>編 ～List<T>はSpan<T>化すると数倍早い～ - Qiita

List<T> のしくみ 以下の説明で、List<T> というか可変長の配列リストというものがどういう仕組みなのか知っていないと困るので簡単に説明します。知っている人は読み飛ばしてください。 List<T> クラスは配列をフィールドとして保持しており、これが List<T> の中身です。そして、要素を追加するときにこの配列を拡張します。 ただし、拡張するとはいっても配列の長さを伸ばすことはできません。実際には、より長い新しい配列を確保して、もともとの配列から要素をすべてコピーして再代入しています。 ここで問題になるのがこの拡張操作のコストです。長さが n のとき、長さ 2n の配列を確保して n 個の要素をコピーするので、これは計算量が O(n) の操作になります。 要素を追加するたびに O(n) かかるとたまったものではないので、ある程度まとめて拡張することを考えます。 ここで、「足りな