Что является более эффективным: словарь TryGetValue или ContainsKey + Item?

Из записи MSDN о методе Dictionary.TryGetValue :

Этот метод объединяет функциональность метода ContainsKey и свойства Item.

Если ключ не найден, параметр value получает соответствующее значение по умолчанию для типа значения TValue; например, 0 (ноль) для целочисленных типов, false для логических типов и null для ссылочных типов.

Используйте метод TryGetValue, если ваш код часто пытается получить доступ к ключам, которых нет в словаре. Использование этого метода более эффективно, чем перехват KeyNotFoundException, генерируемого свойством Item.

Этот метод приближается к операции 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);

Примечание: я не ищу эталон!

TryGetValue будет быстрее

ContainsKeyиспользует ту же проверку TryGetValue, что и внутренне относится к фактическому месту входа. ItemСвойство на самом деле имеет почти идентичную функциональность кода , как TryGetValue, за исключением того, что он будет бросать исключение вместо возвращения ЛЖИ.

Использование с ContainsKeyпоследующим в Itemосновном дублирует функциональность поиска, которая является основной частью вычислений в этом случае.

Быстрый тест показывает, что 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

Поскольку ни один из ответов до сих пор фактически не отвечает на вопрос, вот приемлемый ответ, который я нашел после некоторого исследования:

Если вы декомпилируете 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.

Какая разница :-)

Вы, вероятно, спрашиваете, потому что 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) 

Почему бы тебе не проверить это?

Но я уверен, что TryGetValueэто быстрее, потому что это только один поиск. Конечно, это не гарантируется, то есть разные реализации могут иметь разные характеристики производительности.

Я бы реализовал словарь, создав внутреннюю Findфункцию, которая находит слот для элемента, а затем строит остальное поверх этого.

Все ответы до сих пор, хотя и хорошие, упускают важный момент.

Методы в классах API (например, платформа .NET) образуют часть определения интерфейса (не интерфейс C # или VB, а интерфейс в смысле информатики).

Таким образом, обычно некорректно спрашивать, является ли вызов такого метода более быстрым, если только скорость не является частью формального определения интерфейса (в данном случае это не так).

Традиционно этот вид ярлыков (совмещающий поиск и извлечение) более эффективен независимо от языка, инфраструктуры, ОС, платформы или архитектуры компьютера. Это также более читабельно, потому что оно выражает ваше намерение явно, а не подразумевает его (из структуры вашего кода).

Таким образом, ответ (от старого хака) определенно «Да» (TryGetValue предпочтительнее комбинации ContainsKey и Item [Get] для получения значения из словаря).

Если вы думаете, что это звучит странно, подумайте об этом так: даже если текущие реализации TryGetValue, ContainsKey и Item [Get] не дают никакой разницы в скорости, вы можете предположить, что вполне вероятно, что будущая реализация (например, .NET v5) будет делать (TryGetValue будет быстрее). Подумайте о времени жизни вашего программного обеспечения.

Кроме того, интересно отметить, что типичные современные технологии определения интерфейса все еще редко предоставляют какие-либо средства для формального определения временных ограничений. Может быть .NET v5?

Создание быстрой тестовой программы определенно улучшило использование TryGetValue с 1 миллионом элементов в словаре.

Полученные результаты:

ContainsKey + Item для 1000000 просмотров: 45ms

TryGetValue для 1000000 просмотров: 26мс

Вот тестовое приложение:

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

}

На моей машине с нагрузками ОЗУ, при запуске в режиме RELEASE (не DEBUG), 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();
            }
        }
    }

Помимо разработки микробенчмарка, который даст точные результаты в практической обстановке, вы можете проверить справочный источник .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почти вдвое быстрее, чем ContainsKey+Item .

Неудобный интерфейс 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);

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

Если вы пытаетесь извлечь значение из словаря, TryGetValue (ключ, выходное значение) является лучшим вариантом, но если вы проверяете наличие ключа, для новой вставки, без перезаписи старых ключей, и только с этой областью, ContainsKey (ключ) является лучшим вариантом, тест может подтвердить это:

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

namespace benchmark
{
class Program
{
    public static Random m_Rand = new Random();
    public static Dictionary<int, int> testdict = new Dictionary<int, int>();
    public static Hashtable testhash = new Hashtable();

    public static void Main(string[] args)
    {
        Console.WriteLine("Adding elements into hashtable...");
        Stopwatch watch = Stopwatch.StartNew();
        for(int i=0; i<1000000; i++)
            testhash[i]=m_Rand.Next();
        watch.Stop();
        Console.WriteLine("Done in {0:F4} -- pause....", watch.Elapsed.TotalSeconds);
        Thread.Sleep(4000);
        Console.WriteLine("Adding elements into dictionary...");
        watch = Stopwatch.StartNew();
        for(int i=0; i<1000000; i++)
            testdict[i]=m_Rand.Next();
        watch.Stop();
        Console.WriteLine("Done in {0:F4} -- pause....", watch.Elapsed.TotalSeconds);
        Thread.Sleep(4000);

        Console.WriteLine("Finding the first free number for insertion");
        Console.WriteLine("First method: ContainsKey");
        watch = Stopwatch.StartNew();
        int intero=0;
        while (testdict.ContainsKey(intero))
        {
            intero++;
        }
        testdict.Add(intero, m_Rand.Next());
        watch.Stop();
        Console.WriteLine("Done in {0:F4} -- added value {1} in dictionary -- pause....", watch.Elapsed.TotalSeconds, intero);
        Thread.Sleep(4000);
        Console.WriteLine("Second method: TryGetValue");
        watch = Stopwatch.StartNew();
        intero=0;
        int result=0;
        while(testdict.TryGetValue(intero, out result))
        {
            intero++;
        }
        testdict.Add(intero, m_Rand.Next());
        watch.Stop();
        Console.WriteLine("Done in {0:F4} -- added value {1} in dictionary -- pause....", watch.Elapsed.TotalSeconds, intero);
        Thread.Sleep(4000);
        Console.WriteLine("Test hashtable");
        watch = Stopwatch.StartNew();
        intero=0;
        while(testhash.Contains(intero))
        {
            intero++;
        }
        testhash.Add(intero, m_Rand.Next());
        watch.Stop();
        Console.WriteLine("Done in {0:F4} -- added value {1} into hashtable -- pause....", watch.Elapsed.TotalSeconds, intero);
        Console.Write("Press any key to continue . . . ");
        Console.ReadKey(true);
    }
}
}

Это истинный пример, у меня есть сервис, который для каждого созданного «Предмета» ассоциирует прогрессивный номер, этот номер, каждый раз, когда вы создаете новый элемент, должен быть найден свободным, если вы удаляете Элемент, свободный номер становится бесплатно, конечно, это не оптимизировано, так как у меня есть статическая переменная, которая кэширует текущее число, но если вы заканчиваете все числа, вы можете начать заново с 0 до UInt32.MaxValue

Тест выполнен:
Добавление элементов в хеш-
таблицу ... Выполнено в 0,5908 - пауза ....
Добавление элементов в словарь ...
Выполнено в 0,2679 - пауза ....
Поиск первого свободного числа для вставки
Первый метод : ContainsKey
Выполнено в 0,0561 - добавлено значение 1000000 в словаре - пауза ....
Второй метод: TryGetValue
Выполнено в 0,0643 - добавлено значение 1000001 в словаре - пауза ....
Проверка хеш-таблицы
Выполнено в 0, 3015 - добавлено значение 1000000 в хеш-таблицу - пауза ....
Нажмите любую клавишу для продолжения. ,

Если некоторые из вас могут спросить, может ли ContainsKeys иметь преимущество, я даже попытался инвертировать TryGetValue с ключом Contains, результат тот же.

Итак, для меня, в конечном итоге, все зависит от того, как ведет себя программа.