[1차] 캐쉬(python)

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

컴퓨터 공학과 전공이 아니다 보니 CS 부문에 대해 무지하여 문제를 이해하는데 많은 힌트들이 필요했다. 이 내용은 사실 해당 문제를 풀기 위해서라기 보다는 내가 이해한 Cache 내용에 대한 정리에 가깝다.

Cache

캐시(Cache)는 연산에 필요한 데이터, 값을 미리 가져다 놓는 임시 메모리이다. 캐시가 없다면 CPU가 특정 값을 필요로 하게 된다면 다음과 같은 과정을 거쳐야 한다.

1. CPU는 필요한 데이터의 주소를 지정합니다.
2. 주소는 주기억장치로 전달됩니다.
3. 주기억장치 컨트롤러는 해당 주소에 있는 데이터를 찾기 위해 보조 기억장치로 액세스합니다.
4. 필요한 데이터가 보조 기억장치에 저장되어 있다면, 해당 데이터를 주기억장치로 가져옵니다. 이때 데이터 전송 속도에 따라 시간이 소요됩니다.
5. 주기억장치는 데이터를 CPU로 전달합니다.
6. CPU는 전달받은 데이터를 처리하고 필요한 작업을 수행합니다.

이 과정에서 드는 비용과 시간은 크다. 따라서 CPU 옆에 캐시를 붙여 자주 사용되는 값이나, 사용될 예정인 값을 캐시에 배치해 두게 되면 전체적인 시스템 성능을 향상 시킬 수 있게 된다.

다음은 캐시의 작동 방식이다.

1. CPU는 데이터를 요청합니다.
2. 캐시는 요청된 데이터가 캐시에 있는지 확인합니다. 이를 캐시 미스(cache miss)라고 합니다.
3. 캐시 미스가 발생한 경우, 캐시는 주기억장치로부터 데이터를 가져와 캐시에 저장합니다. 이때 주변 데이터도 함께 가져와 캐시에 저장하는 것이 일반적입니다.
4. CPU는 캐시로부터 데이터를 받아옵니다.
5. CPU가 동일한 데이터에 다시 접근할 때, 캐시 히트(cache hit)가 발생합니다. 이 경우 CPU는 캐시로부터 데이터를 바로 받아올 수 있으므로 주기억장치에 액세스할 필요가 없습니다.

LRU(Least Fast Used)

캐시에 사용되는 알고리즘은 다양하게 존재한다.(FIFO, Random, MRU 등) 이 문제에서는 LRU를 이야기 하므로 이를 기준으로 이야기 해보면, 이 알고리즘은 가장 적게 엑세스 되고, 오래된 데이터를 제거 하는 방식이다. 그림으로 나타내면 다음과 같다.

출처 ) https://xuri.me/2016/08/13/lru-and-lfu-cache-algorithms.html

아래 그림은 cache가 5인 상태이다. 처음 F 까지의 단계는 없던 데이터 이므로 각 데이터들을 캐시에 넣게 된다 이를 cache miss라 한다. 그 후 캐시가 가득찬 후 1) 새로운 것을 push 할때, 가장 오래된 것을 pop 하고 push 한다.(cache miss) 2) 기존의 것을 push 한다면 기존자리를 remove 하고, 다시 push 하게 된다.(cache hit) 이러한 원리로 작동하게 된다. 

 

코드는 다음과 같다.

def solution(cacheSize, cities):
    cities = [j.lower() for j in cities]
    # print(cities)
    cache = []
    answer = 0
    for i in cities:
        if i in cache:
            cache.remove(i)
            cache.append(i)
            answer += 1 # chche hit

        else: # cache miss
            if len(cache) >= cacheSize:
                cache.pop(0)
                cache.append(i)
                answer += 5
            else:
                cache.append(i)
                answer += 5
    return answer