lru알고리즘 구현중 마지막 노드 삭제 함수에서 문제가 발생합니다.

조회수 670회
#LRU Algorithm #2
#이전 알고리즘은 시간 복잡도가 높아 캐시가 많을경우 최대 1시간까지도 실행시간이 걸렸었다.

class Cache_memory:

    def __init__(self,_val,_prev=None,_next=None):

        self.val=_val
        self.prev=_prev
        self.next=_next

    def Cache_update(self): #좌우 노드들의 연결을 서로 시키고 나는 맨앞으로 이동 head,tail의 앞뒤에 있는 노드는 아니라고 가정
        tmp=self.prev
        (self.next).prev=tmp #다음 노드의 이전 값을 tmp로 설정
        (self.prev).next=self.next
        self.next=Cache_head.next
        self.prev=Cache_head
        Cache_head.next=self

    def Cache_delete(self): #tail node에서만 사용하는 함수, 전의 노드를 삭제하고, tail.prev->prev.next=tail로 대입한다.
        tmp=self.prev
        self.prev=tmp.prev
        tmp.prev.next=self



def Cache_append(Cache_val):#값이 없을 경우 노드를 head뒤에 추가한다.
    global Cache_tail
    global Cache_head
    global map
    if(map.get(Cache_val)!=None): #map의 이미 객체가 존재할 경우
        Cache_node=map.get(Cache_val)[0]
    else:
        map={Cache_val:[Cache_memory(Cache_val),0]} #존재하지 않을 경우 map에 값을 추가해준다.
        Cache_node=map[Cache_val][0]
    if(Cache_head.next==Cache_tail): #처음 추가하는 것이라면 head-tail이라면
        Cache_tail.prev= Cache_node
    tmp = Cache_head.next
    Cache_head.next = Cache_node
    Cache_node.prev = Cache_head
    Cache_node.next =tmp
    tmp.prev=Cache_node
    Cache_head.val+=1


def _init_Cache(head,tail):
    head.next=tail
    tail.prev=head
    head.val=0

def find(key): #map의 node값이 None이 아니면 key값을 리턴한다. 만약 None이라면 -1을 리턴한다.(리스트안에 없다)
    global map
    if(map.get(key)!=None):
        return key
    else:
        return -1


CACHE_SIZE = 100
  # cache size를 미리 정해준다.

Hit_count =0
Miss_count =0
Cache_request = 0  # id 값을 불러와 임시적으로 저장할 변수

map={} #dict은 key:[node,count]로 관리될 것이다.

Cache_head=Cache_memory(-1)
Cache_tail=Cache_memory(-1)

_init_Cache(Cache_head,Cache_tail)

F = open("./request1.txt", 'r')  # f라는 객체에 파일 request.tr을 일여놓는다.


while(True):
    Cache_request=F.readline()
    if not Cache_request:
        break #""를 읽어오면 EOF이므로 종료한다.
    else:
        Cache_request=int(Cache_request)#읽어온 str문자열을 정수로 바꾼다.
    index=find(Cache_request)
    if(index>=0):#이미 캐시메모리 안에 해당 값이 있다면 그 값의 index=0으로한다 삭제 x
        tmp=map[index][0]
        tmp.Cache_update()
        map[index][1]+=1 #hit count++
    else: #메모리안에 해당 값이 없다면
        Cache_append(Cache_request)
        if(Cache_head.val>CACHE_SIZE):#마지막 캐시 노드의 값을 삭제한다.
             Cache_tail.Cache_delete()

while(True):
    if(Cache_tail.prev!=None):
        print(Cache_tail)
        Cache_tail=Cache_tail.prev
    else:
        break

알고리즘 공부중 lru캐싱 관리 알고리즘을 알게되어 구현해보려고 노력중입니다!
o(N*N)짜리 알고리즘은 간단히 구현했습니다만, 테스트 데이터를 1000만개정도 해보니 1시간정도가 걸려 O(1)짜리 알고리즘을 위해 double linked list+ dictonary 자료구조를 통해서 구현중에 있습니다.
그런데 map이라는 딕셔너리에도 자료 추가가 되지 않고, Cache_tail.Cache_delete()를 사용하게되면 NoneType Error가 발생하더라구요...

Cache_memory Class에서 이전 노드와의 연결을 끊고 이전 노드의 이전 노드와 tail노드가 연결되도록 구현했는데... 어떤게 문제가 되었을까요..?

실제로 tail의 이전 포인터로 연결을 확인해봤을때는 문제 없이 나옵니다.... 고수님들께서 알려주신다면 정말 감사하겠습니다 ㅠㅠㅠ

request1.txt라는 파일은 단순하게 해시 값이 들어있는 파일입니다.

ex)
1
3
4
5

이런식으로요

캐시 메모리보다 dataset이 커지면 Cache_delete()가 호출되어 문제가 발생합니다.

  • 하다가 너무 답이 없어서 코드를 아예 다시짜버렸는데... 이번에는 또 되네요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 참 쉽지가 않습니다..ㅠ 알 수 없는 사용자 2021.4.11 02:59

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)