#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()가 호출되어 문제가 발생합니다.