Sword finger offer II 031 Least recently used cache

The finger of the sword Offer II 031. At least use cache recently

OrderedDict() / LinkedHashMap

python3: OrderedDict() Order refers to the order of insertion .
java: LinkedHashMap<>() Take the iterator of the first element pointing to key：linked_map.entrySet().iterator().next().getKey()

from collections import OrderedDict as OD
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.od = OD()

    def get(self, key: int) -> int:
        if key in self.od: self.od.move_to_end(key)
        return self.od.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.od: del self.od[key]
        if len(self.od) + 1 > self.capacity:
            self.od.popitem(last = False)
        self.od[key] = value

class LRUCache {
    
    Map<Integer, Integer> map = new LinkedHashMap<>();
    int capacity;

    public LRUCache(int capacity) {
            
        this.capacity = capacity;
    }
    
    public int get(int key) {
    
        if(!map.containsKey(key)) return -1;
        int val = map.remove(key);
        map.put(key, val);
        return val;
    }
    
    public void put(int key, int value) {
    
        if(map.containsKey(key)) map.remove(key);
        else if(map.size() + 1 > capacity) map.remove(map.entrySet().iterator().next().getKey());
        map.put(key, value);
    }
}

class LRUCache extends LinkedHashMap<Integer, Integer>{
    
    private int capacity;
    
    public LRUCache(int capacity) {
    
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
    
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
    
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
    
        return size() > capacity; 
    }
}

Double linked list + Hashtable

LRU The cache mechanism can be realized by hash table supplemented by bidirectional linked list .

The two-way linked list stores key value pairs in the order they are used , The key value pair near the head is the most recently used , The key value pairs near the tail are the most unused .

Hashtable （HashMap）, The key of the cached data is mapped to its position in the bidirectional linked list .

First, use the hash table to locate , Find the location of the cache item in the bidirectional linked list , Then move it to the head of the bidirectional list , Can be in O(1) In time to complete get perhaps put operation . The specific method is as follows ：

about get operation , First judgement key Whether there is ：
If key non-existent , Then return to -1;
If key There is , be key The corresponding node is the most recently used node . Locate the position of the node in the bidirectional linked list through the hash table , And move it to the head of the two-way linked list , Finally, the value of the node is returned .

about put operation , First judgement key Whether there is ：
If key non-existent , Use key and value Create a new node , Add the node to the head of the double linked list , And will key And the node is added to the hash table . Then judge whether the number of nodes in the two-way linked list exceeds the capacity , If the capacity is exceeded , Delete the tail node of the bidirectional linked list , And delete the corresponding item in the hash table ;

If key There is , Then with get The operation is similar to , First, locate through the hash table , Then update the value of the corresponding node to value, And move the node to the head of the bidirectional linked list .

Of the above operations , The time complexity of accessing the hash table is O(1), Add a node at the head of the two-way linked list 、 The complexity of deleting nodes at the end of the two-way linked list is also O(1). And move a node to the head of the two-way linked list , Can be divided into 「 Delete the node 」 and 「 Add a node at the head of the two-way linked list 」 Two step operation , Can be in O(1) Within time .

Store the stored elements into the bidirectional linked list in the order of access . One element at a time , Whether it's put still get operation , Move the element to the end of the linked list . This ensures that the head of the linked list is the least recently used element . After realizing the least recently used functions , After adding the hash table, you can realize get and put The complexity of operation time is O(1). Exists in hash table key → The pointer corresponding to the linked list node , Get the corresponding pointer and you can operate the... In the node key and value value .

In the realization of bidirectional linked list , Using a fake head （dummy head） And the pseudo tail （dummy tail） Mark the boundaries , In this way, there is no need to check whether adjacent nodes exist when adding or deleting nodes .

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
        
class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()
        #  Using pseudo head and pseudo tail nodes  
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        #  If  key  There is , First, locate through the hash table , And then to the head 
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            #  If  key  non-existent , Create a new node 
            node = DLinkedNode(key, value)
            #  Add to hash table 
            self.cache[key] = node
            #  Add to the head of the bidirectional list 
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                #  If the capacity is exceeded , Delete the tail node of the bidirectional linked list 
                removed = self.removeTail()
                #  Delete the corresponding entry in the hash table 
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            #  If  key  There is , First, locate through the hash table , Revise  value, And move to the head 
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
    
    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

public class LRUCache {
    
    class DLinkedNode {
    
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {
    }
        public DLinkedNode(int _key, int _value) {
    key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
    
        this.size = 0;
        this.capacity = capacity;
        //  Using pseudo head and pseudo tail nodes 
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
    
        DLinkedNode node = cache.get(key);
        if (node == null) {
    
            return -1;
        }
        //  If  key  There is , First, locate through the hash table , And then to the head 
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
    
        DLinkedNode node = cache.get(key);
        if (node == null) {
    
            //  If  key  non-existent , Create a new node 
            DLinkedNode newNode = new DLinkedNode(key, value);
            //  Add to hash table 
            cache.put(key, newNode);
            //  Add to the head of the bidirectional list 
            addToHead(newNode);
            ++size;
            if (size > capacity) {
    
                //  If the capacity is exceeded , Delete the tail node of the bidirectional linked list 
                DLinkedNode tail = removeTail();
                //  Delete the corresponding entry in the hash table 
                cache.remove(tail.key);
                --size;
            }
        }
        else {
    
            //  If  key  There is , First, locate through the hash table , Revise  value, And move to the head 
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
    
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
    
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
    
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
    
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

python OrderedDict

python Official documents , python 3.6 And after Dict It's in order , But with OrderedDict It's different ,Dict No, move_to_end() Method ,popitem() Optional parameters are not accepted .

1、 Definition

python Chinese Dictionary Dict It's using hash Storage , Because there is no order between the elements .OrderedDict Is stored in the order of insertion An ordered Dictionary of . In addition, according to key, val Sort .

2、 initialization

2.1 First initialize and define a OrderedDict, Then insert according to the key value pair , here dict You can record the order in which the dictionary is inserted

import collections
d = collections.OrderedDict()
d["name"] = "muya"
d["age"] = 25
d["money"] = "Zero"
 
for key, value in d.items():
    print(key, value)
 
#  Output ：
# name muya
# age 25
# money Zero

2.2 Initialize key value pairs when defining , But these initialized contents cannot be orderly . However, the key values inserted into the dictionary later are still in order .

import collections
 
d = collections.OrderedDict(name="muya", age=25, money="Zero")
d["dream"] = "have money"
d["other dream"] = "have gf"
 
for key, value in d.items():
    print(key, value)
 
#  Output ：
# money Zero
# age 25
# name muya
# dream have money
# other dream have gf

3、 Sort

OrderedDict According to the key perhaps val Sort .

dd = {
    'banana': 3, 'apple':4, 'pear': 1, 'orange': 2}
#  Press  key  Sort 
kd = collections.OrderedDict(sorted(dd.items(), key=lambda t: t[0]))
print(kd)
#  according to  value  Sort 
vd = collections.OrderedDict(sorted(dd.items(),key=lambda t:t[1]))
print(vd)
#  Output 
# OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)])
# OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)])

4、 Common functions

import collections 
dic = collections.OrderedDict()
dic.clear()  # clear( Empty the ordered dictionary )
new_dic = dic.copy() # copy( Copy )
 
# fromkeys( Specify a list , Take the values in the list as the dictionary  key, Generate a dictionary )
name = ['tom','lucy','sam']
dic.fromkeys(name)
dic.fromkeys(name, 20)
dic.items() # items( Return from “ Key value pairs make up elements “ A list of )
dic.keys() # keys( Get all the dictionary's key)
dic.value() # values( Get all the dictionary's value, Return a list )
 
# move_to_end( To specify a  key, Put the corresponding  key-value  Move to the last )
dic["name"] = "muya"
dic["age"] = 25
dic["money"] = "Zero"
dic.move_to_end("name")    #  take  name  Move to the last 
dic.move_to_end("money", last=False)   #  Set up  last  by  False,  take  money  Move to the front 
 
# pop( Get specified  key  Of  value, And delete... From the dictionary )
dic.pop("name")           #  Delete  name,  Note that the keyword must be specified  key 
# popitem( Follow the principle of last in first out , Delete the last added element , return  key-value)
dic.popitem()            #  Delete the last added 
dic.popitem(last=False)  #  Delete the first one to join  
# setdefault( Get specified  key  Of  value, If  key  non-existent , Create )
val = dic.setdefault('k5')

5、 And Dict difference

The conventional Dict Designed to be very good at mapping operations . Tracking the insertion order is secondary
OrderedDict Designed to be good at reordering operations . Space efficiency 、 The speed of iteration and the performance of update operations are secondary
OrderedDict In the frequent rearrangement of tasks, it is still better than Dict Better , This makes it more suitable for realizing various LRU cache
OrderedDict Class popitem() Methods have different signatures . It accepts an optional parameter to specify which element to pop up
Pop up the last element ： The conventional Dict Use d.popitem() ,OrderedDict Class uses od.popitem()
Pop up the first element ： The conventional Dict Use (k := next(iter(d)), d.pop(k)) ,OrderedDict Class uses od.popitem(last=False)
Class has one. move_to_end() Method , You can effectively move elements to either end
take K,V Move to the back ： The conventional Dict Use d[k] = d.pop(k) ,OrderedDict Class uses od.move_to_end(k, last=True)
take K,V Move to the front ： The conventional Dict There is no corresponding function ,OrderedDict Class uses od.move_to_end(k, last=False)

OrderedDict object

An ordered dictionary is like a regular Dictionary , But there are some additional features related to sorting operations . Because of the built-in dict Class gains the ability to remember the insertion order （ stay Python 3.7 This new behavior is guaranteed in ）, They become less important .

Some with dict The differences still exist ：

The conventional dict Designed to be very good at mapping operations . Tracking the insertion order is secondary .
OrderedDict Designed to be good at reordering operations . Space efficiency 、 The speed of iteration and the performance of update operations are secondary .
The OrderedDict algorithm can handle frequent reordering operations better than dict. As shown in the recipes below, this makes it suitable for implementing various kinds of LRU caches.

about OrderedDict , The equality operation checks the matching order .
A regular dict can emulate the order sensitive equality test with p == q and all(k1 == k2 for k1, k2 in zip(p, q)).

OrderedDict Class popitem() Methods have different signatures . It accepts an optional parameter to specify which element to pop up .

A regular dict can emulate OrderedDict’s od.popitem(last=True) with d.popitem() which is guaranteed to pop the rightmost (last) item.

A regular dict can emulate OrderedDict’s od.popitem(last=False) with (k := next(iter(d)), d.pop(k)) which will return and remove the leftmost (first) item if it exists.

OrderedDict Class has one. move_to_end() Method , You can effectively move elements to either end .

A regular dict can emulate OrderedDict’s od.move_to_end(k, last=True) with d[k] = d.pop(k) which will move the key and its associated value to the rightmost (last) position.

A regular dict does not have an efficient equivalent for OrderedDict’s od.move_to_end(k, last=False) which moves the key and its associated value to the leftmost (first) position.

Python 3.8 Before , dict The lack of reversed() Method .

class collections.OrderedDict([items])
Return to one dict Instances of subclasses , It has a special method for reordering dictionaries .

3.1 New features .

popitem(last=True)
Ordered Dictionary popitem() Method removes and returns a (key, value) Key value pair . If last It's worth it , Then press LIFO Return key value pairs in last in first out order , Otherwise, press FIFO Return key value pairs in first in first out order .

move_to_end(key, last=True)
Move an existing key to either end of an ordered dictionary. The item is moved to the right end if last is true (the default) or to the beginning if last is false. Raises KeyError if the key does not exist:

d = OrderedDict.fromkeys(‘abcde’)
d.move_to_end(‘b’)
‘’.join(d)
‘acdeb’
d.move_to_end(‘b’, last=False)
‘’.join(d)
‘bacde’

3.2 New features .

Compared with the usual mapping method , The ordered dictionary also provides support for reverse order iteration , adopt reversed() .

OrderedDict The equality test between is order sensitive , Implemented as a list(od1.items())==list(od2.items()) . OrderedDict Objects and other Mapping Equality test , It's a sequence sensitive dictionary test . This allows OrderedDict Replace with any place where the dictionary can be used .

stay 3.5 Version change : OrderedDict The item (item), key (key) And the value (value) View Now support reverse order iteration , adopt reversed() .

stay 3.6 Version change : PEP 468 In favor of keeping the order of keyword parameters , By passing on to OrderedDict Constructor and its update() Method .

stay 3.9 Version change : Add consolidation (|) And update (|=) Operator , For relevant instructions, see PEP 584.

OrderedDict Examples and usage

Create and remember key values Last An ordered dictionary variant of the insertion order is simple . If the new entry overwrites the existing entry , The original insertion position will be changed and moved to the end :

class LastUpdatedOrderedDict(OrderedDict):
    'Store items in the order the keys were last added'

    def __setitem__(self, key, value):
        super().__setitem__(key, value)
        self.move_to_end(key)
 One  OrderedDict  For implementing  functools.lru_cache()  Variants of are also useful :

from time import time

class TimeBoundedLRU:
    "LRU Cache that invalidates and refreshes old entries."

    def __init__(self, func, maxsize=128, maxage=30):
        self.cache = OrderedDict()      # { args : (timestamp, result)}
        self.func = func
        self.maxsize = maxsize
        self.maxage = maxage

    def __call__(self, *args):
        if args in self.cache:
            self.cache.move_to_end(args)
            timestamp, result = self.cache[args]
            if time() - timestamp <= self.maxage:
                return result
        result = self.func(*args)
        self.cache[args] = time(), result
        if len(self.cache) > self.maxsize:
            self.cache.popitem(0)
        return result
class MultiHitLRUCache:
    """ LRU cache that defers caching a result until it has been requested multiple times. To avoid flushing the LRU cache with one-time requests, we don't cache until a request has been made more than once. """

    def __init__(self, func, maxsize=128, maxrequests=4096, cache_after=1):
        self.requests = OrderedDict()   # { uncached_key : request_count }
        self.cache = OrderedDict()      # { cached_key : function_result }
        self.func = func
        self.maxrequests = maxrequests  # max number of uncached requests
        self.maxsize = maxsize          # max number of stored return values
        self.cache_after = cache_after

    def __call__(self, *args):
        if args in self.cache:
            self.cache.move_to_end(args)
            return self.cache[args]
        result = self.func(*args)
        self.requests[args] = self.requests.get(args, 0) + 1
        if self.requests[args] <= self.cache_after:
            self.requests.move_to_end(args)
            if len(self.requests) > self.maxrequests:
                self.requests.popitem(0)
        else:
            self.requests.pop(args, None)
            self.cache[args] = result
            if len(self.cache) > self.maxsize:
                self.cache.popitem(0)
        return result