lru 구현을 향상시키는 방법

Question

해시 테이블 + 링크 된 목록을 사용하여 LRU를 구현했습니다.

해시 테이블에 체인이 있습니다. 코드의 구조는 다음과 같습니다.

struct Node{ 
int value; 
struct Node *next; 
struct Node* head; 
struct Node* tail; 

}; 



struct Node* lruhashtable[10]; 
struct Node* trackHead; 
struct Node* trackTail; 

trackHead 및 trackTail 포인터는 삽입 순서를 추적합니다. 이것은 최근에 사용 된 요소를 제거하는 데 사용됩니다. 나는 하나가 아닌 여러 개의 교체 정책이 있다고 생각하고 있습니다. 따라서 LRU는 무언가의 조합으로 사용됩니다. 따라서 요소에 다시 액세스 할 때 요소가 LRU에서 제거되면 LRU에서 해당 요소를 제거해야합니다.

본질적으로 나는 전체 시퀀스를 유지하고 있으며, 수백만 개의 항목이 있다면 그것은 나쁘다. 우선 순위 대기열 + 해시 테이블을 사용하는 것 외에이 방법을 개선 할 방법이 있습니까

Answer 1

전체 시퀀스를 유지해야하며 올바른 작업을 수행하는 동안 수백만 개의 항목이 있으면 나쁘지 않습니다.

키가 다른 해시 테이블처럼 해시 테이블을 만들고 있습니다. 그런 다음 최근에 사용한 노드를 찾기 위해 연결된 목록을 반복하는 대신 해시 테이블에서 참조를 사용하면됩니다. 가운데에서 분리하고 앞쪽으로 옮깁니다.

링크 된 목록에서 요소를 제거하는 것은 처음부터 노드를 찾을 수 있다면 일정한 시간 동안의 작업입니다. 해시 테이블이 없으면 반복해야하지만 (선형 시간) 해시 테이블이 있으므로 반복 할 필요가 없습니다.