알고리즘의 시간복잡도에 따른 성능 변화
개요
-탄환이 많을때 되감기 시 급격한 프레임 드랍이 발생함
-이론적 지표가 아닌 현실적으로 가능한 수치인 수백개 선에서도 상당한 버벅임 발생
-이는 컨테이너의 Load 메소드가 비효율적으로 동작하기 때문
-따라서 알고리즘을 개선하여 Load 메소드 작동 시간복잡도를 낮춤
기존 작동방식
-컨테이너 아이템들의 IndexId,ObjId,각 아이템의 SaveData를 리스트 형태로 저장
-Load시 각 아이템을 불러와 현재 리스트에서 IndexId가 일치하는 아이템 탐색
-찾지 못했다면 새로 생성
-각 저장 아이템 데이터에 대해서 매번 리스트를 Find하기 때문에 O(N^2)의 시간복잡도 발생
public virtual void Load(SaveData data)
{
int count = data;
List<int> list = new();
for (int i = 0; i < count; i++)
{
int indexId = data;
ushort objId = data;
T item;
item = Items.Find(x => x.IndexId == indexId);
if (item != null)
{
item.Load(data);
}
else
{
item = Create(ConvertId(objId), false);
item.IndexId = indexId;
item.ObjId = ConvertId(objId);
item.Load(data);
}
list.Add(indexId);
}
var d = new List<T>();
foreach (var i in Items)
{
if (!list.Contains(i.IndexId))
{
d.Add(i);
}
}
foreach (var i in d)
{
i.Delete();
}
}
변경 방식
-저장 시 아이템들을 오름차순으로 정렬 후 저장
-Load 시 아이템을 불러와 현재 리스트의 0번부터 대조 시작
-현재 아이템의 IndexId가 데이터의 IndexId보다 작다면 다음 아이템 대조
-같다면 현재 데이터의 대조를 끝내고 Load후 다음 데이터는 다음 아이템부터 대조
-크다면 다음 데이터를 현재 아이템부터 대조
-모든 아이템을 대조했음에도 저장 데이터가 남았다면 새로 생성
-아이템 리스트들을 한번씩만 대조하기 때문에 O(N)의 시간복잡도
public virtual void Load(SaveData data)
{
int count = data;
List<T> list = GetList();
int arrayIndex = 0;
for (int i = 0; i < count; i++)
{
int indexId = data;
ushort objId = data;
bool isLoad = false;
while (arrayIndex < Items.Count)
{
var it = Items[arrayIndex];
var itIndex = it.IndexId;
if (itIndex < indexId)
{
arrayIndex += 1;
continue;
}
if (itIndex == indexId)
{
arrayIndex += 1;
it.Load(data);
isLoad = true;
list.Remove(it);
break;
}
if (itIndex > indexId)
{
break;
}
}
if (isLoad)
{
continue;
}
var item = Create(ConvertId(objId), false);
item.IndexId = indexId;
item.ObjId = ConvertId(objId);
item.Load(data);
}
foreach (var i in list)
{
i.Delete();
}
}
성능 체크
변경 전
-아이템 300여개 기준으로 Find에 드는 작업량이 데이터를 Load하는데 드는 비용을 초과함
-아이템 개수가 N일때 Find에 드는 작업량은 N^2. 매우 무거움
변경 후
-순수한 데이터 Load이외에 연산이 거의 사라짐
-데이터를 불러오는 작업만 남아 O(N)의 시간복잡도 달성
결과
-단순히 300개 기준으로도 50% 이상의 연산량 감소. 시간복잡도 자체가 바뀌었기 때문에 아이템이 많아질수록 효과가 커짐
-매우 만족함
