티스토리 뷰
캐시 메모리, Cache Memory
캐시 메모리는 CPU와 주 기억장치(Memory, ram)의 속도차이를 극복하기 위하여 CPU ↔ 주기억장치 사이에 존재하는 고속의 버퍼 메모리이다. 캐시 메모리를 사용하여 CPU가 작업을 빠르게 처리할 수 있다.
CPU는 캐시 메모리에 접근하여 연산에 필요한 명령과 데이터를 읽어 들인다.
만약, CPU가 캐시 메모리에 접근할 때 원하는 데이터가 없다면 캐시 메모리는 주기억장치에 접근하여 데이터를 캐시 메모리에 올려야 된다. -> CPU가 원하는 데이터가 캐시 메모리에 있을 수 있도록 하는 것을 의미한다.
캐시의 작동 원리
- 원본 데이터와 별개로 자주 쓰이는 데이터들을 복사해둘 캐시 메모리를 만든다.
- 데이터 요청이 들어올 경우 캐시 메모리 먼저 탐색한다.
- 캐시에 원하는 데이터가 있다면 주기억장치에 접근하지 않고 캐시의 데이터를 가져온다.
- 캐시 메모리에 원하는 데이터가 없을 경우 주기억장치를 탐색하여 원본 데이터를 가져온다.
- 데이터를 가져오며 캐시 메모리의 내용을 갱신한다. (페이지 교체 알고리즘 사용)
- 캐시 메모리의 공간이 모자라게 될 경우 기존 데이터를 삭제하여 공간을 확보한다.
캐시 메모리에서 필요 데이터를 찾은 경우 hit(적중)라고 한다.
hit rate(적중률) 공식
- hit rate = 적중한 페이지 / 전체 페이지
페이지 교체 알고리즘 종류
| 종류 | 내용 | ||
| Random | 교체될 페이지를 임의로 선정 | ||
| FIFO First In First Out |
가장 먼저 적재된 페이지를 교체 (가장 오래된 페이지 교체) | ||
| LFU Least Frequently Used |
사용 횟수가 가장 적은 페이지 교체 | ||
| LRU Least Recently Used |
가장 오랫동안 사용되지 않는 페이지 교체 | ||
| Optimal | 향후 가장 참조되지 않을 페이지 교체 | ||
| NUR Not Used Recently |
참조 비트와 수정 비트 미사용 페이지 교체 | ||
| SCR Second Chance Replacement |
FIFO의 방식의 응용, 교체되지 않을 기회를 한번 더 준다. 참조 비트가 1일 경우 0으로 변경, 참조 비트가 0일 경우 페이지 교체를 한다. |
||
| ETC ... | |||
FIFO 알고리즘
- 가장 오래있던 페이지와 교체한다.
- 각 페이지가 주기억장치에 적재될 때 마다, 그때의 시간을 기억시켜두고, 주기억장치 내에 가장 오래있었던 페이지를 교체한다.
- 페이지 부재가 많이 발생하는 단점이 있다.
※ Belady 모순 : 프로세스에 할당된 페이지 프레임 수(capacity)가 증가하면 페이지 부재 수가 감소해야 되지만,
오히려 페이지 부재 수가 증가한다.- Table을 이용하여 알아보자
| 0 | 1 | 1 | 2 | 0 | 9 | 8 | 2 | 1 | 0 |
Table의 첫번째 row는 탐색할 데이터를 가리킨다.
나머지 row는 Cache메모리의 크기이다. (capacity)
마지막 row는 Cache메모리에서 데이터를 찾은 경우 o 데이터를 찾지 못한 경우 x로 표시한다.
Column 순차적으로 진행한다.
| 0 | 1 | 1 | 2 | 0 | 9 | 8 | 2 | 1 | 0 |
| 0 / * | 0 / * | 0 / * | 0 / * | 0 / * | 9 | 9 | 9 | 9 / * | 0 |
| 1 | 1 | 1 | 1 | 1 / * | 8 | 8 | 8 | 8 / * | |
| 2 | 2 | 2 | 2 / * | 2 / * | 1 | 1 | |||
| x | x | o | x | o | x | x | o | x | x |
그리고 할당된 이후 가장 오래된 페이지(가장 먼저 적재된 페이지)에 *로 표시를 해두었다.
페이지 적중률(Hit Ratio)은 3/10 (적중한 페이지 / 전체 페이지) 이다.
1. 페이지 0을 할당할 차례이며, 비어있는 페이지 프레임이 있으므로 비어있는 페이지 프레임에 0을 할당한다.
2. 페이지 1을 할당할 차례이며, 비어있는 페이지 프레임이 있으므로 비어있는 페이지 프레임에 1을 할당한다.
3. 페이지 1을 할당할 차례이며, 페이지 프레임에 이미 페이지 1이 할당되어 있으므로 넘어간다.
4. 페이지 2를 할당할 차례이며, 비어있는 페이지 프레임이 있으므로 비어있는 페이지 프레임에 2를 할당한다.
5. 페이지 0을 할당할 차례이며, 페이지 프레임에 이미 페이지 0이 할당 되어있으므로 넘어간다.
6. 페이지 9를 할당할 차례이며, 페이지 프레임이 비어있지 않으므로 적재된지 가장 오래된 0과 교체한다.
7. 페이지 8을 할당할 차례이며, 페이지 프레임이 비어있지 않으므로 적재된지 가장 오래된 1과 교체한다.
8. 페이지 2를 할당할 차례이며, 페이지 프레임에 이미 페이지 2가 할당되어 있으므로 넘어간다.
9. 페이지 1을 할당할 차례이며, 페이지 프레임이 비어있지 않으므로 적재된지 가장 오래된 2와 교체한다.
10. 페이지 0을 할당할 차례이며, 페이지 프레임이 비어있지 않으므로 적재된지 가장 오래된 9와 교체한다.
LFU Cache 알고리즘
- 사용된 횟수가 가장 적은(Least Frequence Used) 페이지와 교체한다.
- 사용한 횟수를 기억할 reference를 각 페이지 별로 가지며, 참조할 때마다 증가
| 0 | 1 | 1 | 2 | 0 | 9 | 8 | 2 | 1 | 0 |
table의 작동 양식은 위에서 정의한 내용과 같다.
| 0 | 1 | 1 | 2 | 0 | 9 | 8 | 2 | 1 | 0 |
| 0 / 1번 | 0 / 1번 | 0 / 1번 | 0 / 1번 | 0 / 2번 | 0 / 2번 | 0 / 2번 | 0 / 2번 | 0 / 2번 | 0 / 3번 |
| 1 / 1번 | 1 / 2번 | 1 / 2번 | 1 / 2번 | 1 / 2번 | 1 / 2번 | 1 / 2번 | 1 / 3번 | 1 / 3번 | |
| 2 /1번 | 2 / 1번 | 9 / 1번 | 8 / 1번 | 2 / 2번 | 2 / 2번 | 2 / 2번 | |||
| x | x | o | x | o | x | x | x | o | o |
페이지 적중률 = 3/10
할당된 횟수를 각 페이지에 표시해두었다.
※ 페이지가 처리되는 순서는 다음과 같다.
1. 페이지 0을 할당할 차례이며, 비어있는 페이지 프레임이 있으므로 비어있는 페이지 프레임에 0을 할당하며 참조count를 1증가시킨다. 1번
2. 페이지 1을 할당할 차례이며, 비어있는 페이지 프레임이 있으므로 비어있는 페이지 프레임에 1을 할당하며 참조count를 1증가시킨다. 1번
3. 페이지 1을 할당할 차례이며, 페이지 프레임에 이미 페이지 1이 할당 되어있으므로 해당 페이지의 참조count를 1증가만 시킨다. 2번
4. 페이지 2을 할당할 차례이며, 비어있는 페이지 프레임이 있으므로 비어있는 페이지 프레임에 2을 할당하며 참조count를 1증가시킨다. 1번
5. 페이지 0을 할당할 차례이며, 프레임에 이미 페이지 0이 할당 되어있으므로 해당 페이지의 참조count를 1증가만 시킨다. 2번
6. 페이지 9를 할당할 차례이며, 페이지 프레임이 비어있지 않으므로, 참조한 횟수가 가장 적은 페이지 2와 교체한 후 참조count를 1 증가시칸다. 1번
7. 페이지 8를 할당할 차례이며, 페이지 프레임이 비어있지 않으므로, 참조한 횟수가 가장 적은 페이지 9와 교체한 후 참조count를 1 증가시칸다. 1번
8. 페이지 2를 할당할 차례이며, 페이지 프레임이 비어있지 않으므로, 참조한 횟수가 가장 적은 페이지 8과 교체한 후 참조count를 1 증가시칸다. 2번
9. 페이지 1을 할당할 차례이며, 프레임에 이미 페이지 1이 할당 되어있으므로 해당 페이지의 참조count를 1증가만 시킨다. 3번
10. 페이지 0을 할당할 차례이며, 프레임에 이미 페이지 0이 할당 되어있으므로 해당 페이지의 참조count를 1증가만 시킨다. 3번
릿코드 LFU Cache 구현 문제
https://leetcode.com/problems/lfu-cache/
LFU Cache - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
LFU Cache 알고리즘 객체를 생성하는 문제이다.
객체의 메서드는 다음과 같다.
- new 메서드로 객체를 정의할 수 있으며, 객체의 크기(페이지 프레임)를 설정한다.
- get 메서드로 key값이 캐시에 존재할 경우 key에 대한 value를 가져온다. key가 없으면 -1을 반환한다.
- put 메서드로 캐시에 페이지를 입력할 수 있으며 key-value 형태로 데이터를 넘겨준다.
주의할 점은 put을 사용할 때 LFU 알고리즘으로 작동되어야 하며, 알고리즘의 시간복잡도는 O(1)이 되어야 한다.
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;
#[derive(Debug)]
struct DoublyLinkedListNode {
val: i32,
prev: Option<Rc<RefCell<DoublyLinkedListNode>>>,
next: Option<Rc<RefCell<DoublyLinkedListNode>>>,
}
impl DoublyLinkedListNode {
fn new(val: i32) -> Self {
DoublyLinkedListNode {
val,
prev: None,
next: None,
}
}
fn disconnect(&mut self) {
if let Some(node) = &self.prev {
node.borrow_mut().next = self.next.as_ref().map(|r| r.clone());
}
if let Some(node) = &self.next {
node.borrow_mut().prev = self.prev.as_ref().map(|r| r.clone());
}
self.prev = None;
self.next = None;
}
}
// 빈도 저장 공간
#[derive(Debug)]
struct Frequency {
val: i32,
ref_count: i32,
freq_map: HashMap<i32, Rc<RefCell<DoublyLinkedListNode>>>,
head: Option<Rc<RefCell<DoublyLinkedListNode>>>,
tail: Option<Rc<RefCell<DoublyLinkedListNode>>>,
}
impl Frequency {
fn new(val: i32) -> Self {
Frequency {
val,
ref_count: 0,
freq_map: HashMap::new(),
head: None,
tail: None,
}
}
fn remove_key(&mut self, key: i32) {
if let Some(old_node) = self.freq_map.get_mut(&key) {
if self.tail.as_ref().map_or(false, |n| Rc::ptr_eq(&n, old_node)) {
self.tail = old_node.borrow().prev.as_ref().map(|r| r.clone());
}
if self.head.as_ref().map_or(false, |n| Rc::ptr_eq(&n, old_node)) {
self.head = old_node.borrow().next.as_ref().map(|r| r.clone());
}
old_node.borrow_mut().disconnect();
self.freq_map.remove(&key);
self.ref_count -= 1;
}
}
fn push_back(&mut self, key: i32) {
let new_node = Rc::new(RefCell::new(DoublyLinkedListNode::new(key.clone())));
if let Some(old_node) = &self.tail {
old_node.clone().borrow_mut().next = Some(new_node.clone());
new_node.borrow_mut().prev = Some(old_node.clone());
self.tail = Some(new_node.clone())
} else {
self.head = Some(new_node.clone());
self.tail = Some(new_node.clone());
}
self.freq_map.insert(key, new_node);
self.ref_count += 1;
}
fn pop_front(&mut self) {
let key = self.head.as_ref().unwrap().borrow().val.clone();
self.remove_key(key);
}
}
#[derive(Debug)]
struct CacheTable {
value: i32,
freq: i32
}
#[derive(Debug)]
struct LFUCache {
capacity: i32,
len: i32,
lowest_freq: i32,
data_info: HashMap<i32, CacheTable>,
freq: HashMap<i32, Frequency>
}
impl LFUCache {
fn new(capacity: i32) -> Self {
LFUCache {
capacity,
len: 0,
lowest_freq: 0,
data_info: HashMap::new(),
freq: HashMap::new(),
}
}
fn get(&mut self, key: i32) -> i32 {
if let Some(item) = self.data_info.get_mut(&key) {
let old_freq = self.freq.get_mut(&item.freq).unwrap();
old_freq.remove_key(key);
if self.lowest_freq == old_freq.val && old_freq.ref_count == 0 {
self.lowest_freq += 1;
}
item.freq += 1;
self.freq.entry(item.freq).or_insert(Frequency::new(item.freq)).push_back(key);
item.value.clone()
} else {
-1
}
}
fn put(&mut self, key: i32, value: i32) {
if let Some(item) = self.data_info.get_mut(&key) {
// cache 메모리에 데이터가 있던 경우
let old_freq = self.freq.get_mut(&item.freq).unwrap();
old_freq.remove_key(key);
if self.lowest_freq == old_freq.val && old_freq.ref_count == 0 {
self.lowest_freq += 1;
}
item.freq += 1;
item.value = value;
self.freq.entry(item.freq).or_insert(Frequency::new(item.freq)).push_back(key);
} else {
// cache 메모리에 데이터가 없음
if self.capacity > 0 {
// table 의 길이와 capacity 가 같은 경우 => cache 메모리 공간이 없는 경우 참조 횟수가 가장 적은 페이지 제거
if self.len == self.capacity {
let lowest_freq = self.freq.get_mut(&self.lowest_freq).unwrap();
self.data_info.remove(&lowest_freq.head.as_ref().unwrap().borrow().val);
lowest_freq.pop_front();
self.len -= 1;
}
self.data_info.insert(key, CacheTable {
value,
freq: 1
});
self.freq.entry(1).or_insert((Frequency::new(1))).push_back(key);
self.len += 1;
self.lowest_freq = 1;
}
}
}
}
pub fn run() {
let mut lfu_cache = LFUCache::new(2);
println!("null");
lfu_cache.put(1, 1);
println!("null");
lfu_cache.put(2, 2);
println!("null");
println!("{}", lfu_cache.get(1));
lfu_cache.put(3, 3);
println!("null");
println!("{}", lfu_cache.get(2));
println!("{}", lfu_cache.get(3));
lfu_cache.put(4, 4);
println!("null");
println!("{}", lfu_cache.get(1));
println!("{}", lfu_cache.get(3));
println!("{}", lfu_cache.get(4));
}
LRU Cache 알고리즘
- 가장 오랫동안 참조되지 않은(Least Recently Used) 페이지를 교체하는 기법이다.
- OS에서 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어떤 페이지와 교체할지를 결정하는 방법이다.
| 0 | 1 | 1 | 2 | 0 | 9 | 8 | 2 | 1 | 0 |
table의 작동 양식은 위에서 정의한 내용과 같다.
| 0 | 1 | 1 | 2 | 0 | 9 | 8 | 2 | 1 | 0 |
| 0 / * | 0 / * | 0 / * | 0 / * | 0 | 0 | 0 / * | 2 | 2 | 2 / * |
| 1 | 1 | 1 | 1 / * | 9 | 9 | 9 / * | 1 | 1 | |
| 2 | 2 | 2 / * | 8 | 8 | 8 / * | 0 | |||
| x | x | x | x | o | x | x | x | x | x |
페이지 적중률 = 1/10
할당한 후 참조된 이후 가장 오래된 페이지에 *로 표시를 해두었다.
※ 페이지가 처리되는 순서는 다음과 같다.
1. 페이지 0을 할당할 차례이며, 비어있는 페이지 프레임이 있으므로 비어있는 페이지 프레임에 0을 할당한다.
2. 페이지 1을 할당할 차례이며, 비어있는 페이지 프레임이 있으므로 비어있는 페이지 프레임에 1을 할당한다.
3. 페이지 1을 할당할 차례이며, 페이지 프레임에 이미 페이지 1이 할당 되어있으므로 넘어간다.
4. 페이지 2를 할당할 차례이며, 비어있는 페이지 프레임이 있으므로 비어있는 페이지 프레임에 2를 할당한다.
5. 페이지 0을 할당할 차례이며, 페이지 프레임에 이미 페이지 0이 할당 되어있으므로 넘어간다.
6. 페이지 9를 할당할 차례이며, 페이지 프레임이 비어있지 않으므로 기존 할당된 페이지와 교체를 해야되며 참조된지 가장 오래된 페이지 1과 교체를 한다.
7. 페이지 8를 할당할 차례이며, 페이지 프레임이 비어있지 않으므로 기존 할당된 페이지와 교체를 해야되며 참조된지 가장 오래된 페이지 2와 교체를 한다.
8. 페이지 2을 할당할 차례이며, 페이지 프레임이 비어있지 않으므로 기존 할당된 페이지와 교체를 해야되며 참조된지 가장 오래된 페이지 0과 교체를 한다.
9. 페이지 1을 할당할 차례이며, 페이지 프레임이 비어있지 않으므로 기존 할당된 페이지와 교체를 해야되며 할당된지 가장 오래된 페이지 9와 교체를 한다.
10. 페이지 0을 할당할 차례이며, 페이지 프레임이 비어있지 않으므로 기존 할당된 페이지와 교체를 해야되며 할당된지 가장 오래된 페이지 9과 교체를 한다.
릿코드 LRU Cache 구현 문제
https://leetcode.com/problems/lru-cache/
LRU Cache - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
LRU Cache 알고리즘 객체를 생성하는 문제이다.
객체의 메서드는 다음과 같다
- new 메서드로 객체를 정의할 수 있으며, 객체의 크기(페이지 프레임)를 설정한다.
- put 메서드로 객체에 페이지를 입력할 수 있으며, key-value 형태로 데이터를 넣는다.
- get 메서드로 key값이 캐시에 존재할 경우 key에 대한 value를 가져온다. key가 없으면 -1을 반환한다.
주의 할 점은 put을 사용할 때 LRU 알고리즘으로 작동해야 된다.
가장 처음 할당된 데이터를 알아야 되고 이럴 때 Doubly linked list를 사용할 수 있다.
사용되는 Data Structure는 Doubly Linked List(2중 연결 리스트)와 Hashmap를 이용한다.
Doubly Linked List(2중 연결 리스트)
노드와 노드가 양방향으로 연결되어 있는 자료구조이다. 각 노드는 value를 저장하는 부분, 이전노드(previous)와 다음노드(next)를 가리키는 부분이 있다. Doubly Linked List는 아래와 같은 모양으로 구
kmj24.tistory.com
use std::rc::Rc;
use std::cell::{RefCell, Ref};
use std::collections::HashMap;
use std::collections::hash_map::Entry;
#[derive(Debug)]
struct DoublyLinkedListNode<T> {
val: T,
prev: Option<Rc<RefCell<DoublyLinkedListNode<T>>>>,
next: Option<Rc<RefCell<DoublyLinkedListNode<T>>>>,
}
impl<T> DoublyLinkedListNode<T> {
fn new(val: T) -> Rc<RefCell<DoublyLinkedListNode<T>>> {
Rc::new(RefCell::new(DoublyLinkedListNode {
val,
prev: None,
next: None,
}))
}
}
// 2중연결 리스트 구현
#[derive(Debug)]
struct DoublyLinkedList<T> {
head: Option<Rc<RefCell<DoublyLinkedListNode<T>>>>,
tail: Option<Rc<RefCell<DoublyLinkedListNode<T>>>>,
length: usize
}
impl<T> DoublyLinkedList<T> where T: Copy {
fn new() -> Self{
DoublyLinkedList {
head: None,
tail: None,
length: 0,
}
}
fn len(&self) -> usize {
self.length
}
fn push_front(&mut self, val: T) -> Rc<RefCell<DoublyLinkedListNode<T>>> {
let new_head = DoublyLinkedListNode::new(val);
match &self.head.take() {
Some(old_head) => {
old_head.borrow_mut().prev = Some(Rc::clone(&new_head));
new_head.borrow_mut().next = Some(Rc::clone(&old_head));
},
_ => {
self.tail = Some(Rc::clone(&new_head));
}
}
self.head = Some(Rc::clone(&new_head));
self.length += 1;
new_head
}
fn push_back(&mut self, val: T) -> Rc::<RefCell<DoublyLinkedListNode<T>>> {
let new_tail = DoublyLinkedListNode::new(val);
match &self.tail.take() {
Some(old_tail) => {
old_tail.borrow_mut().next = Some(Rc::clone(&new_tail));
new_tail.borrow_mut().prev = Some(Rc::clone(&old_tail));
},
_ => {
self.head = Some(Rc::clone(&new_tail));
}
}
self.tail = Some(Rc::clone(&new_tail));
self.length += 1;
new_tail
}
fn pop_front(&mut self) -> Option<T> {
match &self.head.take() {
Some(head_node) => {
match head_node.borrow_mut().next.as_mut() {
Some(next_node) => {
next_node.borrow_mut().prev = None;
self.head = Some(Rc::clone(&next_node));
},
_ => {
self.tail = None;
}
}
self.length -= 1;
Some(head_node.borrow().val)
},
_ => {
None
}
}
}
fn pop_back(&mut self) -> Option<T> {
match &self.tail.take() {
Some(tail_node) => {
match tail_node.borrow_mut().prev.as_mut() {
Some(prev_node) => {
prev_node.borrow_mut().next = None;
self.tail = Some(Rc::clone(&prev_node));
},
_ => {
self.head = None;
}
}
self.length -= 1;
Some(tail_node.borrow().val)
},
_ => {
None
},
}
}
fn remove(&mut self, node: Rc<RefCell<DoublyLinkedListNode<T>>>) -> T {
if node.borrow().prev.is_none() && node.borrow().next.is_none() {
self.head = None;
self.tail = None;
self.length = 0;
return node.borrow().val;
}
let mut rn = node.borrow_mut();
match rn.prev.take() {
Some(prev_node) => {
match rn.next.take() {
Some(next_node) => {
prev_node.borrow_mut().next = Some(Rc::clone(&next_node));
next_node.borrow_mut().prev = Some(prev_node);
},
_ => {
prev_node.borrow_mut().next = None;
self.tail = Some(prev_node);
}
}
},
_ => {
self.head = rn.next.clone();
self.head.as_mut().unwrap().borrow_mut().prev = None;
}
}
self.length -= 1;
rn.val
}
}
// LRU Cache 알고리즘 객체
#[derive(Debug)]
struct LRUCache {
capacity: usize,
link: HashMap<i32, Rc<RefCell<DoublyLinkedListNode<(i32, i32)>>>>,
list: DoublyLinkedList<(i32, i32)>
}
impl LRUCache {
fn new(capacity: i32) -> Self {
LRUCache {
capacity: capacity as usize,
link: HashMap::with_capacity(capacity as usize),
list: DoublyLinkedList::new()
}
}
fn get(&mut self, key: i32) -> i32 {
match self.link.entry(key) {
// key 를 찾았을 경우 해당 value를 return
Entry::Occupied(mut o) => {
let (k, v) = self.list.remove(o.get().clone());
*o.get_mut() = self.list.push_front((k, v));
v
},
_ => {
// key 를 찾지 못한 경우 -1을 return
-1
}
}
}
fn put(&mut self, key: i32, value: i32) {
if self.link.contains_key(&key) {
// key 가 이미 존재할 경우 해당 key 에 대한 노드 제거
self.list.remove(Rc::clone(self.link.get(&key).unwrap()));
} else if self.capacity == self.list.len() {
// 현재 할당된 크기가 최대 크기 한도와 같을 경우 연결 해제
if let Some((k, _v)) = self.list.pop_back() {
self.link.remove(&k);
}
}
self.link.insert(key, self.list.push_front((key, value)));
}
}
fn main() {
let mut lru_cache = LRUCache::new(2);
println!("null");
let (key, value) = (1, 1);
lru_cache.put(key, value);
println!("null");
let (key, value) = (2, 2);
lru_cache.put(key, value);
println!("null");
println!("{}", lru_cache.get(1));
let (key, value) = (3, 3);
lru_cache.put(key, value);
println!("null");
println!("{}", lru_cache.get(2));
let (key, value) = (4, 4);
lru_cache.put(key, value);
println!("null");
println!("{}", lru_cache.get(1));
println!("{}", lru_cache.get(3));
println!("{}", lru_cache.get(4));
}Doubly LinkedList를 사용할 때 핵심은 list의 head가 가장 최신에 참조한 데이터가 오도록 위치시키는 것이다.
'Computer Science > 알고리즘_자료구조' 카테고리의 다른 글
| Greedy algorithm, 탐욕법 (0) | 2022.02.26 |
|---|---|
| [알고리즘] Dijkstra, 다익스트라 알고리즘 (0) | 2021.09.13 |
| [알고리즘] 정렬알고리즘(2) - bubble sort, 버블정렬 (0) | 2021.09.04 |
| [알고리즘] 문자열_알고리즘 KMP 알고리즘 (0) | 2021.08.28 |
| [알고리즘] 정렬 알고리즘(1) - selection sort, 선택정렬 (0) | 2021.07.02 |