3. 캐시(난이도: 하) - Python3.6.1

1.풀이방법

 

LRU(Least Recently Used)알고리즘을 사용한다.

:LRU알고리즘은 페이지 교체 전략 중의 하나로 사용한지 가장 오래된 항목부터 버리는 방식이다.

같은 도시이름이라도 대소문자에 따라서 다르게 인식할 수 있으니 모두 소문자로 통일한다음 캐시에 적재한다.

캐시에 새롭게 추가될 경우 cache miss - 5 , 캐시에 데이터가 있을 경우 cache hit - 1 

2.코드

def Question3(cacheSize,cities):

    if cacheSize<0 or cacheSize > 30: #1

        return 'out of range!'

    if cacheSize == 0: #2

        return len(cities)*5

    cities = [x.lower() for x in cities] #3

    page = [0 for i in range(cacheSize)] #4

    rank = [0 for i in range(cacheSize)] #5

    latestValue = 1

    cacheTime = 0

    for i in range(len(cities)): #6

        if cities[i] in page: #7

            Check_num = page.index(cities[i])

            rank[Check_num] = latestValue

            latestValue += 1

            cacheTime += 1 #cache hit

        else: #8

            Check_num = getLeastRecently(rank)

            page[Check_num] = cities[i]

            rank[Check_num] = latestValue

            latestValue += 1

            cacheTime += 5 #cache miss

    return cacheTime #10

def getLeastRecently(rank): #9

    latestValue = rank[0]

    index = 0

    for i in range(len(rank)):

        if latestValue > rank[i]:

            latestValue = rank[i]

            index = i

    return index

3.코드설명

#1 캐시사이즈가 0보다 작거나 30보다 크면 'out of range!' 를 반환한다.

#2 캐시사이즈가 0일 경우에 데이터가 들어올때마다 cache miss 이므로 도시갯수*5 를 반환한다.

#3 입력된 도시이름을 모두 소문자로 변환한다.(같은도시라도 다르게 인식할수가 있음)

#4 입력된 캐시사이즈만큼 배열을 만든다.

#5 DB캐시에서 가장오래된값을 항목을 찾기위한 배열을 만든다.

#6 도시갯수만큼 반복문을 돌린다.

#7 DB캐시에 도시이름이 있는데 다시 들어왔을경우 최신값으로 업데이트 후 cache hit 시간을 저장한다.

#8 DB캐시에 도시이름이 없을경우 도시이름을 저장,최신값으로 업데이트 후 cache miss 시간을 저장한다.

#9 DB캐시에서 교체해야될 인덱스를 반환해준다.(가장 오래된항목)

#10 합산된 시간을 반환해준다.

4.결과 

>>> Question3(3,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA'])

50

>>> Question3(3,['Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul'])

21

>>> Question3(2,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome'])

60

>>> Question3(5,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome'])

52

>>> Question3(2,['Jeju', 'Pangyo', 'NewYork', 'newyork'])

16

>>> Question3(0,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA'])

25