WIL-2_알고리즘(2)

알고리즘 문제 중 LRU 문제가 있었다.

[문제][1차] 캐시

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

처음에 Queue를 이용하여 구현하였다. 코드는 아래와 같다.

    public int solution2(int cacheSize, String[] cities) {
        int answer = 0;
        Queue<String> q = new LinkedList<>();

        for (int i = 0; i < cities.length; i++) {
            String str = cities[i].toUpperCase();
            if (q.contains(str)) {
                q.remove(str);
                q.add(str);
                answer += 1;
            } else {
                answer += 5;
                q.add(str);
                if (q.size() > cacheSize) {
                    q.poll();
                }
            }
        }
        return answer;
    }

문제를 푸는 것은 문제없이 풀 수 있었다. 그러나 로직 중 Queue에 들어 있는 있는지를 판단하는 contains 가 있다. search를 진행하는 과정이 사실 Queue를 사용하는 것이 적합하지 않다고 한다. 그래서 hash를 사용하도록 해보았다.

hash를 활용한 2번째 코드

	public void go(Set<String> cache, int capacity, String city, int[] answer) {
        if (capacity == 0) {
            answer[0] += 5;
            return;
        }

        if (cache.contains(city)) {
            cache.remove(city);
            cache.add(city);
            answer[0] += 1;
        } else {
            if (cache.size() == capacity) {
                String firstKey = cache.iterator().next();
                cache.remove(firstKey);
            }
            cache.add(city);
            answer[0] += 5;
        }
    }

    public int solution(int cacheSize, String[] cities) {
        Set<String> cache = new LinkedHashSet<>();

        int[] answer = {0};
        for (String city : cities) {
            go(cache, cacheSize, city.toLowerCase(), answer);
        }
        return answer[0];
    }

이렇게 하고 2개의 시간을 비교해 보았다.
solution1: hash, solution2: Queue

//  solution 1
//        테스트 1 〉	    통과 (0.52ms, 73.9MB)
//        테스트 2 〉	    통과 (0.15ms, 75.4MB)
//        테스트 3 〉	    통과 (0.56ms, 71.4MB)
//        테스트 4 〉	    통과 (0.48ms, 75.2MB)
//        테스트 5 〉	    통과 (0.22ms, 73MB)
//        테스트 6 〉	    통과 (0.05ms, 74.9MB)
//        테스트 7 〉	    통과 (0.16ms, 78MB)
//        테스트 8 〉	    통과 (0.12ms, 76.6MB)
//        테스트 9 〉	    통과 (0.43ms, 77.6MB)
//        테스트 10 〉	통과 (1.08ms, 73.7MB)
//        테스트 11 〉	통과 (46.77ms, 127MB)
//        테스트 12 〉	통과 (0.81ms, 71.3MB)
//        테스트 13 〉	통과 (1.61ms, 81.2MB)
//        테스트 14 〉	통과 (1.82ms, 78.6MB)
//        테스트 15 〉	통과 (1.93ms, 83.8MB)
//        테스트 16 〉	통과 (3.54ms, 89MB)
//        테스트 17 〉	통과 (1.66ms, 84.2MB)
//        테스트 18 〉	통과 (3.71ms, 76.3MB)
//        테스트 19 〉	통과 (2.64ms, 79.4MB)
//        테스트 20 〉	통과 (3.12ms, 81MB)

//  solution 2
//        테스트 1 〉	    통과 (0.21ms, 81.4MB)
//        테스트 2 〉	    통과 (0.13ms, 67MB)
//        테스트 3 〉	    통과 (0.38ms, 77.7MB)
//        테스트 4 〉	    통과 (0.21ms, 77.9MB)
//        테스트 5 〉	    통과 (0.16ms, 63.8MB)
//        테스트 6 〉	    통과 (0.23ms, 76.9MB)
//        테스트 7 〉	    통과 (0.24ms, 90.4MB)
//        테스트 8 〉	    통과 (0.26ms, 72.4MB)
//        테스트 9 〉	    통과 (0.31ms, 84.9MB)
//        테스트 10 〉	통과 (0.55ms, 78.9MB)
//        테스트 11 〉	통과 (34.59ms, 108MB)
//        테스트 12 〉	통과 (0.35ms, 75.5MB)
//        테스트 13 〉	통과 (0.88ms, 72.9MB)
//        테스트 14 〉	통과 (1.35ms, 77.2MB)
//        테스트 15 〉	통과 (1.72ms, 79.5MB)
//        테스트 16 〉	통과 (1.85ms, 75.2MB)
//        테스트 17 〉	통과 (1.74ms, 73.7MB)
//        테스트 18 〉	통과 (2.45ms, 85.1MB)
//        테스트 19 〉	통과 (2.53ms, 76.7MB)
//        테스트 20 〉	통과 (2.86ms, 83.6MB)

조금 당황했다. 시간이 Queue가 이겨버렸다. 그래서 그냥 해보는 김에 테스트케이스를 많이 만들고 실험을 해보았다.

테스트 케이스 생성 코드

class TestcaseGenerator {
    static int N = 10000;
    static int capacity = 100000;
    static String[] cities;

    public static String generateRandomCityName() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 5; ++i) {
            int randomValue = (int) (Math.random() * 26);
            sb.append((char) (randomValue + 'a'));
        }
        return sb.toString();
    }

    public static void setCities() {
        ArrayList<String> arrayList = new ArrayList<>();
        for (int i = 0; i < N; ++i) {
            arrayList.add(generateRandomCityName());
        }
        cities = arrayList.toArray(new String[0]);
    }
}

랜덤으로 생성하는 것이라, cache hit가 일어나기가 쉽지 않기 때문에 글자수는 5개로 줄이고 소문자만 허용하도록 바꿨다. cache size도 10000개쯤 해야 hit가 일어날 수 있을거라 생각하여 늘려버렸다.

실행문

class Main {
    public static void main(String[] args) {
        TestcaseGenerator.setCities();
        Solution solution = new Solution();
        long start = System.currentTimeMillis();
        // hash
        solution.solution(TestcaseGenerator.capacity, TestcaseGenerator.cities);
        long end = System.currentTimeMillis();
        System.out.println("solution: " + ((end - start) / 1000.0f));

        TestcaseGenerator.setCities();
        start = System.currentTimeMillis();
        // Queue
        solution.solution2(TestcaseGenerator.capacity, TestcaseGenerator.cities);
        end = System.currentTimeMillis();
        System.out.println("solution2: " + ((end - start) / 1000.0f));
    }
}

드디어 원하는 결과가 나왔다.
Queue의 경우 search에 O(n)의 결과가 나오지만,
hash는 O(1)이라고 한다.

이번 문제로 여러가지 자료구조의 모습을 조금 생각해보는 계기가 되었고, 자료구조의 공부가 필요함을 느꼈다.