LRU cache (Swift)

https://medium.com/@prateektiwari.in/what-is-lru-cache-and-its-implementation-what-data-structure-should-be-used-2f8004489fa2

LRU Cache - LeetCode

 

• cache 가 full 이면 가장 오래전에 사용한 애를 cache 에서 쫒아내야한다.
• O(1) 로 구현해야 한다.

필요한 조건 분석

• fast lookup O(1)
• fast removal O(1)
• least recently used 기록

fast access / look up 을 생각하면 HashMap 이 생각나야 한다.

fast removal / least recently used 를 생각하면 Doubly LinkedList가 생각나야 한다.

필요한 코드

• Node: 이중 연결 리스트를 위한 노드 클래스
• Dictionary: hashmap [key:Node] 로 구성됨
• head: 연결리스트의 head pointer (노드 추가할 때 사용)
• tail: 연결리스트의 tail pointer (노드 삭제할 때 사용
• add(_:Node): 연결 리스트에서 head 뒤에 삽입하는 함수
• remove(_: Node): 연결 리스트에서 노드 삭제 함수

get

1. hashmap 에 없으면 -1을 리턴한다.
2. hashmap 에 있다면 값을 반환하고 연결리스트를 업데이트 해준다
   (update: remove -> add)

put

1. hashmap 에 없다면 hashmap 에 추가하고 연결 리스트에도 추가한다. (add)
2. hashmap 에 있다면 업데이트 해준다.
   (update: remove -> add)
3. capacity 를 확인하고 용량이 넘었으면 tail.prev 노드를 삭제한다. (제일끝)

 

전체 코드

class LRUCache {
    class Node {
        var prev, next : Node?
        var key, value:  Int
        init(key: Int, value: Int) {
            self.key = key
            self.value = value
        }
    }
    
    private let capacity: Int
    private var currentSize: Int
    private var hashMap: [Int:Node] = [:]
    private let head, tail : Node?
    
    init(_ capacity: Int) {
        self.capacity = capacity
        self.currentSize = 0
        self.head = Node(key: -1, value: -1)
        self.tail = Node(key: -1, value: -1)
        head?.next = tail
        tail?.prev = head
    }
    
    func get(_ key: Int) -> Int {
        printCache()
        if hashMap[key] == nil {
            return -1
        }
        //update queue
        remove(node: hashMap[key])
        add(node: hashMap[key])
        return hashMap[key]!.value
    }
    
    func put(_ key: Int, _ value: Int) {
        printCache()
        let newNode = Node(key: key, value: value)
        if hashMap[key] == nil {
            hashMap[key] = newNode
            add(node: newNode)
            currentSize += 1
        }else {
            remove(node: hashMap[key])
            hashMap[key] = newNode
            add(node: newNode)
        }
        
        if capacity < currentSize {
            hashMap.removeValue(forKey: tail!.prev!.key)
            remove(node: tail?.prev)
            currentSize -= 1
        }
    }
    
    private func add(node: Node?) {
        // head node head.next
        let next = head?.next
        head?.next = node
        node?.prev = head
        node?.next = next
        next?.prev = node
    }
    private func remove(node: Node?) {
        // node.prev node node.next
        node?.prev?.next = node?.next
        node?.next?.prev = node?.prev
    }
    private func printCache(){
        var curr = head
        while curr != nil {
            print(curr!.value, terminator: " ")
            curr = curr?.next
        }
        print("\n-----")
    }
}
// 새로운 노드를 추가할 떄는 head 뒤에 붙인다.
// 삭제하는 노드는 tail 앞에 노드를 삭제한다.

var lRUCache = LRUCache(3);
lRUCache.put(1, 1)
lRUCache.put(2, 2)
lRUCache.put(3, 3)
lRUCache.put(4, 4)
print(lRUCache.get(4))
print(lRUCache.get(3))
print(lRUCache.get(2))
print(lRUCache.get(1))
lRUCache.put(5, 5)
print(lRUCache.get(1))
print(lRUCache.get(2))
print(lRUCache.get(3))
print(lRUCache.get(4))
print(lRUCache.get(5))

 

---