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

Question

Из записи 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);

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

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

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

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

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

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

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

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

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

Answer 6

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

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

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

Answer 7

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

Результаты:

ContainsKey + Item для 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);

}

Answer 8

На моем компьютере с загрузкой ОЗУ при запуске в режиме 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();
            }
        }
    }

Answer 9

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

Answer 10

Если вы пытаетесь получить значение из словаря, 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
Донe в 0,0561 - добавлено значение 1000000 в словаре - пауза ....
Второй метод: TryGetValue
Выполнено в 0,0643 - добавлено значение 1000001 в словаре - пауза ....
Проверка хеш-таблицы
Выполнено за 0,3015 - добавлено значение 1000000 в хеш-таблицу - пауза ....
Нажмите любую клавишу для продолжения.,

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

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