개요
유니티 시스템 프로그래밍 Pt.1 스터디 2주차를 진행하던 중, 더 최적화할 수 있을 것 같은 코드를 발견하여 이에 대한 의견을 제시하였다
코드는 다음과 같다.
/// <summary>
/// 지정된 BGM을 재생합니다.
/// </summary>
/// <param name="bgm">재생할 BGM의 열거형 값.</param>
public void PlayBGM(EBGM bgm)
{
if (_currentBGMSource)
{
_currentBGMSource.Stop();
_currentBGMSource = null;
}
if (!_bgmDic.ContainsKey(bgm))
{
Debug.LogError($"Invalid clip name. {bgm}");
return;
}
_currentBGMSource = _bgmDic[bgm];
_currentBGMSource.Play();
}그리고 내가 제시한 코드는 이렇다
/// <summary>
/// 지정된 BGM을 재생합니다.
/// </summary>
/// <param name="bgm">재생할 BGM의 열거형 값.</param>
public void PlayBGM(EBGM bgm)
{
if (_currentBGMSource)
{
_currentBGMSource.Stop();
_currentBGMSource = null;
}
if (!_bgmDic.TryGetValue(bgm, out AudioSource bgmSource))
{
Debug.LogError($"Invalid clip name. {bgm}");
return;
}
_currentBGMSource = bgmSource;
_currentBGMSource.Play();
}
나의 주장은 다음과 같았다
- 단순히 ContainsKey로 비교 후 다른 로직으로 넘어가는 것이라면 상관 없지만, 다시 Key를 이용해서 찾을 경우 쓸데없이 2번의 연산을 진행하는 것이다
- 따라서 위와 같은 경우에는 성능 차이가 있다
이에 대해 이야기를 나누었는데 내가 전달하고자 하는 바는 이해했으나 명확하게 이해가 안된다 라는 답변을 받았다
당시 정신이 없었기도 했지만 내가 제대로 모르고 있는건 아닐까? 그러니까 설명을 명확하게 하지 못한게 아닐까? 라는 생각에서 다시 한번 지식을 정리하기 위하여 글을 쓰게 되었다
성능 테스트
테스트 환경은 다음과 같다
- Unity 2022.3.14f1 Apple Silicon
- JetBrain Rider 2023.1.1.
테스트를 위해 작성한 코드는 다음과 같다
using System.Collections.Generic;
using System.Diagnostics;
using UnityEngine;
using Debug = UnityEngine.Debug;
public class Test : MonoBehaviour
{
private readonly Dictionary<string, int> _dic = new Dictionary<string, int>();
private readonly Stopwatch _sw = new Stopwatch();
private void Awake()
{
// 테스트를 위한 Dictionary 초기화
_dic["str"] = 1;
int iterations = 50000000;
int outValue;
// ContainsKey로 확인한 후 값 할당하는 방식의 성능 테스트
_sw.Reset();
_sw.Start();
for (int i = 0; i < iterations; i++)
{
if (_dic.ContainsKey("str"))
{
outValue = _dic["str"];
}
}
_sw.Stop();
Debug.Log($"ContainsKey Execution Time (with value assignment): {_sw.ElapsedMilliseconds} ms");
// TryGetValue 성능 테스트
_sw.Reset();
_sw.Start();
for (int i = 0; i < iterations; i++)
{
_dic.TryGetValue("str", out outValue);
}
_sw.Stop();
Debug.Log($"TryGetValue Execution Time: {_sw.ElapsedMilliseconds} ms");
}
}
테스트 결과는 다음과 같다
우선 처음 주장대로 내가 주장한 바는 맞다
하지만 왜? 를 제대로 설명을 못했기에 근본적으로 코드를 체크해보았다
C# Dictionary.cs
C#의 Map인 Dictionary의 내부 코드를 보기 위하여 다음의 공식문서를 참고하였다
MS Reference Source .NET Framework 4.8 dictionary.cs
ContainsKey + Indexer 사용
우선 ContainsKey를 살펴보자
public bool ContainsKey(TKey key) {
return FindEntry(key) >= 0;
}
FindEntry라는 메서드를 이용하여 키를 찾는데, 이를 따라가면
private struct Entry {
public int hashCode; // Lower 31 bits of hash code, -1 if unused
public int next; // Index of next entry, -1 if last
public TKey key; // Key of entry
public TValue value; // Value of entry
}
private int[] buckets;
private Entry[] entries;
private int FindEntry(TKey key) {
if (key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets != null) {
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
return i;
}
}
}
return -1;
}
이런 메서드가 있다
ContainsKey와 FindEntry 메서드를 분석하여 알 수 있는건
- ContainsKey는 FindEntry를 이용함
- FindEntry는 내부적으로 구현된 해시 함수를 통하여 해시코드로 변환, 이를 이용하여 entries 배열을 순회하여 값을 찾아낸다
- 과정에서 O(1)이 소요됨
여기까지 결과적으로 O(1)이 소모가 되며 이제 인덱서가 어떻게 작동하는지 확인하면 명쾌하게 답이 나올 것 같다
public TValue this[TKey key] {
get {
int i = FindEntry(key);
if (i >= 0) return entries[i].value;
ThrowHelper.ThrowKeyNotFoundException();
return default(TValue);
}
set {
Insert(key, value, false);
}
}
인덱서의 동작은 ContainsKey와 동일한 구현임을 확인할 수 있었다
결론
같은 작업을 두 번 수행하기 때문에 O(2 * 1)이지만, 빅오표기법에서 상수 계수는 무시되기 때문에 O(1)이라고 표현해야 한다
다만 두 번의 키 검색이 일어나 같은 작업을 두 번 수행한다 라고 표현하는 게 맞다
TryGetValue
코드는 다음과 같다
public bool TryGetValue(TKey key, out TValue value) {
int i = FindEntry(key);
if (i >= 0) {
value = entries[i].value;
return true;
}
value = default(TValue);
return false;
}
구현된 ContainsKey, Indexer와 내부 구조가 동일하다
결론
TryGetValue는 O(1)의 시간 복잡도를 가진다
피드백
이 과정을 거치고, 내가 어떤 부분에서 잘못했는지 이해했다
- 비유를 들어 설명한답시고 해시를 이용한 자료구조인 Dictionary를 가지고 O(n), O(2n) 이렇게 설명하고 있으니 여기서부터 헷갈리셨을 것이고
- 그냥 간단하게 인덱서를 이용한 방식도 Key를 이용하여 두번 검색을 한다고 하면 되는 것인데
다시보니 정말 바보같이 설명을 한 것 같다
지금 지식을 조금 정리해서 다시 말하자면
- 두 방법 다 시간 복잡도는 O(1)이다. 다만 ContainsKey - Indexer를 사용하는 방식은 두 번의 키 검색이 일어나 두 번 연산하게 된다
- 따라서 위의 상황에선 한 번의 키 검색으로 작업을 완료하는 TryGetValue를 사용하는 것이 좋다
이렇게 깔끔하게 마무리 할 수 있을 것 같다
개선점
제대로 알지도 못하면서 설명을 하려고 한 샘이 되었다
이는 나에게도 마이너스고, 잘못된 지식을 알려드리게 되면 상대방도 헷갈리기 때문에 굉장히 실례되는 행동을 한 것 같다
앞으로는 명확하게 설명이 안 될 때
- 심신미약(?) 상태에서 생각하지 말고 정신차리고 다시 답변 드리기
- 명확하게 글로 논리 정리해서 전달하기. 생각나는 데로 쓰지 말기
- 공식문서를 근거로 확실한 정보를 전달하기
이미 다 아는 내용이지만, 다시 점검하자. 올바른 정보만을 전달하자