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

更新時(shí)間：2021年04月10日 10:14:12 作者：TIMIZ

這篇文章主要介紹了C# 解決在Dictionary中使用枚舉的效率問題，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧

使用字典的好處

System.Collections.Generic命名空間下的Dictionary，它的功能非常好用，且功能與現(xiàn)實(shí)中的字典是一樣的。

它同樣擁有目錄和正文，目錄用來進(jìn)行第一次的粗略查找，正文進(jìn)行第二次精確查找。通過將數(shù)據(jù)進(jìn)行分組，形成目錄，正文則是分組后的結(jié)果。它是一種空間換時(shí)間的方式，犧牲大的內(nèi)存換取高效的查詢效率。所以，功能使用率查詢>新增時(shí)優(yōu)先考慮字典。

        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);

執(zhí)行時(shí)間00:00:00.0003135

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

執(zhí)行時(shí)間00:00:00.0005091

從上面可以看出，它進(jìn)行大量查詢時(shí)的用時(shí)非常短，查詢效率極高。但使用時(shí)需要避免使用枚舉作為關(guān)鍵詞進(jìn)行查詢；它會(huì)造成查詢效率降低。

使用枚舉作為key時(shí)查詢效率變低

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

執(zhí)行時(shí)間00:00:00.0011010

從這里的執(zhí)行時(shí)間可以看出，查詢效率大大降低。

優(yōu)化方案：使用int代替enum，enum強(qiáng)制轉(zhuǎn)型后間接查詢；可使查詢效率與非枚舉的直接查詢相近。（還有其他的優(yōu)化方案，個(gè)人只使用過這個(gè)）

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;
        }
    }
}

執(zhí)行時(shí)間 00:00:00.0005005

為什么使用枚舉會(huì)降低效率

使用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是使用了泛型的成員，它內(nèi)部使用int類型不會(huì)發(fā)生裝箱，但是由于Enum沒有IEquatable接口，內(nèi)部運(yùn)行時(shí)會(huì)引起裝箱行為，該行為降低了查詢的效率。

IEquatable源碼：

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

裝箱：值類型轉(zhuǎn)換為引用類型（隱式轉(zhuǎn)換）

把數(shù)據(jù)從棧復(fù)制到托管堆中，棧中改為存儲(chǔ)數(shù)據(jù)地址。

拆箱：引用類型轉(zhuǎn)換為值類型（顯式轉(zhuǎn)換）

補(bǔ)充：C#中Dictionary<Key,Value>中[]操作的效率問題

今天有朋友問到如果一個(gè)Dictionary<Key,Value>中如果數(shù)據(jù)量很大時(shí)，那么[ ]操作會(huì)不會(huì)效率很低。

感謝微軟開源C#,讓我們有機(jī)會(huì)通過代碼驗(yàn)證自己的猜想。

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

先上結(jié)論：Dictionary<Key,Value>的[ ]操作的時(shí)間 = 一次調(diào)用GetHashCode + n次調(diào)用Key.Equals的時(shí)間之和。

期中n受傳入的key的GetHashCode 的重復(fù)率影響，比如傳入的key的hash值為5，Dictionary中hash值為5的值有100個(gè)，這100值相當(dāng)于用鏈表存儲(chǔ)，如果要查找的值在第20個(gè)那么n的值就是19。如果GetHashCode 基本沒什么重復(fù)率，那么n始終1，極端情況下n可能為一個(gè)很大的數(shù)（參考測試代碼）。

C#中的關(guān)鍵代碼如下：

 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;

同時(shí)在這里我想說一下Dictionary<Key,Value>類中數(shù)據(jù)的組織結(jié)構(gòu)：

        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時(shí)，如果已經(jīng)存在相同hash值會(huì)將buckets中的值更新，如果不存在則會(huì)加入新的值，關(guān)鍵代碼如下：

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

注意最后一句，將新加入值的下標(biāo)inddex的值賦值給了buckets，這樣相當(dāng)于就更新了鏈表頭指針。這個(gè)鏈表就是前面產(chǎn)生n的原因。

下面我放一些測試的結(jié)果：

當(dāng)GetHashCode的消耗為1ms時(shí)：

當(dāng)GetHashCode的消耗為100ms時(shí)：

增加的消耗是99ms也就是GetHashCode增加的消耗，后面的尾數(shù)就是上面公式里的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);
        }
    }
}

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教。

您可能感興趣的文章: