Least Recently Used

문제

 

문제풀이

LRU(Least Recently Used) 알고리즘

• 캐시(Cache)에서 메모리를 다루기 위해  사용되는 알고리즘
• 캐시가 사용하는 리소스의 크기는 제한되어 있음
• 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장 및 참조할 수 있어야 함
• 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터를 갱신

코드

function solution(s, w) {
  let answer = Array.from({length: s});

  for(let i = 0; i < w.length; i++) {
    if(!answer.includes(w[i])) { //Cache Miss일 경우
      if(answer.length === s) { //메모리 사이즈가 모두 찼을 경우
        answer.pop(); //가장 최근에 사용된 적 없는 데이터 삭제
        answer.unshift(w[i]);
      } else {  
        answer.unshift(w[i]);
      }
    } else { //Cache Hit일 경우
      let pos = answer.indexOf(w[i]); //해당 작업과 동일하면서 가장 최근에 적재된 데이터 위치를 탐색
      for(let j = pos; j > 0; j--) {
        [answer[j - 1], answer[j]] = [answer[j], answer[j - 1]];
      }
    }
  }
  
  return answer;
}

let size = 5;
let work = [1, 2, 3, 2, 6, 2, 3, 5, 7]
console.log(solution(size, work));

---

function solution(s, w) {
  let answer = Array.from({length: s});

  w.forEach(x => {
    let pos = -1;
    for(let i = 0; i < size; i++) {
      if(answer[i] === x) pos = i;
    }
    if(pos === -1) {
      answer.unshift(x);
      if(answer.length > s) answer.pop();
    }
    else {
      answer.splice(pos, 1); //해당 데이터를 삭제할 경우 자동으로 기존 데이터들은 한칸씩 뒤로 이동
      answer.unshift(x);
    }
  })
  
  return answer;
}

let size = 5;
let work = [1, 2, 3, 2, 6, 2, 3, 5, 7]
console.log(solution(size, work));

 

코드_삽입 정렬

function solution(s, w) {
  let answer = Array.from({length: s});

  w.forEach(x => {
    let pos = -1;
    for(let i = 0; i < s; i++) {
      if(answer[i] === x) { //Cache Hit일 경우
        pos = i; //해당 데이터가 저장된 위치 저장
      }
    }
    if(pos === -1){ //Cache Miss일 경우
      for(let i = s - 1; i >= 1; i--) { //맨 뒤에서부터 맨 앞 이전까지 순회
        answer[i] = answer[i - 1]; //삽입 정렬 수행
      }
    }
    else {
      for(let i = pos; i >= 1; i--) { //Cache Hit일 경우에는 해당 데이터가 저장된 위치부터 순회
        answer[i] = answer[i - 1];
      }
    }
    answer[0] = x; //메모리 상 가장 맨 앞에 저장(삽입 정렬로 인해 가장 맨 앞은 비어져 있음)
  })
  
  return answer;
}

let size = 5;
let work = [1, 2, 3, 2, 6, 2, 3, 5, 7]
console.log(solution(size, work));