2018 KAKAO BLIND RECRUITMENT - 캐시
Date: 2022년 9월 20일
Tags: 알고리즘
출처: https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=java
캐시
지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.
어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.
입력 형식
- 캐시 크기(
cacheSize)와 도시이름 배열(cities)을 입력받는다. cacheSize는 정수이며, 범위는 0 ≦cacheSize≦ 30 이다.cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.- 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
출력 형식
- 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.
조건
- 캐시 교체 알고리즘은
LRU(Least Recently Used)를 사용한다. cache hit일 경우 실행시간은1이다.cache miss일 경우 실행시간은5이다.
입출력 예제
| 캐시크기(cacheSize) | 도시이름(cities) | 실행시간 |
|---|---|---|
| 3 | ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"] | 50 |
| 3 | ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"] | 21 |
| 2 | ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"] | 60 |
| 5 | ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"] | 52 |
| 2 | ["Jeju", "Pangyo", "NewYork", "newyork"] | 16 |
| 0 | ["Jeju", "Pangyo", "Seoul", "NewYork", "LA"] | 25 |
문제풀이
(DB 캐시를 적용할 때)
캐시 크기에 따른
실행시간 측정 프로그램을 작성하시오
캐시크기에 따라서 실행시간이 얼마나 나오는지 알아야 함 즉, 캐시크기와 실행시간의 상관관계를 확인해야함
입력형식
- 캐시 크기(
cacheSize)와 도시이름 배열(cities)을 입력받는다. cacheSize는 정수이며, 범위는 0 ≦cacheSize≦ 30 이다.cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.- 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
조건풀이
- 캐시 교체 알고리즘은
LRU(Least Recently Used)를 사용한다. LRU 알고리즘이랑 Oracle Database의 메모리 관리를 효율적으로 하기 위해 고안된 대표적인 알고리즘으로 최신 데이터를 메모리에 유지시키고 오래된 데이터는 메모리에서 내보내게 하는 알고리즘 select * from emp where name=”sco”; 를 입력했을 경우
- 해당 문장이 메모리에 정보가 올라와있다면 1초
cache hit - 메모리에 정보가 없어 디스크에서 조회하면 5초
cache miss하지만 메모리 공간이 한정되어있어, 무한히 데이터를 올릴 수 없다. 이를 고려한 문제인 것 같음최근에 내가 검색한 데이터는 다시 검색한 확률이 높을것이다라고 가정하는 알고리즘
조건을 보면서 캐시교체 알고리즘을 큐로 구현할 수 있을 것 같다는 생각이 들었다.
큐를 보면 가장 오래된 것이 가장 먼저 나간다. 이걸 캐시 교체 알고리즘에 비추어 보면,
캐시의 크기 = 큐의 크기
내가 검색한 데이터가 큐에 들어갈 때 해당 데이터에 이미 있는지 없는지 확인하고 큐에 들어갈 것 이를 확인했을 때 이미 있다면 cache hit 없다면 cache miss 로 처리하면 될 것같아.. 추가적인 문제가 발생할것같지만 일단, 해보면서 해결해보도록하자
import java.util.LinkedList;
import java.util.Queue;
public class programmers_cache {
public static void main(String[] args) {
String[] cities = {"Jeju", "Pangyo", "NewYork", "newyork"};
//{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};
//{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
//{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"};
int cacheSize = 2;
int cache_hit = 1;
int cache_miss = 5;
int result = 0;
Queue<String> queue = new LinkedList<>();
for(String city : cities){
if (queue.contains(city)){
result = result + cache_hit;
}else{
result = result + cache_miss;
}
if(queue.size()<=cacheSize){
queue.add(city);
}else{
queue.remove();
queue.add(city);
}
}
System.out.println(result);
}
}테스트 케이스 하나에서 miss가 난 코드
2 , ["Jeju", "Pangyo", "NewYork", "newyork"] , 16
→ 원인은 대소문자를 구분하지 않는다고 했음
import java.util.LinkedList;
import java.util.Queue;
public class programmers_cache {
public static String[] toUpperArray(String[] arr){
String[] result = new String[arr.length];
for(int i=0;i<arr.length;i++){
result[i] = arr[i].toUpperCase();
}
return result;
}
public static void main(String[] args) {
String[] cities = {"Jeju", "Pangyo", "NewYork", "newyork"};
//{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};
//{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
//{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"};
int cacheSize = 2;
int cache_hit = 1;
int cache_miss = 5;
int result = 0;
Queue<String> queue = new LinkedList<>();
for(String city : toUpperArray(cities)){
if (queue.contains(city.toUpperCase())){
result = result + cache_hit;
}else{
result = result + cache_miss;
}
System.out.println(queue);
System.out.println(result);
if(queue.size()<=cacheSize){
queue.add(city);
}else{
queue.remove();
queue.add(city);
}
}
System.out.println(result);
}
}그래서 원인을 제거하기 위해 city 배열을 대문자로 변경해주는 함수를 하나 만들었다.
여기에서 7,9,11 ~ 20번에서 테스트케이스를 통과하지 못함.
큐를 이용한 풀이를 찾게되어서 해당 풀이를 해석하고 이해해보고자 함.
class Solution {
public int solution(int cacheSize, String[] cities) {
int time = 0;
//타임이 왜 들어가는 걸까 ? ---* 1 *---
if (cacheSize == 0) {
return cities.length * 5;
}
//cacheSize가 0일 경우 예외처리 ---* 2 *---
Queue<String> queue = new LinkedList<>();
// 큐 선언
for (int i = 0; i < cities.length; i++) {
boolean hit = ((LinkedList<String>) queue).removeFirstOccurrence(cities[i].toUpperCase());
//이해가 안감 ---* 3 *---
queue.add(cities[i].toUpperCase());
//큐에 데이터를 넣는 부분
time += 1;
//데이터가 들어가면 무조건 +1
if (!hit) {
//hit를 하지 못한 경우
time += 4; //데이터를 한번 넣으면 무조건 1이 들어간다는 가정하에 진행하기 때문에 4를 한번 더 더해준다.
//hit인 경우는 무조건 데이터가 중복되었다는 소리이기 때문에 큐의 크기가 커지지 않는다 (조건문)
if (queue.size() > cacheSize) {
String removed = ((LinkedList<String>) queue).removeFirst();
}
//항상 지워지는 것은 옛날에 들어온 데이터 ---* 4 *---
}
}
int answer = time;
return answer;
}
}-
time이라는 변수를 이용하여 걸리는 시간을 계산함 -
cacheSize == 0일 경우 캐시에 데이터를 저장하지 않기 때문에 모든 데이터를 넣는 데 5 * 갯수 만큼의 시간이 걸린다 → 이것을 예외로 처리해주었다. -
이 부분은 코드가 길어서 따로 분석해보려고 가져왔다.
removeFirstOccurrence는 실행속도측면에서 오래된것부터 탐색하기때문에 많은 향상을 시킨다!즉, 큐에 들어온지 가장 오래된 것부터 탐색하여 비슷한 문자열이 있다면
hit에 true 를 리턴할 것이다.나의 코드와 이 코드의 결정적인 차이는 이 코드에서 발생한 것으로 보인다. 속도 문제.
내 경우에는 contains을 통해 다 뒤지는 로직으로 찾았다면, 해당 코드는 가장 오래된 코드부터 뒤지는 것이다. 즉, 큐의 특성을 제대로 활용하지 못한 로직이였던 것.
boolean hit = ((LinkedList<String>) queue).removeFirstOccurrence(cities[i].toUpperCase()); -
LinkedList가 가지고 있는 메서드를 적절하게 잘 활용하여 나중에 가장 먼저 들어온 데이터가 가장 먼저 삭제되도록 함.
나의문제점
→ 큐를 사용한다는 아이디어는 좋았지만, 큐를 제대로 활용하지 못했고 큐 자체가 왜 링크드 리스트를 사용하는지 알지못해 해당 사항을 제대로 사용하지 못함 .
수정한 코드
import java.util.LinkedList;
import java.util.Queue;
public class programmers_cache {
public static String[] toUpperArray(String[] arr){
String[] result = new String[arr.length];
for(int i=0;i<arr.length;i++){
result[i] = arr[i].toUpperCase();
}
return result;
}
public static void main(String[] args) {
String[] cities = {"Jeju", "Pangyo", "NewYork", "newyork"};
//{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};
//{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
//{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"};
int cacheSize = 2;
int result = 0;
Queue<String> queue = new LinkedList<>();
for(String city : cities){
boolean hit = ((LinkedList<String>)queue).removeFirstOccurrence(city.toUpperCase());
queue.add(city.toUpperCase());
result += 1;
if(!hit){
result +=4;
if(queue.size()>cacheSize)
{
String removed = ((LinkedList<String>)queue).removeFirst();
}
}
}
System.out.println(result);
}
}
