[Programmers] [1차] 캐시 - JAVA

반응형

728x90

[Programmers] [1차] 캐시 2018 KAKAO BLIND RECRUITMENT - LV2

---

접근

• 구현

---

풀이

데이터베이스 연산을 수행할 때 사용되는 1차 캐시를 구현하는 문제이다. 데이터베이스에 조회 연산을 수행할 때 조회한 뒤 1차 캐시에 저장하여 다음번 조회 시 1차 캐시에 들어있는 값을 바로 반환하며 조회 성능을 높일 수 있는 방법으로 현재 문제에서는 1차 캐시에서 조회 시 1의 수행시간을 가지고 데이터베이스에 직접 조회 시 5의 수행시간을 가지게 된다. 1차 캐시가 가득차 데이터를 교환해야 하는 경우 LRU 알고리즘을 사용해 교체하게 된다. LRU 알고리즘은 Least Recently Used로 가장 사용 횟수가 적은 데이터를 교체하는 방식이다. 그렇기 때문에 1차 캐시에서 조회가 일어날 경우 사용 빈도를 관리해 주어야 한다.

    private static class FirstCache {
        private Queue<String> cache;

        public FirstCache() {
            this.cache = new LinkedList<>();
        }

 큐를 사용한 1차 캐시 클래스를 만들어 필요한 기능들을 다 내부 메서드로 구현한 뒤 문제를 풀었다.

	public boolean find(String city) {
            return cache.contains(city);
        }

1차 캐시에 값이 존재하는지 체크하는 메서드로 단순히 존재 여부를 체크해 반환한다.

	public void getInCache(String city) {
            Queue<String> newQue = new LinkedList<>();

            while (!cache.isEmpty()) {
                String cityInCache = cache.poll();
                if (!cityInCache.equals(city)) {
                    newQue.offer(cityInCache);
                }
            }

            while (!newQue.isEmpty()) {
                cache.offer(newQue.poll());
            }

            cache.offer(city);
        }

1차 캐시에 값이 존재하는 경우 사용하는 메서드로 LRU를 위해 사용 빈도를 변경해주어야 한다. 새로운 큐를 생성하여 조회하고자 하는 값을 제외한 모든 데이터를 다시 순서대로 담은 뒤 마지막에 1차 캐시에서 조회한 데이터를 넣어주며 사용 빈도를 관리해 준다.

	public void getInDatabase(String city, int cacheSize) {
            if(cache.size() < cacheSize){
                cache.offer(city);
                return;
            }
            cache.poll();
            
            cache.offer(city);
        }

1차 캐시에 값이 존재하지 않을 경우 수행하는 메서드이다. 캐시에 저장 가능한 공간이 있다면 저장하고, 공간이 없다면 제일 사용 빈도가 적은 데이터를 뽑아낸 뒤 새로운 값을 캐시에 저장한다.

	FirstCache firstCache = new FirstCache();

        int totalExecuteTime = 0;

        for (String city : cities) {
            city = city.toUpperCase();
            if (cacheSize == 0) {
                totalExecuteTime += 5;
                continue;
            }

1차 캐시 클래스 내 메서드는 끝이 났고 메인 로직의 코드이다. 필요한 것들을 선언하고 이 문제에서 대소문자를 구별하지 않기 때문에 도시 이름은 모두 대문자로 변경하여 저장했다. 그리고 캐시 사이즈가 0인 경우에는 무조건 데이터베이스를 통한 조회를 실행하기 때문에 불필요한 연산을 줄이고자 처리를 해두었다.

	    if (firstCache.find(city)) {
                firstCache.getInCache(city);
                totalExecuteTime++;
            } else {
                firstCache.getInDatabase(city, cacheSize);
                totalExecuteTime += 5;
            }

메인의 코드는 이게 전부이다. 1차 캐시에 데이터가 있는지에 따라 나눠지고 데이터가 있다면 캐시에서 값을 얻으며 사용 빈도를 최신화해주고 1의 실행 시간을 가지게 된다. 1차 캐시에 데이터가 없는 경우 데이터베이스를 통한 조회를 실행하고 5 실행 시간을 가진다.

---

ArrayList 사용

1차 캐시의 크기도 커지고 입출력이 빈번하게 일어난다면 당연히 큐나 스택을 사용하는 게 좋을 줄 알았는데 이 문제의 범위에선 ArrayList가 더 빠르고 간단하게 구현이 가능했다.

    private static class FirstCache {
        private List<String> cache;

        public FirstCache() {
            this.cache = new ArrayList<>();
        }

        public boolean find(String city) {
            return cache.contains(city);
        }

        public void getInCache(String city) {
            cache.remove(city);
            cache.add(city);
        }

        public void getInDatabase(String city, int cacheSize) {
            if (cache.size() >= cacheSize) {
                cache.remove(0);
            }
            cache.add(city);
        }
    }

코드가 매우 간결해지고 성능도 더 잘 나왔는데 find와 getInCache 메서드는 큐와 리스트 둘 다 O(n)이고 getInDatabase의 경우 큐는 O(1)로 수행이 가능하지만 리스트의 remove 연산이 O(n)으로 이론상 캐시의 크기가 커질수록 큐를 사용한 연산의 성능이 좋다고 볼 수 있다. 이 문제에서 캐시의 최대 크기가 30 밖에 되지 않아서 ArrayList를 사용한 연산으로도 충분히 빠르게 수행이 가능했던 것 같다.

---

전체 코드

import java.util.*;

class Solution {
    private static class FirstCache {
        private Queue<String> cache;

        public FirstCache() {
            this.cache = new LinkedList<>();
        }

        public boolean find(String city) {
            return cache.contains(city);
        }

        public void getInCache(String city) {
            Queue<String> newQue = new LinkedList<>();

            while (!cache.isEmpty()) {
                String cityInCache = cache.poll();
                if (!cityInCache.equals(city)) {
                    newQue.offer(cityInCache);
                }
            }

            while (!newQue.isEmpty()) {
                cache.offer(newQue.poll());
            }

            cache.offer(city);
        }

        public void getInDatabase(String city, int cacheSize) {
            if(cache.size() < cacheSize){
                cache.offer(city);
                return;
            }
            cache.poll();
            
            cache.offer(city);
        }

    }
    public int solution(int cacheSize, String[] cities) {
        FirstCache firstCache = new FirstCache();

        int totalExecuteTime = 0;

        for (String city : cities) {
            city = city.toUpperCase();
            if (cacheSize == 0) {
                totalExecuteTime += 5;
                continue;
            }
            
            if (firstCache.find(city)) {
                firstCache.getInCache(city);
                totalExecuteTime++;
            } else {
                firstCache.getInDatabase(city, cacheSize);
                totalExecuteTime += 5;
            }

        }

        return totalExecuteTime;
    }
}