什么更有效:字典TryGetValue或ContainsKey + Item？

Question

从MSDN上的Dictionary.TryGetValue方法入口:

此方法结合了ContainsKey方法和Item属性的功能.

如果未找到密钥,则value参数将获取值类型TValue的相应默认值; 例如,0(零)表示整数类型,false表示布尔类型,null表示引用类型.

如果您的代码经常尝试访问不在字典中的键,请使用TryGetValue方法.使用此方法比捕获Item属性抛出的KeyNotFoundException更有效.

该方法接近O(1)操作.

从描述中,不清楚它是否比调用ContainsKey然后进行查找更有效或更方便.TryGetValue通过执行单个查找,只调用ContainsKey然后调用Item或实际上是否更有效？

换句话说,什么是更有效(即哪一个执行更少的查找):

Dictionary<int,int> dict;
//...//
int ival;
if(dict.ContainsKey(ikey))
{
  ival = dict[ikey];
}
else
{
  ival = default(int);
}

要么

Dictionary<int,int> dict;
//...//
int ival;
dict.TryGetValue(ikey, out ival);

注意:我不是在寻找基准!

Answer 1

TryGetValue 会更快.

ContainsKey使用相同的检查TryGetValue,内部指的是实际的输入位置.该Item属性实际上具有几乎相同的代码功能TryGetValue,除了它将抛出异常而不是返回false.

使用ContainsKey后跟Item基本上复制查找功能,这是本例中的大部分计算.

Answer 2

一个快速的基准显示TryGetValue有一点点优势:

    static void Main() {
        var d = new Dictionary<string, string> {{"a", "b"}};
        var start = DateTime.Now;
        for (int i = 0; i != 10000000; i++) {
            string x;
            if (!d.TryGetValue("a", out x)) throw new ApplicationException("Oops");
            if (d.TryGetValue("b", out x)) throw new ApplicationException("Oops");
        }
        Console.WriteLine(DateTime.Now-start);
        start = DateTime.Now;
        for (int i = 0; i != 10000000; i++) {
            string x;
            if (d.ContainsKey("a")) {
                x = d["a"];
            } else {
                x = default(string);
            }
            if (d.ContainsKey("b")) {
                x = d["b"];
            } else {
                x = default(string);
            }
        }
   }

这产生了

00:00:00.7600000
00:00:01.0610000

ContainsKey + Item假设命中和未命中的混合均匀,使访问速度降低约40%.

此外,当我将程序更改为始终未命中(即始终查找"b")时,两个版本变得同样快:

00:00:00.2850000
00:00:00.2720000

然而,当我把它"全部命中"时,它TryGetValue仍然是一个明显的赢家:

00:00:00.4930000
00:00:00.8110000

Answer 3

由于到目前为止没有一个答案真正回答了这个问题,所以这是我在一些研究后发现的可接受的答案:

如果您反编译TryGetValue,您会看到它正在执行此操作:

public bool TryGetValue(TKey key, out TValue value)
{
  int index = this.FindEntry(key);
  if (index >= 0)
  {
    value = this.entries[index].value;
    return true;
  }
  value = default(TValue);
  return false;
}

而ContainsKey方法是:

public bool ContainsKey(TKey key)
{
  return (this.FindEntry(key) >= 0);
}

因此,如果项目存在,TryGetValue只是ContainsKey加上数组查找.

资源

似乎TryGetValue的速度几乎是ContainsKey + Item组合的两倍.

Answer 4

谁在乎 :-)

你可能会问,因为TryGetValue使用起来很痛苦 - 所以用扩展方法将它封装起来.

public static class CollectionUtils
{
    // my original method
    // public static V GetValueOrDefault<K, V>(this Dictionary<K, V> dic, K key)
    // {
    //    V ret;
    //    bool found = dic.TryGetValue(key, out ret);
    //    if (found)
    //    {
    //        return ret;
    //    }
    //    return default(V);
    // }


    // EDIT: one of many possible improved versions
    public static TValue GetValueOrDefault<K, V>(this IDictionary<K, V> dictionary, K key)
    {
        // initialized to default value (such as 0 or null depending upon type of TValue)
        TValue value;  

        // attempt to get the value of the key from the dictionary
        dictionary.TryGetValue(key, out value);
        return value;
    }

然后打电话:

dict.GetValueOrDefault("keyname")

要么

(dict.GetValueOrDefault("keyname") ?? fallbackValue) 

Answer 5

你为什么不测试它？

但我很确定它TryGetValue更快,因为它只进行一次查找.当然,这不能保证,即不同的实现可能具有不同的性能特征.

我实现字典的方法是创建一个内部Find函数来查找项目的插槽,然后在其上构建其余部分.

Answer 6

到目前为止,所有的答案虽然很好,却错过了一个重要的观点.

API类(例如.NET框架)中的方法构成了接口定义的一部分(不是C#或VB接口,而是计算机科学中的接口).

因此,询问调用这样的方法是否更快是不正确的,除非速度是正式接口定义的一部分(在这种情况下不是这样).

传统上,无论语言,基础设施,操作系统,平台或机器架构如何,这种快捷方式(组合搜索和检索)都更有效.它也更具可读性,因为它明确地表达了你的意图,而不是暗示它(来自你的代码结构).

所以答案(来自一个头发花白的老黑客)绝对是'是'(TryGetValue比ContainsKey和Item [Get]的组合更可取从Dictionary中检索一个值).

如果您认为这听起来很奇怪,请按照以下方式思考:即使TryGetValue,ContainsKey和Item [Get]的当前实现没有产生任何速度差异,您也可以假设它可能是未来的实现(例如.NET v5)会做(TryGetValue会更快).考虑一下软件的生命周期.

另外,值得注意的是,典型的现代接口定义技术仍然很少提供正式定义时序约束的任何方法.也许.NET v5？

Answer 7

除了设计一个在实际设置中给出准确结果的微基准之外，您还可以检查 .NET Framework 的参考源。

• System.Collections.Generic.Dictionary<TKey, TValue>.TryGetValue(TKey, out TValue)
• System.Collections.Generic.Dictionary<TKey, TValue>.ContainsKey(TKey)
• System.Collections.Generic.Dictionary<TKey, TValue>.Item(TKey)

它们都调用FindEntry(TKey)完成大部分工作并且不记忆其结果的方法，因此调用速度几乎是+TryGetValue的两倍ContainsKeyItem。

不方便的接口TryGetValue可以使用扩展方法进行调整：

using System.Collections.Generic;

namespace Project.Common.Extensions
{
    public static class DictionaryExtensions
    {
        public static TValue GetValueOrDefault<TKey, TValue>(
            this IDictionary<TKey, TValue> dictionary,
            TKey key,
            TValue defaultValue = default(TValue))
        {
            if (dictionary.TryGetValue(key, out TValue value))
            {
                return value;
            }
            return defaultValue;
        }
    }
}

^{从 C# 7.1 开始，您可以替换default(TValue)为普通的default. 类型被推断出来。}

用法：

var dict = new Dictionary<string, string>();
string val = dict.GetValueOrDefault("theKey", "value used if theKey is not found in dict");

它返回null查找失败的引用类型，除非指定了显式默认值。

var dictObj = new Dictionary<string, object>();
object valObj = dictObj.GetValueOrDefault("nonexistent");
Debug.Assert(valObj == null);

var dictInt = new Dictionary<string, int>();
int valInt = dictInt.GetValueOrDefault("nonexistent");
Debug.Assert(valInt == 0);

Answer 8

在我的机器上，如果在 RELEASE 模式（不是 DEBUG）下运行，有大量 RAM，则ContainsKey等于TryGetValue/try-catch如果Dictionary<>找到了中的所有条目。

ContainsKey到目前为止，当只有几个字典条目未找到时（在我下面的示例中，设置MAXVAL为大于ENTRIES丢失某些条目的任何值）时，它们的表现都优于它们：

结果：

Finished evaluation .... Time distribution:
Size: 000010: TryGetValue: 53,24%, ContainsKey: 1,74%, try-catch: 45,01% - Total: 2.006,00
Size: 000020: TryGetValue: 37,66%, ContainsKey: 0,53%, try-catch: 61,81% - Total: 2.443,00
Size: 000040: TryGetValue: 22,02%, ContainsKey: 0,73%, try-catch: 77,25% - Total: 7.147,00
Size: 000080: TryGetValue: 31,46%, ContainsKey: 0,42%, try-catch: 68,12% - Total: 17.793,00
Size: 000160: TryGetValue: 33,66%, ContainsKey: 0,37%, try-catch: 65,97% - Total: 36.840,00
Size: 000320: TryGetValue: 34,53%, ContainsKey: 0,39%, try-catch: 65,09% - Total: 71.059,00
Size: 000640: TryGetValue: 32,91%, ContainsKey: 0,32%, try-catch: 66,77% - Total: 141.789,00
Size: 001280: TryGetValue: 39,02%, ContainsKey: 0,35%, try-catch: 60,64% - Total: 244.657,00
Size: 002560: TryGetValue: 35,48%, ContainsKey: 0,19%, try-catch: 64,33% - Total: 420.121,00
Size: 005120: TryGetValue: 43,41%, ContainsKey: 0,24%, try-catch: 56,34% - Total: 625.969,00
Size: 010240: TryGetValue: 29,64%, ContainsKey: 0,61%, try-catch: 69,75% - Total: 1.197.242,00
Size: 020480: TryGetValue: 35,14%, ContainsKey: 0,53%, try-catch: 64,33% - Total: 2.405.821,00
Size: 040960: TryGetValue: 37,28%, ContainsKey: 0,24%, try-catch: 62,48% - Total: 4.200.839,00
Size: 081920: TryGetValue: 29,68%, ContainsKey: 0,54%, try-catch: 69,77% - Total: 8.980.230,00

这是我的代码：

    using System;
    using System.Collections.Generic;
    using System.Diagnostics;

    namespace ConsoleApplication1
    {
        class Program
        {
            static void Main(string[] args)
            {
                const int ENTRIES = 10000, MAXVAL = 15000, TRIALS = 100000, MULTIPLIER = 2;
                Dictionary<int, int> values = new Dictionary<int, int>();
                Random r = new Random();
                int[] lookups = new int[TRIALS];
                int val;
                List<Tuple<long, long, long>> durations = new List<Tuple<long, long, long>>(8);

                for (int i = 0;i < ENTRIES;++i) try
                    {
                        values.Add(r.Next(MAXVAL), r.Next());
                    }
                    catch { --i; }

                for (int i = 0;i < TRIALS;++i) lookups[i] = r.Next(MAXVAL);

                Stopwatch sw = new Stopwatch();
                ConsoleColor bu = Console.ForegroundColor;

                for (int size = 10;size <= TRIALS;size *= MULTIPLIER)
                {
                    long a, b, c;

                    Console.ForegroundColor = ConsoleColor.Yellow;
                    Console.WriteLine("Loop size: {0}", size);
                    Console.ForegroundColor = bu;

                    // ---------------------------------------------------------------------
                    sw.Start();
                    for (int i = 0;i < size;++i) values.TryGetValue(lookups[i], out val);
                    sw.Stop();
                    Console.WriteLine("TryGetValue: {0}", a = sw.ElapsedTicks);

                    // ---------------------------------------------------------------------
                    sw.Restart();
                    for (int i = 0;i < size;++i) val = values.ContainsKey(lookups[i]) ? values[lookups[i]] : default(int);
                    sw.Stop();
                    Console.WriteLine("ContainsKey: {0}", b = sw.ElapsedTicks);

                    // ---------------------------------------------------------------------
                    sw.Restart();
                    for (int i = 0;i < size;++i)
                        try { val = values[lookups[i]]; }
                        catch { }
                    sw.Stop();
                    Console.WriteLine("try-catch: {0}", c = sw.ElapsedTicks);

                    // ---------------------------------------------------------------------
                    Console.WriteLine();

                    durations.Add(new Tuple<long, long, long>(a, b, c));
                }

                Console.ForegroundColor = ConsoleColor.Yellow;
                Console.WriteLine("Finished evaluation .... Time distribution:");
                Console.ForegroundColor = bu;

                val = 10;
                foreach (Tuple<long, long, long> d in durations)
                {
                    long sum = d.Item1 + d.Item2 + d.Item3;

                    Console.WriteLine("Size: {0:D6}:", val);
                    Console.WriteLine("TryGetValue: {0:P2}, ContainsKey: {1:P2}, try-catch: {2:P2} - Total: {3:N}", (decimal)d.Item1 / sum, (decimal)d.Item2 / sum, (decimal)d.Item3 / sum, sum);
                    val *= MULTIPLIER;
                }

                Console.WriteLine();
            }
        }
    }

Answer 9

制作一个快速测试程序,使用TryGetValue和字典中的100万个项目肯定会有所改进.

结果:

ContainsKey +项目1000000次点击:45ms

TryGetValue为1000000次点击:26ms

这是测试应用程序:

static void Main(string[] args)
{
    const int size = 1000000;

    var dict = new Dictionary<int, string>();

    for (int i = 0; i < size; i++)
    {
        dict.Add(i, i.ToString());
    }

    var sw = new Stopwatch();
    string result;

    sw.Start();

    for (int i = 0; i < size; i++)
    {
        if (dict.ContainsKey(i))
            result = dict[i];
    }

    sw.Stop();
    Console.WriteLine("ContainsKey + Item for {0} hits: {1}ms", size, sw.ElapsedMilliseconds);

    sw.Reset();
    sw.Start();

    for (int i = 0; i < size; i++)
    {
        dict.TryGetValue(i, out result);
    }

    sw.Stop();
    Console.WriteLine("TryGetValue for {0} hits: {1}ms", size, sw.ElapsedMilliseconds);

}