더 효율적인 것은 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의 참조 소스를 검사 할 수 있습니다.
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)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를 반전하려고 시도한 경우에도 결과는 동일합니다.
따라서 마지막으로 고려해야 할 것은 프로그램의 작동 방식에 달려 있습니다.
'IT story' 카테고리의 다른 글
| 특정 폴더에서 intellij 색인 생성 비활성화 (0) | 2020.04.12 |
|---|---|
| 왜 C에서 수학 라이브러리를 연결해야합니까? (0) | 2020.04.12 |
| 오류 :«MvcApplication 유형을로드 할 수 없습니다» (0) | 2020.04.12 |
| Visual Studio 2010 이상에서 확대 / 축소를 다시 설정하는 방법 (0) | 2020.04.12 |
| React Native를 어떻게 디버깅합니까? (0) | 2020.04.12 |