コガネブログ

平日更新を目標に Unity や C#、Visual Studio、ReSharper などのゲーム開発アレコレを書いていきます

【Unity】配列やリストなどのコレクションの検索速度の検証結果

Unity Unity - 最適化

はじめに

// 配列から Enumerable.First 関数で検索
result = array.First( c => c.Id == id );

// 配列から Array.Find 関数で検索
result = Array.Find( array, c => c.Id == id );

// List 型から Enumerable.First 関数で検索
result = list.First( c => c.Id == id );

// List 型から List.Find 関数で検索
result = list.Find( c => c.Id == id );

// Dictionary 型から Item プロパティで検索
result = dict[ id ];

配列やList、Dictionaryでデータを管理する場合に
どの検索方法が一番高速に目的の値を見つけられるのか気になったので検証してみました

検証結果

int 型を検索のキーにした場合

要素数 3

種類 検索方法 1,000 回 10,000 回 100,000 回
配列 Enumerable.First 関数 0.0005795658 0.004271284 0.057308550
配列 Array.Find 関数 0.0006520133 0.006025381 0.075985970
List 型 Enumerable.First 関数 0.0006136764 0.007729059 0.056947820
List 型 List.Find 関数 0.0004730094 0.002483077 0.034829830
Dictionary 型 Item プロパティ 0.0002357513 0.000731707 0.005586177

要素数 100

種類 検索方法 1,000 回 10,000 回 100,000 回
配列 Enumerable.First 関数 0.0065264590 0.059183370 0.606084500
配列 Array.Find 関数 0.0007105730 0.009019807 0.068646670
List 型 Enumerable.First 関数 0.0047110920 0.051282260 0.479253300
List 型 List.Find 関数 0.0008086748 0.005613847 0.066725310
Dictionary 型 Item プロパティ 0.0002128109 0.000764608 0.005503654

要素数 1,000

種類 検索方法 1,000 回 10,000 回 100,000 回
配列 Enumerable.First 関数 0.0565683800 0.578600400 5.684542000
配列 Array.Find 関数 0.0036986620 0.038125160 0.437770800
List 型 Enumerable.First 関数 0.0467912200 0.441232300 4.453321000
List 型 List.Find 関数 0.0034164020 0.032565220 0.370563000
Dictionary 型 Item プロパティ 0.0002632141 0.000767946 0.005365372

string 型を検索のキーにした場合

要素数 3

種類 検索方法 1,000 回 10,000 回 100,000 回
配列 Enumerable.First 関数 0.0006520133 0.006025381 0.075985970
配列 Array.Find 関数 0.0004953481 0.007307969 0.058195980
List 型 Enumerable.First 関数 0.0005910359 0.009179484 0.081498430
List 型 List.Find 関数 0.0005047061 0.007720864 0.055874410
Dictionary 型 Item プロパティ 0.0004244111 0.002759278 0.032580110

要素数 100

種類 検索方法 1,000 回 10,000 回 100,000 回
配列 Enumerable.First 関数 0.0108221900 0.071493430 0.740682800
配列 Array.Find 関数 0.0016427040 0.018918930 0.172148000
List 型 Enumerable.First 関数 0.0058641840 0.061031950 0.605424900
List 型 List.Find 関数 0.0015983360 0.018354740 0.169441600
Dictionary 型 Item プロパティ 0.0004147515 0.002325932 0.030544040

要素数 1,000

種類 検索方法 1,000 回 10,000 回 100,000 回
配列 Enumerable.First 関数 0.0666090800 0.670052600 6.579340000
配列 Array.Find 関数 0.0121087100 0.116956200 1.161278000
List 型 Enumerable.First 関数 0.0531546800 0.528328200 5.307425000
List 型 List.Find 関数 0.0109483600 0.116275200 1.125834000
Dictionary 型 Item プロパティ 0.0005065203 0.003016088 0.033546450

感想

単純な検索速度は Dictionary の Item プロパティを使用するのが一番高速でした
なので、頻繁に参照するデータを管理する場合や
一意のキーでデータを検索できる場合は Dictionary を使用するのが良さそうです

また、配列や List で条件を指定して検索する場合は Enumerable.First 関数ではなく
Array.Find 関数や List.Find 関数を使用したほうが高速でした

検証用スクリプト

using UnityEngine;
using System.Collections;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class test : MonoBehaviour
{
    public int m_loop_num = 1000;
    public int m_element_num = 100;
    public float m_time = 0.0f;

    enum Jobs
    {
        SOLDIER,    // 王国兵士
        SORCERER,   // 魔法使い
    }

    class Character
    {
        public int      Id;
        public string   Name;
        public Jobs     Job;
        
        public Character(int id, string name, Jobs job)
        {
            Id      = id;
            Name    = name;
            Job     = job;
        }
    }

    void Start () 
    {
        m_time = 0;
        Character result = null;

        var list = new List<Character>{};

        for (int i = 0; i < m_element_num; i++) 
        {
            list.Add (new Character (i, ('a' + i).ToString(), Jobs.SORCERER));
        }

        var array = new Character[m_element_num];

        for (int i = 0; i < m_element_num; i++) 
        {
            array[i] = (new Character (i, ('a' + i).ToString(),Jobs.SOLDIER));
        }
        
        var dict = new Dictionary<int, Character> ();

        for (int i = 0; i < m_element_num; i++) 
        {
            dict[i] = new Character (i, ('a' + i).ToString(),Jobs.SOLDIER);
        }

        var dict_name = new Dictionary<string, Character> ();
        
        for (int i = 0; i < m_element_num; i++) 
        {
            dict_name[('a' + i).ToString()] = new Character (i, ('a' + i).ToString(),Jobs.SOLDIER);
        }

        //first_num------------------------------------------------
        m_time = Time.realtimeSinceStartup;
        for (int i = 0; i < m_loop_num; i++) 
        {
            int num = UnityEngine.Random.Range(0, m_element_num -1);
            result = list.First (c => c.Id == num);
        }
        m_time = Time.realtimeSinceStartup - m_time;
        Debug.Log ("list_first_num  " + m_time);

        //find_num-------------------------------------------------
        m_time = Time.realtimeSinceStartup;
        for (int i = 0; i < m_loop_num; i++) 
        {
            int num = UnityEngine.Random.Range(0, m_element_num -1);
            result = list.Find (c => c.Id == num);
        }
        m_time = Time.realtimeSinceStartup - m_time;
        Debug.Log ("list_find_num  " + m_time);

        //first_name===============================================
        m_time = Time.realtimeSinceStartup;
        for (int i = 0; i < m_loop_num; i++) 
        {
            string name = ('a' + UnityEngine.Random.Range(0, m_element_num -1)).ToString(); 
            result = list.First (c => c.Name == name);
        }
        m_time = Time.realtimeSinceStartup - m_time;
        Debug.Log ("list_first_name  " + m_time);

        //find_name================================================
        m_time = Time.realtimeSinceStartup;
        for (int i = 0; i < m_loop_num; i++) 
        {
            string name = ('a' + UnityEngine.Random.Range(0, m_element_num -1)).ToString(); 
            result = list.Find (c => c.Name == name);
        }
        m_time = Time.realtimeSinceStartup - m_time;
        Debug.Log ("list_find_name  " + m_time);

        //first_num------------------------------------------------
        m_time = Time.realtimeSinceStartup;
        for (int i = 0; i < m_loop_num; i++) 
        {
            int num = UnityEngine.Random.Range(0, m_element_num -1);
            result = array.First (c => c.Id == num);
        }
        m_time = Time.realtimeSinceStartup - m_time;
        Debug.Log ("array_first_num  " + m_time);

        //find_num-------------------------------------------------
        m_time = Time.realtimeSinceStartup;
        for (int i = 0; i < m_loop_num; i++) 
        {
            int num = UnityEngine.Random.Range(0, m_element_num -1);
            result = Array.Find(array, c => c.Id == num);
        }
        m_time = Time.realtimeSinceStartup - m_time;
        Debug.Log ("array_find_num  " + m_time);

        //first_name================================================
        m_time = Time.realtimeSinceStartup;
        for (int i = 0; i < m_loop_num; i++) 
        {
            string name = ('a' + UnityEngine.Random.Range(0, m_element_num -1)).ToString(); 
            result = array.First (c => c.Name == name);
        }
        m_time = Time.realtimeSinceStartup - m_time;
        Debug.Log ("array_first_name  " + m_time);

        //find_name================================================
        m_time = Time.realtimeSinceStartup;
        for (int i = 0; i < m_loop_num; i++) 
        {
            string name = ('a' + UnityEngine.Random.Range(0, m_element_num -1)).ToString(); 
            result = Array.Find(array, c => c.Name == name);
        }
        m_time = Time.realtimeSinceStartup - m_time;
        Debug.Log ("array_find_name  " + m_time);

        //Dictionary_num--------------------------------------------
        m_time = Time.realtimeSinceStartup;
        for (int i = 0; i < m_loop_num; i++) 
        {
            result = dict[UnityEngine.Random.Range(0, m_element_num)];
        }
        m_time = Time.realtimeSinceStartup - m_time;
        Debug.Log ("Dictionary_num  " + m_time);

        //Dictionary_name===========================================
        m_time = Time.realtimeSinceStartup;
        for (int i = 0; i < m_loop_num; i++) 
        {
            result = dict_name[('a' + UnityEngine.Random.Range(0, m_element_num)).ToString()];
        }
        m_time = Time.realtimeSinceStartup - m_time;
        Debug.Log ("Dictionary_name  " + m_time);
    }
}

関連記事