알고리즘의 시간복잡도에 따른 성능 변화

댓글 0
댓글을 작성하려면 로그인이 필요합니다.
아직 댓글이 없습니다. 첫 번째 댓글을 작성해보세요.
개요
-탄환이 많을때 되감기 시 급격한 프레임 드랍이 발생함
-이론적 지표가 아닌 현실적으로 가능한 수치인 수백개 선에서도 상당한 버벅임 발생
-이는 컨테이너의 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% 이상의 연산량 감소. 시간복잡도 자체가 바뀌었기 때문에 아이템이 많아질수록 효과가 커짐
-매우 만족함

개요 -통상적, 편의상으로 데이터들의 ID는 문자열값으로 부여함 -리플레이 시스템 구현을 위해서 해당 개체의 베이스 데이터 ID값을 저장해둬야함. 그래야 로드 시 해당 개체가 존재하지 않을때 DB에서 데이터를 찾아와 인스턴싱 가능 -하지만 문자열을 SaveData로 하면 byte[]로 변환할때 많은 용량을 사용하고 성능도 좋지 않음 -따라서 DB딴에서 처음

개요 -유니티에서 게임오브젝트를 움직이게 하기 위해서 Tranform에 접근함 -작업 한번이 무거운건 아니지만, 탄환-플레이어-적 등을 이동시키다보면 매프레임 이에 접근하게 되고 쌓여서 작지 않은 부하가 됨 -특히 구현중인 리플레이 시스템에서 매 프레임마다 개체들의 위치,각도,크기 를 저장하고 있기 때문에 접근횟수가 몇배로 뻥튀기되어 무시 못할 정도 -따라

개요 -적과 탄환의 충돌 판정을 체크하는데 연산을 너무 많이 함 -적마다 현재 존재하는 모든 탄환에 대해 충돌 체크 연산을 시행 -부딫힐 가능성이 제로인 저 멀리 있는 탄환과도 연산을 시행하고 있음 -이에 따라 게임 공간을 구역(Cell)으로 나눠 적이 있는 구역과 인접한 구역에 있는 탄환하고만 충돌 연산을 시행하도록 변경함 -구역은 10x10, 총 100

개요 -통상적, 편의상으로 데이터들의 ID는 문자열값으로 부여함 -리플레이 시스템 구현을 위해서 해당 개체의 베이스 데이터 ID값을 저장해둬야함. 그래야 로드 시 해당 개체가 존재하지 않을때 DB에서 데이터를 찾아와 인스턴싱 가능 -하지만 문자열을 SaveData로 하면 byte[]로 변환할때 많은 용량을 사용하고 성능도 좋지 않음 -따라서 DB딴에서 처음

개요 -유니티에서 게임오브젝트를 움직이게 하기 위해서 Tranform에 접근함 -작업 한번이 무거운건 아니지만, 탄환-플레이어-적 등을 이동시키다보면 매프레임 이에 접근하게 되고 쌓여서 작지 않은 부하가 됨 -특히 구현중인 리플레이 시스템에서 매 프레임마다 개체들의 위치,각도,크기 를 저장하고 있기 때문에 접근횟수가 몇배로 뻥튀기되어 무시 못할 정도 -따라

개요 -적과 탄환의 충돌 판정을 체크하는데 연산을 너무 많이 함 -적마다 현재 존재하는 모든 탄환에 대해 충돌 체크 연산을 시행 -부딫힐 가능성이 제로인 저 멀리 있는 탄환과도 연산을 시행하고 있음 -이에 따라 게임 공간을 구역(Cell)으로 나눠 적이 있는 구역과 인접한 구역에 있는 탄환하고만 충돌 연산을 시행하도록 변경함 -구역은 10x10, 총 100