C# 解決在Dictionary中使用枚舉的效率問題

使用字典的好處

System.Collections.Generic命名空間下的Dictionary,它的功能非常好用,且功能與現實中的字典是一樣的。

它同樣擁有目錄和正文,目錄用來進行第一次的粗略查找,正文進行第二次精確查找。通過將數據進行分組,形成目錄,正文則是分組後的結果。它是一種空間換時間的方式,犧牲大的內存換取高效的查詢效率。所以,功能使用率查詢>新增時優先考慮字典。

        public static Tvalue DicTool<Tkey, Tvalue>(Tkey key, Dictionary<Tkey, Tvalue> dic)
        {
            return dic.TryGetValue(key, out Tvalue _value) ? _value : (Tvalue)default;
        }
           Stopwatch stopwatch = Stopwatch.StartNew();
            for (int i = 0; i < 1; i++)
            {
                DicTool(0, Dic);
            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);

執行時間00:00:00.0003135

            Stopwatch stopwatch = Stopwatch.StartNew();
            for (int i = 0; i < 10000; i++)
            {
                DicTool(0, Dic);
            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);

執行時間00:00:00.0005091

從上面可以看出,它進行大量查詢時的用時非常短,查詢效率極高。但使用時需要避免使用枚舉作為關鍵詞進行查詢;它會造成查詢效率降低。

使用枚舉作為key時查詢效率變低

 Stopwatch stopwatch = Stopwatch.StartNew();
            for (int i = 0; i < 10000; i++)
            {
                DicTool(MyEnum.one, Dic);
            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);

執行時間00:00:00.0011010

從這裡的執行時間可以看出,查詢效率大大降低。

優化方案: 使用int代替enum,enum強制轉型後間接查詢;可使查詢效率與非枚舉的直接查詢相近。(還有其他的優化方案,個人隻使用過這個)

using System;
using System.Diagnostics;
using System.Collections.Generic;
namespace Test
{
    public class Program
    {
        public enum MyEnum : int
        {
            one,
            two,
            three
        }
        public static void Main(string[] args)
        {
            Dictionary<int, int> Dic = new Dictionary<int, int>()
            {
                { (int)MyEnum.one,1},
                { (int)MyEnum.two,2},
                { (int)MyEnum.three,3}
            };
            Stopwatch stopwatch = Stopwatch.StartNew();
            for (int i = 0; i < 10000; i++)
            {
                DicTool((int)MyEnum.one, Dic);
            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);
        }
        public static Tvalue DicTool<Tkey, Tvalue>(Tkey key, Dictionary<Tkey, Tvalue> dic)
        {
            return dic.TryGetValue(key, out Tvalue _value) ? _value : (Tvalue)default;
        }
    }
}

執行時間 00:00:00.0005005

為什麼使用枚舉會降低效率

使用ILSpy軟件反編譯源碼,得到以下:

public bool TryGetValue(TKey key, out TValue value)
{
    int num = this.FindEntry(key);
    if (num >= 0)
    {
        value = this.entries[num].value;
        return true;
    }
    value = default(TValue);
    return false;
}
private int FindEntry(TKey key)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    if (this.buckets != null)
    {
        int num = this.comparer.GetHashCode(key) & 2147483647;
        for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next)
        {
            if (this.entries[i].hashCode == num && this.comparer.Equals(this.entries[i].key, key))
            {
                return i;
            }
        }
    }
    return -1;
}

查看Dictionary源碼後可以知道,效率減低來源於this.comparer.GetHashCode(key) 這段代碼。

comparer是使用瞭泛型的成員,它內部使用int類型不會發生裝箱,但是由於Enum沒有IEquatable接口,內部運行時會引起裝箱行為,該行為降低瞭查詢的效率。

IEquatable源碼:

namespace System
{
 [__DynamicallyInvokable]
 public interface IEquatable<T>
 {
  [__DynamicallyInvokable]
  bool Equals(T other);
 }
}

裝箱:值類型轉換為引用類型(隱式轉換)

把數據從棧復制到托管堆中,棧中改為存儲數據地址。

拆箱:引用類型轉換為值類型(顯式轉換)

補充:C#中Dictionary<Key,Value>中[]操作的效率問題

今天有朋友問到如果一個Dictionary<Key,Value>中如果數據量很大時,那麼[ ]操作會不會效率很低。

感謝微軟開源C#,讓我們有機會通過代碼驗證自己的猜想。

此處是微軟C#的源代碼地址

先上結論:Dictionary<Key,Value>的[ ]操作的時間 = 一次調用GetHashCode + n次調用Key.Equals的時間之和。

期中n受傳入的key的GetHashCode 的重復率影響,比如傳入的key的hash值為5,Dictionary中hash值為5的值有100個,這100值相當於用鏈表存儲,如果要查找的值在第20個那麼n的值就是19。如果GetHashCode 基本沒什麼重復率,那麼n始終1,極端情況下n可能為一個很大的數(參考測試代碼)。

C#中的關鍵代碼如下:

 int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;

同時在這裡我想說一下Dictionary<Key,Value>類中數據的組織結構:

        private struct Entry {
            public int hashCode;    // Lower 31 bits of hash code, -1 if unused
            public int next;        // Index of next entry, -1 if last
            public TKey key;           // Key of entry
            public TValue value;         // Value of entry
        } 
        private int[] buckets;
        private Entry[] entries;

期中buckets是保存所有的相同hash值的Entry的鏈表頭,而相同hash值的Entry是通過Entry .next連接起來的。在新加入的Value時,如果已經存在相同hash值會將buckets中的值更新,如果不存在則會加入新的值,關鍵代碼如下:

            entries[index].hashCode = hashCode;
            entries[index].next = buckets[targetBucket];
            entries[index].key = key;
            entries[index].value = value;
            buckets[targetBucket] = index;

註意最後一句,將新加入值的下標inddex的值賦值給瞭buckets,這樣相當於就更新瞭鏈表頭指針。這個鏈表就是前面產生n的原因。

下面我放一些測試的結果:

當GetHashCode的消耗為1ms時:

當GetHashCode的消耗為100ms時:

增加的消耗是99ms也就是GetHashCode增加的消耗,後面的尾數就是上面公式裡的n。

附測試代碼如下:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading; 
namespace ConsoleApplication1
{
    class Program
    {
        public class Test1
        {
            private ushort num = 0;
            public Test1(ushort a)
            {
                num = a;
            }
 
            public override int GetHashCode()
            {
                Thread.Sleep(1);
                return num / 100;
            }
 
            public override bool Equals(object obj)
            {
                Thread.Sleep(1);
                return num.Equals((obj as Test1).num);
            }
        }
 
        static void Main(string[] args)
        {
            Dictionary<Test1, string> testDic = new Dictionary<Test1, string>();
            for (ushort a = 0; a < 100; a++)
            {
                Test1 temp = new Test1(a);
                testDic.Add(temp, a.ToString());
            }
 
            Stopwatch stopWatch = new Stopwatch();
            string str = "";
 
            stopWatch.Start();
            str = testDic[new Test1(99)];
            stopWatch.Stop();
            Console.WriteLine("num = " + str +" pass Time = " + stopWatch.ElapsedMilliseconds);
 
            stopWatch.Restart();
            str = testDic[new Test1(1)];
            stopWatch.Stop();
            Console.WriteLine("num = " + str + " pass Time = " + stopWatch.ElapsedMilliseconds);
 
            stopWatch.Restart();
            str = testDic[new Test1(50)];
            stopWatch.Stop();
            Console.WriteLine("num = " + str + " pass Time = " + stopWatch.ElapsedMilliseconds);
 
            stopWatch.Restart();
            str = testDic[new Test1(98)];
            stopWatch.Stop();
            Console.WriteLine("num = " + str + " pass Time = " + stopWatch.ElapsedMilliseconds);
 
            stopWatch.Restart();
            str = testDic[new Test1(97)];
            stopWatch.Stop();
            Console.WriteLine("num = " + str + " pass Time = " + stopWatch.ElapsedMilliseconds);
        }
    }
}

以上為個人經驗,希望能給大傢一個參考,也希望大傢多多支持WalkonNet。如有錯誤或未考慮完全的地方,望不吝賜教。

推薦閱讀:

    None Found