[연속 캐시]

[문제]

최신 마이크로콘트롤러를 최대한 저렴하게 만들기 위해 매우 간단한 캐쉬를 설계했다. 프로세서는 0에서부터 n-1로 숫자가 매겨진

int n개의 바이트를 가진 느린 메모리 시스템과 연결된다. 캐쉬는 빠른 접근을 위해 이 중에서 int k개의 카피를 한번에 가지고 있다. 캐쉬는 base address를 가지고 있으며 base, base+1, ..., base+k-1로 숫자 매겨진 바이트들의 카피를 가지고 있다. 프로그램이 바이트를 읽을 때, 캐쉬 제어기는 다음과 같은 알고리즘을 따라 동작한다:

• 기존의 base address와 차이를 최소화하여서 필요한 바이트를 가진 k개의 새로운 범위의 바이트를 찾는다. 필요한 바이트가 이미 캐쉬에 존재한다면 base address는 그대로 유지됨을 유의하라.
• 기존의 범위에는 포함이 안되고 새로운 범위에만 포함되는 바이트들을 메모리에서 읽어서 캐쉬를 새 범위로 업데이트하고 새로운 범위에는 없고 기존의 범위에만 있는 바이트들을 버린다.
• 필요한 바이트를 프로그램에 반환한다.

당신은 프로그램의 성능을 테스트하기 위해 얼마나 많은 바이트들이 메모리에서 읽어지는지 확인하고 싶다. 프로그램이 읽는 바이트의 개수는 읽어들이는 순서에 맞게

vector<int> addresses 에 주어져있다. 프로그램이 시작할 때 base address는 0이다.

풀이 1) - python

class Solution:
    def solution(self, n, k, addresses):
        c_start=answer=0
        c_end=k-1
        
        for i in addresses:
            if i>c_end:
                if i > c_end+k-1:
                    answer+=k
                else:
                    answer+=i-c_end
                c_end=i
                c_start=i-k+1
            elif i<c_start:
                if i+k-1 < c_start:
                    answer+=k
                else:
                    answer+=c_start-i
                c_start=i
                c_end=i+k-1
        return answer

풀이 2) - python

class Solution:
    def solution(self, n, k, addresses):
        answer = 0
        cache = [0,k-1] #캐시를 전부 리스트로 하지 말고 가상으로 이 범위에 있다고 생각하고 계산하는게 훨씬 빠르게 가능
        
        for i in addresses:
            temp = []
            
            if i <= cache[-1] and i >= cache[0]: #안에 들어있으면 패스!
                pass
            
            elif i > cache[-1] : # 더 크면 큰쪽으로 선언 후 차이 비교
                temp=[i+1-k,i]
                addaral = 0
                if cache[-1] >= temp[0] : #겹친다면
                    addaral = k - (cache[-1] - temp[0] + 1) #겹치는 수를 계산
                else : 
                    addaral = k
                answer += addaral
                cache=temp
                
            elif i < cache[0] : # 더 작으면 작은쪽으로 선언 후 차이 비교 모든 경우의 수는 이 세가지 안에 들어옴으로 else로 써도 상관없지만, 시각 용이성을 위해 이와 같이 적습니다.
                temp=[i,i+k-1]
                addaral = 0
                if temp[-1] >= cache[0] : #겹친다면
                    addaral = k - (temp[-1] - cache[0] + 1) #겹치는 수를 계산
                else : 
                    addaral = k
                answer += addaral
                cache=temp
        
        return answer

풀이 3) - python

class Solution:
    def solution(self, n, k, addresses):
        res=0
        begin=0
        end=k-1
        for a in addresses:
            if a>=begin and a<=end:
                continue
            elif a>end:
                if a-end>=k:
                    res+=k
                else:
                    res+=a-end
                begin=a-k+1
                end=a
            elif a<begin:
                if begin-a>=k:
                    res+=k
                else:
                    res+=begin-a
                begin=a
                end=a+k-1
        return res