【Unity】【C#】Listから要素を削除・挿入する処理は重いよって話とその解決策

C#でListから要素を削除や挿入する処理は重いよって話とその解決策をまとめました。

Listから要素を削除する処理は重い
どのくらい重いのか試してみる
並び順を気にしなくて良いのであれば入れ替えてから末尾を削除
参照には弱いけど挿入と削除に強いLinkedList
挿入にも同じことが言える
まとめ
参考

Unity2019.1.10

Listから要素を削除する処理は重い

List.RemoveAt(index)を使うと指定したindexの要素を削除できます。
この処理は結構頻繁に使われがちですが、実は重いです。
正確に言うと、より先頭に近い要素を削除したときに重いです。

しかしindexを指定しているので、検索のための処理に時間はかからないはずです。
それでは何が重いのでしょうか?

実は、Listではあるindexの要素を削除するとそれ以降の要素を一つずつコピーして詰めていきます。

f:id:halya_11:20191014211327p:plain

このコピーの対象が多くなれば多くなるほど重くなります。
先頭に近い要素を削除するとコピー処理をしなければならない要素が多くなるので重くなるというわけです。

計算量として表すと、O(n) ただし nはCount - indexとなります。

ちなみにこの処理は.Netのソースコードを見るとよくわかります。

referencesource.microsoft.com

どのくらい重いのか試してみる

それでは実際にどれくらい重いのか計測してみます。
以下のコードでは100000個の要素を持つリストを二つ生成し、片方は前から、他方は後ろから要素を削除しています。

using System.Collections.Generic;
using UnityEngine;

public class Example : MonoBehaviour
{
    private void Start()
    {
        var list1 = CreateList();
        var list2 = CreateList();

        var stopwatch = new System.Diagnostics.Stopwatch();

        // 後ろから消す
        stopwatch.Start();
        for (int i = 0; i < list1.Count; i++) {
            list1.RemoveAt(list1.Count - 1);
        }
        Debug.Log(stopwatch.Elapsed);

        // 前から消す
        stopwatch.Restart();
        for (int i = 0; i < list2.Count; i++) {
            list2.RemoveAt(0);
        }
        Debug.Log(stopwatch.Elapsed);
    }

    private List<int> CreateList()
    {
        var result = new List<int>(100000);
        for (int i = 0; i < 100000; i++) {
            result.Add(i);
        }
        return result;
    }
}

計測結果は以下の通りとなりました。

削除方法	計測結果(ms)
前から	3129
後ろから	10

後ろから削除した場合にはコピーが発生しないのであまり時間はかかっていません。
それに比べて前から削除するとかなり重い処理になっていることがわかります。

ちなみに明らかに有意な差ががあるので計測はざっくり一回のみです。
正確な計測結果が欲しい方はご自身で計測してください。

並び順を気にしなくて良いのであれば入れ替えてから末尾を削除

さてじゃあ要素を削除したい場合にはどうすればいいのでしょうか？

要素の並び順が変わってもいい状況であれば、以下のような手段が考えられます。

消したい要素と末尾の要素を入れ替える
末尾の要素を削除する

これでどの要素を削除する際にも末尾から削除が行われるので大量のコピーは発生しないはずです。
ソースコードを書いて試してみます。

using System.Collections.Generic;
using UnityEngine;

public class Example : MonoBehaviour
{
    private void Start()
    {
        var list1 = CreateList();
        var list2 = CreateList();
        var stopwatch = new System.Diagnostics.Stopwatch();

        // 普通に削除
        stopwatch.Start();
        for (int i = 0; i < list1.Count; i++) {
            var targetIndex = Random.Range(0, list1.Count - 1);
            list1.RemoveAt(targetIndex);
        }
        Debug.Log(stopwatch.Elapsed);

        // 一番最後の要素をコピーしてから一番最後の要素を消す
        stopwatch.Restart();
        for (int i = 0; i < list2.Count; i++) {
            var targetIndex = Random.Range(0, list2.Count - 1);
            // 消したいindexに一番最後の要素を移す
            list2[targetIndex] = list2[list2.Count - 1];
            // 一番最後の要素を削除
            list2.RemoveAt(list2.Count - 1);
        }
        Debug.Log(stopwatch.Elapsed);
    }

    private List<int> CreateList()
    {
        var result = new List<int>(100000);
        for (int i = 0; i < 100000; i++) {
            result.Add(i);
        }
        return result;
    }
}

計測結果は以下の通りとなりました。

削除方法	計測結果(ms)
普通に削除	1518
末尾の要素をコピーしてから末尾を削除	36

普通に削除した場合に比べてかなり効果があることが見て取れます。
乱数によって計測結果はブレますが、有意な差があることがわかればOKです。

参照には弱いけど挿入と削除に強いLinkedList

また、要素の挿入や削除を頻繁に行う場合にはLinkedListを使うことも有効です。
これはデータ型として連結リストが使われており、挿入や削除を行った時にコピーが発生しません。

その代わりListのようにindexを指定して要素を参照することができないため一度Listに変換したりする必要があります。
挿入や削除を大量に行って、参照はたまに行うような用途に向いています。

それではLinkedListの処理負荷もコードを書いて検証してみます。

using System.Collections.Generic;
using UnityEngine;

public class Example : MonoBehaviour
{
    private void Start()
    {
        var list1 = CreateList();
        var list2 = CreateLinkedList();
        var stopwatch = new System.Diagnostics.Stopwatch();

        // List
        stopwatch.Start();
        for (int i = 0; i < list1.Count; i++) {
            list1.RemoveAt(0);
        }
        Debug.Log(stopwatch.Elapsed);

        // LinkedList
        stopwatch.Restart();
        for (int i = 0; i < list2.Count; i++) {
            list2.RemoveFirst();
        }
        Debug.Log(stopwatch.Elapsed);
    }

    private List<int> CreateList()
    {
        var result = new List<int>(100000);
        for (int i = 0; i < 100000; i++) {
            result.Add(i);
        }
        return result;
    }

    private LinkedList<int> CreateLinkedList()
    {
        var result = new LinkedList<int>();
        for (int i = 0; i < 100000; i++) {
            result.AddLast(i);
        }
        return result;
    }
}