LRU is still useful, sometimes for cache management. Limited memory, focus on key resources

(And interviews)

To learn LRU, the first step is to establish an intuitive understanding

The description of LRU is concise, limited in capacity, and the most recently used resources are listed first.

Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. It should support the following operations: get for data and PUT for writing data.

Get (key) – Gets the value of the key if it exists in the cache (always positive), otherwise -1 is returned.

Write data PUT (key, value) – Writes the data value of the key if it does not exist. When the cache reaches its maximum capacity, it should remove the least-recently used data values before writing new data to make room for new data values.

A simulation

There are two green cells below, representing the capacity of this LRU, two

Put node 1 first, capacity 2, is currently empty, directly put

Node 2, capacity 2, current number 1, can be directly put

Then read node 1, the current hash table has, return to normal, this node is the latest node

Add node 3. When the current number reaches its capacity, delete the oldest one before adding a new one.

How to delete, start from the current node, follow the arrow count. Count to the number of capacity, do not repeat the node, all want. (Remember to skip, read the value of the node)

Count to the number of capacity, do not repeat the node, the previous one does not repeat the node, is to be deleted. (Remember to skip, read the value of the node)

Because the current node is the most recently used, the more arrow direction, the more previously used, (the same element, the first times, is valid)

Deleting Controller 2

If node 2 cannot be read, -1 is returned

In the end:

Data structure:

Hash tables (dictionaries in Swift) and double-linked lists are used.

Key-value access, of course, hash table.
To ensure that newly inserted and used elements come first, and elements that haven’t been used for a long time come last, create a linked list.

Header element, most recently used. Tail-oriented elements are used less and less these days

When the number of elements exceeds the capacity, we need to delete tail elements, we need to have a tail pointer record, with tail Pointers, to delete the last element, we need to find its last pointer to operate, we need to have a precursor. (or the pointer before the pointer)

There is a precursor. List elements naturally find their next, or successor. (Inherent properties of linked lists)

Linked lists have predecessors and successors, so they are double linked lists.

On the other hand, nodes in a double-linked list can be easily self-deleted without the assistance of other Pointers

Simple and crude, achieve an LRU, O (1) complexity

LRU can be divided into two parts: data writing and data reading

First write, write, process inside just have data, convenient debugging read

Design the part stored

Case by case,

  • If the element you want to insert is already in the list, by key.

To maintain the order of the LRU of the linked list, it is necessary to put it in the first place, and change its front and back Pointers, as well as the related nodes.

Delete it, insert it into the head node,

I’m also going to update his value, maybe the value of this key has changed.

  • If the element you want to insert is no longer in the list, according to key.

Three more scenarios to consider,

If the first element is inserted, the structure is created, with a false head node followed by a false tail node

If the existing element is full, remove the last element, which is the least recently used one

In the last case, everything is fine. Insert the new node into the first one in the header.

Class DLinkedNode {// Delete the last node, to synchronize the hash table. The hash table also needs to be used when you delete itletkey: Int var val: Int var prior: DLinkedNode? var next: DLinkedNode? init(_ key: Int, value: Int) { self.key = key val = value } } class LRUCache { var dummyHead = DLinkedNode(0, value: 0) var dummyTail = DLinkedNode(0, value: 0) var capacity: Int var container = [Int: DLinkedNode]() var hasCount: Int = 0 init(_ capacity: Int) { self.capacity = capacity } func put(_ key: Int, _ value: Func insertHead(_ node: DLinkedNode){func insertHead(_ node: DLinkedNode){letformer = dummyHead.next former? .prior = node dummyHead.next = node node.prior = dummyHead node.next = former } func deleteNode(_ node: DLinkedNode){ node.prior? .next = node.next node.next? .prior = node.prior node.prior = nil node.next = nil } funcdeleteTail() {if lettoDel = dummyTail.prior{ toDel.prior? .next = dummyTail dummyTail.prior = toDel.prior container.removeValue(forKey: toDel.key)
        }
    }
}


Copy the code
Design the part that reads

The reading part is relatively simple

If there’s no key in the hash table, return -1, no key

If there is a key in the hash table, find the corresponding node and return the value. This node is also updated to the first node in the header. So in a linked list, delete, insert to the head.



class DLinkedNode {
    letkey: Int var val: Int var prior: DLinkedNode? var next: DLinkedNode? init(_ key: Int, value: Int) { self.key = key val = value } } class LRUCache { var dummyHead = DLinkedNode(0, value: 0) var dummyTail = DLinkedNode(0, value: 0) var capacity: Int var container = [Int: Var hasCount: Int = 0 init(_ capacity: Int) {self.capacity = capacity} func get(_ key: Func put(_ key: Int, _ value: Int) {if letContainer [key]{node.val = value deleteNode(node) insertHead(node)}else{
            ifNext = dummyTail dummyTail. Prior = dummyHead}ifHasCount >= capacity{hasCount -= 1 deleteTail()} hasCount += 1 if no, insert the head nodelet node = DLinkedNode(key, value: value)
            insertHead(node)
            container[key] = node
        }
    }
    
    func insertHead(_ node: DLinkedNode){
        letformer = dummyHead.next former? .prior = node dummyHead.next = node node.prior = dummyHead node.next = former } func deleteNode(_ node: DLinkedNode){ node.prior? .next = node.next node.next? .prior = node.prior node.prior = nil node.next = nil } funcdeleteTail() {if lettoDel = dummyTail.prior{ toDel.prior? .next = dummyTail dummyTail.prior = toDel.prior container.removeValue(forKey: toDel.key)
        }
    }
}


Copy the code
It can be seen that the key performance of LRU lies in the use of structural recording and retention

So here’s the head and the tail of the list, updated all the time. The order of the linked list elements conforms to LRU

The linked list is updated every time it is accessed (except when the key is not present)

Easy to debug, even better. Overwrote the var description of NSObject.

Last full version:

Better yet, fake head and tail lists can be built from the start, so you don’t have to judge each time you write an element


class DLinkedNode: NSObject {
    letkey: Int var val: Int var prior: DLinkedNode? var next: DLinkedNode? Init (_ key: Int, value: Int) {self.key = key val = value} String{ var result = String(val) var point = priorwhile let bee = point{
            result = "\(bee.val) -> " + result
            point = bee.prior
        }
        point = next
        while let bee = point{
            result = result + "-> \(bee.val)"
            point = bee.next
        }
        returnResult}} class LRUCache {// how to change O (n) to O (1). Var dummyHead = DLinkedNode(0, value: 0) var dummyTail = DLinkedNode(0, value: 0) var capacity: Int var container = [Int: DLinkedNode]() var hasCount: Int = 0 init(_ capacity: Next = dummyTail dummyTail. Prior = dummyHead} func get(_ key: Int) -> Int {// There is a refresh mechanismif let node = container[key]{
            deleteNode(node)
            insertHead(node)
            return node.val
        }
        else{
            return -1
        }
    }
    
    func put(_ key: Int, _ value: Int) {
        if letContainer [key]{node.val = value deleteNode(node) insertHead(node)}else{
            ifHasCount >= capacity{hasCount -= 1 deleteTail()} hasCount += 1 if no, insert the head nodelet node = DLinkedNode(key, value: value)
            insertHead(node)
            container[key] = node
        }
    }
    
    func insertHead(_ node: DLinkedNode){
        letformer = dummyHead.next former? .prior = node dummyHead. Next = node node.prior = dummyHead node. Next = former} Func deleteNode(_ node: DLinkedNode){node. Prior? .next = node.next node.next? .prior = node.prior node.prior = nil node.next = nil } funcdeleteTail() {if lettoDel = dummyTail.prior{ toDel.prior? .next = dummyTail dummyTail.prior = toDel.prior container.removeValue(forKey: toDel.key)
        }
    }
}


Copy the code