MatchList
matchList는 항상 최대 20의 크기를 유지합니다. 이 때 기본키 역시 유지되어야 하기 때문에 match 정보를 업데이트 하려면 필드를 매핑해야 합니다. 이제까지는 for문으로 매핑한 후 게임의 순서로 정렬을 해줬습니다.
int updateStartIndex = LOL.gameCount - newMatchCount; // 업데이트 시작할 인덱스
for (int j = 0; j < newMatchCount; j++) {
int updateIndex = updateStartIndex + j;
Match newMatch = newMatchList.get(j);
// 기존 매치 정보 업데이트 (in-place 업데이트로 리스트 크기 유지)
log.info("set updated Match");
Match match = summonerInfo.getMatchList().get(updateIndex);
match.updateMatch(newMatch);
match.setSummonerInfo(summonerInfo);
}
summonerInfo.getMatchList().sort(Comparator.comparing(Match::getGameStartTimestamp));
}하지만 matchList의 구조를 살펴보면
0번이 가장 최신 경기이고 경기 시간을 기준으로 내림차순 입니다.
플레이어가 4경기를 플레이 했지만 아직 갱신이 안됐다고 가정하겠습니다.
Slice
0~3번 인덱스에 최신 경기가 들어가야 합니다. 그럼 6~9번 경기는 밀려나서 없어집니다.
이렇게 되면 기존 0~5번 경기를 4~9로 복사한 후 0~3번에 최신 경기를 위치시켜야 합니다. 이러면 복잡도가 O(N)입니다. 이건 배열의 slice 아이디어인데 메모리를 많이 소비하기 때문에 별로라고 생각했습니다.
In-place
위 코드가 inplace 방식입니다. 최신 경기가 4경기를 가장 오래된 데이터인 6~9번 데이터에 오버랩 하여 배열에 매핑합니다. 그런 다음 경기 시간 필드를 이용해 정렬합니다. 메모리 부하는 발생하지 않지만 정렬에 O(nlogn) 복잡도가 필요합니다.
두 matches 내부는 이미 정렬이 되어 있지만 newMatch를 위에 위치시키기 위해 어쩔 수 없이 sorting을 새로 해야하는 낭비가 발생합니다.
사실 20경기 밖에 안돼서 뭘 선택하든 성능의 차이가 크진 않겠지만 최대한 좋은 자료구조를 사용해보고 싶었습니다.(공부를 위해)
Circular Queue
front는 최신 경기의 위치, cur은 현재 가리키고 있는 인덱스의 위치입니다.
초기화
public CircularQueue(List<Match> matchList) {
this.size = LOL.gameCount;
matches = new Match[size];
front = 0;
cur = 0;
while (cur < matchList.size()) {
matches[cur] = matchList.get(cur);
cur++;
}
cur %= size;
}최초에 경기 리스트를 이용해 queue를 초기화 합니다. cur이 20될 경우를 대비해 size로 나머지 연산 처리합니다.
갱신
public void update(Match newMatch) {
if (matches[cur] == null)
matches[cur] = newMatch;
matches[cur].updateMatch(newMatch);
matches[cur].updateSummonerInfo(matches[cur].getSummonerInfo());
rotate();
}이후 최신 경기를 업데이트 합니다. rotate()는 cur을 시계 방향으로 이동시킵니다.
ex) 원형 큐의 크기는 20이고 현재 19경기의 데이터만 가지고 있습니다. 이러면 0 ~ 18까지는 데이터가 있고 19는 null입니다.
여기서 최신 경기가 2개 생겼다고 하면 두 경기는 18, 19번 인덱스에 매핑하면 됩니다.(19번은 비어있었고 18번 경기가 가장 오래됐기 때문)
최신위치 옮기기
public void setFront(int index) {
this.front = index;
this.cur = front;
}이를 이용해 최신 경기가 18번 인덱스라는 것을 설정합니다. 그리고 cur 역시 front로 옮겨주면 18번 인덱스를 0번 인덱스처럼 사용할 수 있습니다.
즉 위의 배열 그림을 빌려보면
이미 두 matches 내부는 정렬되어 있기 때문고 포인터가 있기 때문에 두 matches의 위치를 바꿀 필요 없이 포인터로 시작점(front)을 가리키기만 하면 문제가 없습니다.
사용
CircularQueue queue = new CircularQueue(summonerInfo.getMatchList());
queue.setFront(LOL.gameCount - newMatchList.size());
for(Match newMatch : newMatchList) {
queue.update(newMatch);
}
summonerInfo.updateMatchList(queue.getMatchList());
정렬도 필요없고 update할 때 반복문을 사용하게 되지만 최악의 경우 O(N) (: Max N = 20), 1~20으로 다른 방법에 비해 단축됩니다. 메모리도 많이 사용하지 않아 좋을 것 같습니다.
Full Code
static class CircularQueue {
private Match matches[];
private int cur, front, size;
public CircularQueue(List<Match> matchList) {
this.size = LOL.gameCount;
matches = new Match[size];
front = 0;
cur = 0;
while (cur < matchList.size()) {
matches[cur] = matchList.get(cur);
cur++;
}
cur %= size;
}
public void setFront(int index) {
this.front = index;
this.cur = front;
}
public void update(Match newMatch) {
if (matches[cur] == null)
matches[cur] = newMatch;
matches[cur].updateMatch(newMatch);
matches[cur].updateSummonerInfo(matches[cur].getSummonerInfo());
rotate();
}
public List<Match> getMatchList() {
List<Match> matchList = new ArrayList<>();
for (int i = 0; i < size; i++) {
Match match = matches[(i + front) % size];
if (match != null) {
matchList.add(match);
}
}
return matchList;
}
public void rotate() {
cur = (cur + 1) % size;
}
}
public void updateMatches(SummonerInfo summonerInfo, List<Match> newMatchList) {
CircularQueue queue = new CircularQueue(summonerInfo.getMatchList());
queue.setFront(LOL.gameCount - newMatchList.size());
for(Match newMatch : newMatchList) {
queue.update(newMatch);
}
summonerInfo.updateMatchList(queue.getMatchList());
}결과
갱신
14:15:14.012 ~ 14:15:16:269 약 2.2초로 이전 업데이트가 6초 걸렸었는데 4초가 단축됐네요.
생성
20:55:07.332 ~ 20:55:12:720 약 5.4초 걸립니다.
ec2 환경에서 갱신을 해보니
04:04:09:724 ~ 04:04:11:751로 약 2초가 걸렸습니다. 물론 로컬환경에서는 새 게임이 8개였고 ec2에서는 1개여서 거의 비슷하다고 볼 수 있겠네요.
- 2024.11.14)
어차피 matchList를 가져올 때 시간 순으로 sorting해서 가져오기 때문에 처음에 matchList를 시간이 오래된 순서로 가져온 후 정해진 갯수만큼 0~n까지 바로 덮어씌우면 끝 아닌가?
-> 중요한 건 update 후의 List를 곧바로 응답값으로 전달해야한다. 만약 그대로 전달하면 List 내부의 값 자체는 정상적으로 update 됐지만 순서가 올바르지 않다. 이 경우 처음 문제처럼 또 sorting을 해줘야하기 때문에 문제가 된다.
