IT story

더 효율적인 것은 Dictionary TryGetValue 또는 ContainsKey + Item입니까?

hot-time 2020. 4. 12. 10:32
반응형

더 효율적인 것은 Dictionary TryGetValue 또는 ContainsKey + Item입니까?


Dictionary.TryGetValue 메서드 의 MSDN 항목에서 :

이 메서드는 ContainsKey 메서드의 기능과 Item 속성을 결합합니다.

키를 찾을 수 없으면 값 매개 변수는 값 유형 TValue에 적절한 기본값을 가져옵니다. 예를 들어 정수 유형의 경우 0, 부울 유형의 경우 false, 참조 유형의 경우 null입니다.

코드에서 사전에없는 키에 자주 액세스하려고하면 TryGetValue 메서드를 사용하십시오. 이 메소드를 사용하면 Item 속성에서 발생하는 KeyNotFoundException을 잡는 것보다 효율적입니다.

이 방법은 O (1) 연산에 접근합니다.

설명에서 ContainsKey를 호출 한 다음 조회를 수행하는 것보다 더 효율적이거나 더 편리한 지 명확하지 않습니다. 구현에 TryGetValueContainsKey를 호출 한 다음 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 더 빠를 것입니다.

ContainsKeyTryGetValue내부적으로 실제 입력 위치를 나타내는와 동일한 검사를 사용합니다 . Item속성은 실제로 TryGetValuefalse와 같은 예외를 throw한다는 점을 제외하고는 코드 기능과 거의 동일합니다 .

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 + Item40 % 느린 안타 미스의도 조화를 가정에 대한 액세스를.

또한 프로그램을 항상 그리워 (즉, 항상 찾고 "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 인터페이스가 아니라 컴퓨터 과학 의미의 인터페이스)의 일부를 형성합니다.

따라서 속도가 공식적인 인터페이스 정의 (이 경우에는 해당되지 않음)의 일부가 아닌 한 이러한 메서드를 호출하는 것이 더 빠른지 묻는 것은 일반적으로 올바르지 않습니다.

전통적으로 이러한 종류의 바로 가기 (검색 및 검색 결합)는 언어, 인프라, OS, 플랫폼 또는 기계 아키텍처에 관계없이 더 효율적입니다. 또한 코드 구조에서 의도를 암시하지 않고 명시 적으로 의도를 표현하기 때문에 더 읽기 쉽습니다.

따라서 어리석은 낡은 핵에서 나온 대답은 '예'입니다 (TryGetValue는 Dictionary에서 값을 검색하기 위해 ContainsKey와 Item [Get]의 조합보다 선호됩니다).

이것이 이상하다고 생각되면 다음과 같이 생각하십시오. TryGetValue, ContainsKey 및 Item [Get]의 현재 구현에서 속도 차이가 발생하지 않더라도 향후 구현 (예 : .NET v5) 일 가능성이 있다고 가정 할 수 있습니다. 할 것입니다 (TryGetValue가 빠를 것입니다). 소프트웨어 수명에 대해 생각하십시오.

게다가, 전형적인 최신 인터페이스 정의 기술은 여전히 ​​공식적으로 타이밍 제약을 정의하는 수단을 거의 제공하지 않는다는 점에 주목하는 것이 흥미 롭습니다. .NET v5일까요?


빠른 테스트 프로그램을 만들면 사전에 1 백만 개의 항목이있는 TryGetValue를 사용하여 개선 된 결과가 있습니다.

결과 :

ContainsKey + 1000000 조회수 : 45ms

1000000 조회에 대한 TryGetValue : 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);

}

내 컴퓨터에서 RAM이 많은 상태에서 RELEASE 모드 (DEBUG 아님)로 실행될 때 /에 해당하는 모든 항목이 있으면 / ContainsKey와 같습니다 .TryGetValuetry-catchDictionary<>

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의 참조 소스를 검사 할 수 있습니다.

그들 모두 FindEntry(TKey)는 대부분의 작업을 수행 하는 메소드를 호출 하고 결과를 기억하지 않으므로 호출 TryGetValueContainsKey+ 보다 거의 두 배 빠릅니다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)plain로 바꿀 수 있습니다 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 (key, out value)가 가장 좋은 옵션이지만 이전 키를 덮어 쓰지 않고 키가 있는지 확인하고 새 삽입을 확인하려는 경우, 해당 범위 내에서만 ContainsKey (key)가 가장 좋은 옵션이며 벤치 마크에서이를 확인할 수 있습니다.

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

이것은 진정한 예입니다. 나는 각 "항목"에 대해 생성 된 서비스를 가지고 있으며, 새로운 번호를 생성 할 때마다이 번호는 누진 번호를 연결합니다. 항목을 삭제하면 무료 번호가됩니다. 무료, 물론 이것은 현재 숫자를 캐시하는 정적 var가 있기 때문에 최적화되지는 않지만 모든 숫자를 끝내는 경우 0에서 UInt32로 다시 시작할 수 있습니다.

테스트 실행 :
해시 테이블에 요소 추가 ...
0,5908에서 완료-일시 정지 ....
사전에 요소 추가 ...
0,2679에서 완료-일시 정지 ...
삽입을위한 첫 번째 자유 번호 찾기
첫 번째 방법 : ContainsKey
완료 0,0561-사전에 값 1000000 추가-일시 정지 ....
두 번째 방법 : TryGetValue
완료 0,0643-사전에 값 1000001 추가-일시 정지 ... 0에서
해시 테이블
완료 테스트 , 3015-해시 테이블에 1000000 값을 추가-일시 중지 ..
계속하려면 아무 키나 누르 십시오. .

ContainsKeys가 이점을 가질 수 있는지 묻는 사용자 중 일부가 Contains 키를 사용하여 TryGetValue를 반전하려고 시도한 경우에도 결과는 동일합니다.

따라서 마지막으로 고려해야 할 것은 프로그램의 작동 방식에 달려 있습니다.

참고 URL : https://stackoverflow.com/questions/9382681/what-is-more-efficient-dictionary-trygetvalue-or-containskeyitem

반응형