vaguely

和歌山に戻りました。ふらふらと色々なものに手を出す毎日。

【Unity】【C#】2つのListを見比べて一方にしか存在しないものを検出したい

はじめに

List を検索してガチャガチャやりたい話のメモです。

前提:

  • Id (int型)という共通の要素を持つ2つの List があり、それぞれ searchIds 、 models という名前とする。
  • searchIds の中身は任意で変更できるものとする

やりたいこと:

  • searchIds の中に、 models に含まれない Id を持つものがあれば models にその Id を持つアイテムを追加する
  • models の中に、 searchIds に含まれない Id を持つものがあればそのアイテムを削除する

ベースとなるクラス、変数

searchIds

public 変数とし、 UnityEditor 上から編集 -> ボタンクリックで反映することとします。

public List< int> SearchIds = new List< int> {
    1, 4, 6, 7, 9,
};

models のデータ格納用クラスです。

SampleModel.cs

using UnityEngine;

public class SampleModel: MonoBehaviour {
   public int Id { get; private set; }
   private GameObject model;

   public void Init(int setId, GameObject setModel) {
      Id = setId;
      model = setModel;
   }
   public void DestroyModel() {
      Destroy(model);
      Destroy(gameObject);
   }
}

models

private List models = new List();

ベースのクラス

このクラスの UpdateModels を変更してみて、実行速度や GC Alloc などが変化するかを見てみたいと思います。

ListComparer.cs

using System.Collections.Generic;
using System.Linq;
using UnityEngine;
using UnityEngine.Profiling;
using UnityEngine.UI;

public class ListComparer : MonoBehaviour {
    public GameObject BaseCube;
    public Button UpdateButton;

    public List< int> SearchIds = new List< int> {
        1, 4, 6, 7, 9,
    };
    private List< SampleModel> models = new List< SampleModel>();

    private void Start() {
        UpdateButton.onClick.AddListener(() => {
      // 計測開始.
            Profiler.BeginSample("SamplingProfile");
            UpdateModels();
      // 計測終了.
            Profiler.EndSample();

            Debug.Log("count: " + models.Count);
            models.ForEach(m => Debug.Log("id: " + m.Id));
        });
    }

    private void UpdateModels() {
        foreach (int i in SearchIds) {
      // 本来は else で既存データの値を更新するため、FirstOrDefault で SampleModel を取得する.
            SampleModel target = models.FirstOrDefault(s => s.Id == i);
            if(target == null) {
                models.Add(GenerateModel(i, Instantiate(BaseCube)));
            }
        }

        List< int> removeIndexes = new List< int>();
        for (int i = 0; i < models.Count; i++) {
            int index = i;
            if (SearchIds.Any(s => s == models[index].Id) == false) {
                removeIndexes.Add(index);
            }
        }

        removeIndexes.Sort();

        // Remove していくので逆から実行.
        for (int i = removeIndexes.Count - 1; i >= 0; i--) {
            models[removeIndexes[i]].DestroyModel();
            models.RemoveAt(removeIndexes[i]);
        }
    }
    private SampleModel GenerateModel(int id, GameObject model) {
        SampleModel newModel = new GameObject("Model")
            .AddComponent();
        newModel.Init(id, model);
        return newModel;
    }
}

試す

さて、さっそく思いついたものをいくつか試してみたいと思います。

検証 1. 削除してから追加してみる

ListComparer.cs

~省略~
  private void UpdateModels() {

        List< int> removeIndexes = new List< int>();
        for (int i = 0; i < models.Count; i++) {
            int index = i;
            if (SearchIds.Any(s => s == models[index].Id) == false) {
                removeIndexes.Add(index);
            }
        }
        removeIndexes.Sort();

        // Remove していくので逆から実行.
        for (int i = removeIndexes.Count - 1; i >= 0; i--) {
            models[removeIndexes[i]].DestroyModel();
            models.RemoveAt(removeIndexes[i]);
        }

        foreach (int i in SearchIds) {
            SampleModel target = models.FirstOrDefault(s => s.Id == i);
            if(target == null) {
                models.Add(GenerateModel(i, Instantiate(BaseCube)));
            }
        }
    }
  ~省略~

Profiler で確認した結果は後でまとめて載せますが、ベースのコードとほぼ同じでした。

まぁ順番を変えたぐらいでは特に変化がないですね。

検索するのが追加・削除のどちらか一方のみであれば変化があるかもしれません。

検証 2. 要素の中身を破棄するのと List から Remove するのを分ける

削除対象のインデックスを取得するときに、合わせて要素の中身を削除すると何か変わるでしょうか。

ListComparer.cs

~省略~
  private void UpdateModels() {

        List< int> removeIndexes = new List< int>();
        for (int i = 0; i < models.Count; i++) {
            int index = i;
            if (SearchIds.Any(s => s == models[index].Id) == false) {
        models[index].DestroyModel();
                removeIndexes.Add(index);
            }
        }
        removeIndexes.Sort();

        // Remove していくので逆から実行.
        for (int i = removeIndexes.Count - 1; i >= 0; i--) {
            models.RemoveAt(removeIndexes[i]);
        }

        foreach (int i in SearchIds) {
            SampleModel target = models.FirstOrDefault(s => s.Id == i);
            if(target == null) {
                models.Add(GenerateModel(i, Instantiate(BaseCube)));
            }
        }
    }
  ~省略~

他と比べて初回が遅いですね。

削除する方は特に影響ないはずなのですが。。。

検証 3. Linq をなくしてみる

検証1. のコードから、 Linq を外してみるとどうなるでしょうか。

ListComparer.cs

~省略~
  private void UpdateModels() {
    
    List< int> removeIndexes = new List< int>();
        for (int i = 0; i < models.Count; i++) {
            bool found = false;
            for (int j = 0; j < SearchIds.Count; j++) {
                if (SearchIds[j] == models[i].Id)   {
                    found = true;
                    break;
                }
            }

            if (found == false) {
                removeIndexes.Add(i);
            }
        }

        removeIndexes.Sort();
        
        // Remove していくので逆から実行.
        for (int i = removeIndexes.Count - 1; i >= 0; i--) {
            models[removeIndexes[i]].DestroyModel();
            models.RemoveAt(removeIndexes[i]);
        }

        for (int i = 0; i < SearchIds.Count; i++) {
            bool idFound = false;

            for (int j = 0; j < models.Count; j++) {
                if (models[j].Id == SearchIds[i])   {
                    idFound = true;
                    break;
                }
            }
            // 見つかったものにも処理を行う場合は models[SearchIds[i]] で.
            if (idFound == false)   {
                models.Add(GenerateModel(SearchIds[i], Instantiate(BaseCube)));
            }
    }
  }
  ~省略~

流石というかなんというか、 GC Alloc のサイズが小さくなり、速度も速くなりました。

とはいえ変数の量が増えたりコードが長くなってしまうため、毎フレーム実行しまくるとか高パフォーマンスが要求される場面でなければ避けたい、というのが個人的な本音です(ー_ー;)

検証 4. 検証3. を removeIndexes を作らずに実行してみる

検証3. では、 models が Id 順に揃っていないこともあり、インデックスを持つ List(removeIndexes) を作っていました。

これを作らないで直接 Remove していくと何か変わるでしょうか。

自作クラスのソート

まず models を Id でソートする必要があります。

以前試したときのコードを基に SampleModel をソートできるようにします。

SampleModelComparer.cs

using System.Collections.Generic;

// ソート用のクラス.
public class SampleModelComparer: IComparer< SampleModel> {
    public int Compare(SampleModel x, SampleModel y) {
        if (x == null) {
            return y == null ? 0 : 1;
        }
        if (y == null) {
            return -1;
        }
        return x.Id.CompareTo(y.Id);
    }
}

ListComparer.cs

~省略~
  private SampleModelComparer comparer = new SampleModelComparer();
~省略~
  private void UpdateModels() {
    // Remove していくので逆から実行.
        for (int i = models.Count - 1; i >= 0; i--) {
        bool found = false;
            for (int j = 0; j < SearchIds.Count; j++) {
                if (SearchIds[j] == models[i].Id) {
                    found = true;
                    break;
                }
            }
            if (found == false) {
                models[i].DestroyModel();
                models.RemoveAt(i);
            }
        }   
        for (int i = 0; i < SearchIds.Count; i++) {
            bool idFound = false;
    
            for (int j = 0; j < models.Count; j++) {
                if (models[j].Id == SearchIds[i]) {
                    idFound = true;
                    break;
                }
            }
            // 見つかったものにも処理を行う場合は models[SearchIds[i]] で.
            if (idFound == false) {
                models.Add(GenerateModel(SearchIds[i], Instantiate(BaseCube)));
            }
        }
    // 要素を追加した後にソート.
        models.Sort(comparer.Compare);
  }
  ~省略~

わざわざソート用のクラスを作った割には。。。という悲しい結果となりました。

もし removeIndexes で int 型の Id ではなく、重いデータを持つものを格納していたら違った結果になるかもしれません。

結果

f:id:mslGt:20180916073529p:plain

今回試した中では、検証3. の Linq をなくした場合が一番良い結果となりました。

ただ検証3. でも触れた通り、コードが長くなったり変数が多くなったりして、ミスが発生しやすいという懸念もありますので、状況に合わせて選択したいと思います。

また今回の検証では Linq の方が遅い、という結果になりましたが、もう少し GC Alloc の量が少なかったり、速く処理できるコードも書けるかもしれません。

こちらについてはもう少し良いものが見つかれば追加して比較してみたいと思います。