OS LRU 파이썬 구현

서론

지금은 취업 준비 중인데요. 면접에서 LRU를 구현하려면 어떻게 할 것이냐는 질문에 페이지마다 타임 카운터 같은 것을 달아서 새로 들어온 페이지는 0으로 두고 페이지가 들어올 때마다 타임 카운터를 1씩 올려서 교체 시에 타임 카운터가 가장 큰 페이지를 버리겠다고 대답했었습니다.

이 방법은 타임 카운터를 한 개씩 올리는 것도 그렇고 타임 카운터가 가장 큰 페이지를 찾는 탐색도 그렇고 시간복잡도 O(n)을 가집니다. 더 효과적인 방법이 없냐고 질문하셔서 대답을 못 했습니다.

그래서 면접이 끝나고 찾아보니 링크드 리스트와 해쉬맵을 사용해서 LRU를 O(1)로 구현하는 방법이 있었습니다. 더 효과적인걸 물어보셨어서 줄이면 O(logn)정도가 되지 않을까 생각했었는데 O(1)의 방법을 사용하고 있다니 신기했습니다.

방법

1. 링크드 리스트로 구현한 큐를 사용합니다. 그리고 head와 tail을 설정합니다. 오래된 페이지가 head 쪽에 가깝고 최근에 들어온 페이지가 tail 쪽에 가깝게 만듭니다. 가장 오래된 페이지와 가장 최근에 들어온 페이지만 구별하면 되기 때문에 이 링크드 리스트에서의 삽입/삭제는 O(1)의 시간복잡도를 가집니다.
2. 문제는 이미 큐에 있는 페이지를 다시 사용했을 때 다시 큐의 마지막 페이지로 넣는 곳인데요. 이 부분은 해쉬맵을 사용하면 인덱스로 링크드 리스트를 탐색하게 되어 시간복잡도 O(1)를 가집니다. (python은 딕셔너리가 해쉬맵과 같은 역할을 하므로 딕셔너리를 사용하였습니다.)
3. 따라서 삽입, 삭제, 탐색 모두 시간복잡도 O(1)를 가지게 됩니다.

구현

if node.key in self.dict: 이 부분이 코드에서 유일하게 탐색하는 부분인데 이 부분도 딕셔너리의 경우 키값을 해쉬맵을 통하여 인덱스로 변경시켜 인덱스로 접근을 하므로 O(1)의 시간 복잡도를 가집니다.

class node:
    def __init__(self, key, prev=None, next=None):
        self.key = key
        self.prev = prev
        self.next = next


class LRU:
    def __init__(self, max_size):
        self.max_size = max_size
        self.dict = {}
        self.dict['head'] = node('head')
        self.dict['tail'] = node('tail')
        self.dict['head'].next = self.dict['tail'].key
        self.dict['tail'].prev = self.dict['head'].key

    def put(self, node):
        if node.key in self.dict:
            # 삭제했다가 다시 넣어주어야함.
            self.dict[self.dict[node.key].prev].next = self.dict[node.key].next
            self.dict[self.dict[node.key].next].prev = self.dict[node.key].prev
            # 그리고 넣어줌
        else:
            if len(self.dict)-2 == self.max_size:
                # 딕셔너리 제일앞 지움(제일 오래 되었다는 뜻)
                tmp = self.dict['head'].next

                self.dict['head'].next = self.dict[self.dict['head'].next].next
                self.dict[self.dict['head'].next].prev = self.dict['head'].key

                self.dict.pop(self.dict[tmp].key)
                # 그리고 넣어줌
            else:
                # 딕셔너리 제일뒤에 넣음(제일 최근에 들어갔단뜻)
                # 그냥 넣으면 됨
                pass

        self.dict[node.key] = node

        self.dict[node.key].prev = self.dict[self.dict['tail'].prev].key
        self.dict[self.dict['tail'].prev].next = node.key

        self.dict['tail'].prev = node.key
        self.dict[node.key].next = self.dict['tail'].key


lru = LRU(5)
page = [1, 2, 3, 2, 3, 4, 3, 1, 5, 2, 6, 7, 8]
for i in page:
    lru.put(node(i))


key = 'head'

while key != None:
    print(f'prev: {lru.dict[key].prev}')
    print(f'key: {lru.dict[key].key}')
    print(f'next: {lru.dict[key].next}')
    print()
    key = lru.dict[key].next

# 결과: 5, 2, 6, 7, 8

prev: None
key: head 
next: 5   

prev: head
key: 5    
next: 2   

prev: 5   
key: 2    
next: 6   

prev: 2   
key: 6    
next: 7

prev: 6
key: 7
next: 8

prev: 7
key: 8
next: tail

prev: 8
key: tail
next: None

시간복잡도

시간 복잡도를 확인하기 위해서 다음과 같이 page 리스트 길이를 10배씩 하면서 실험해보았습니다. 결괏값이 리스트 길이 10배마다 10배가 되는 것처럼 보여서 시간복잡도가 O(n)처럼 보이지만 여기서 n은 for i in page:를 탐색할 때 나오는 n입니다. 즉 반복문 아래로의 코드는 O(1)의 시간복잡도를 가지기 때문에 전체 시간복잡도 O(n)이 나옵니다. 결론적으로 LRU를 링크드 리스트와, 해쉬맵을 통해서 구현하면 시간복잡도 O(1)을 얻을 수 있습니다.

lru = LRU(10)

page = []
for i in range(1, 100): # 100~10000000
    page.append(random.randint(1, 11))
start = time.time()
for i in page:
    lru.put(node(i))
print(f'LRU\tn=100\t\ttime: {time.time()-start:.5f}')

LRU     n=100           time: 0.00000
LRU     n=1000          time: 0.00199
LRU     n=10000         time: 0.01795
LRU     n=100000        time: 0.17903
LRU     n=1000000       time: 1.78895
LRU     n=10000000      time: 17.56030

생각

면접 질문 하나로 배열, 링크드 리스트, 해쉬맵, 운영체제까지 이번에 공부가 정말 많이 됐습니다. 다음번에는 더 잘 대답할 수 있을 것 같습니다.