从头开始具有双链表的LRU缓存-moveToHead(Java) [英] LRU cache with Doubly Linked List from scratch - moveToHead (Java)
问题描述
我已经实现了一个简单的LRU缓存，它是从头开始手动编写的双链表.缓存中填充了以数字(整数)ID区分的对象请求.这些请求对象被生成为一组L≤N的L个随机独立且相同分布的请求的流. L个预定义的Request对象，并一个接一个地到达缓存(即以串行方式).然后，我检查高速缓存是否命中或未命中，以及当前高速缓存大小是否已达到最大高速缓存大小，然后根据情况，将请求的项插入高速缓存或从请求的项中替换LRU高速缓存的项.
I have implemented a simple LRU cache as a doubly linked list written manually from scratch. The cache is filled with objects Request distinguished by their numeric (integer) ID. These Request objects are generated as a stream of L random independent and identically distributed requests for a set of N < L predefined Request objects and arrive to the cache one by one (i.e. in a serial fashion). Then I check for cache hit or miss and if the current cache size has reached the maximum cache size and then, depending on the case, I perform insertion of the requested item to the cache or replacement of the LRU cached item from the requested item.
缓存的操作之一是:当我遇到缓存命中时，如果所请求的项目不在头部，则必须将其移到那里.
One of the operations of the cache is the following: when I have a cache hit, then if the requested item is not in the head, it has to be moved there.
例如，假设高速缓存的最大大小为M = 4，并且在给定时间的内容如下:
As an example, let's say that the cache has max size M = 4 and its contents at a given time are as follows:
项目:7 | 3 | 4 | 5
Item: 7 | 3 | 4 | 5
缓存位置索引:0 | 1 | 2 | 3(0为头，3为尾)
Cache position index: 0 | 1 | 2 | 3 (0 is head, 3 is tail)
现在，例如，如果我们有第4个项目的缓存命中，则由于该项目不在缓存的开头，因此应将其移动到那里，结果将是:
Now if we have for example a cache hit for the item 4, since this item is not located at the head of the cache, it should be moved there and the result will be:
项目:4 | 7 | 3 | 5
Item: 4 | 7 | 3 | 5
缓存位置索引:0 | 1 | 2 | 3(0为头，3为尾)
Cache position index: 0 | 1 | 2 | 3 (0 is head, 3 is tail)
但是，当我运行代码时，结果却是这样:
However, when I run the code the result is this instead:
项目:4 | 7 | 3 | 4 | 5
Item: 4| 7 | 3 | 4 | 5
缓存位置索引:0 | 1 | 2 | 3 | 4(0是头，4是尾)
Cache position index: 0 | 1 | 2 | 3 | 4 (0 is head, 4 is tail)
换句话说，相关项(在此示例中为项4)不会从高速缓存中删除，而是添加到磁头中，而只是添加到磁头中.因此，高速缓存大小增加了1(在此示例中，它已变为5，大于最大高速缓存大小M = 4).
In other words, the relevant item (in this example, item 4) is not removed from the cache and then added to the head, but it is simply added to the head. Therefore, cache size is increased by 1 (in this example, it has become 5, which is greater than the max cache size M = 4).
以下是相关代码，以及说明我认为问题本质的注释:
Here is the relevant code, along with a comment that shows I think the nature of the problem:
public void moveToHead(Request request) {
if(request != head) {
// set previous node equal to the requested item
request.left = request;
// --> if I set here request = null; then I will move to the head a null object!!! What to do? <--
// move requested item to head
head.left = request;
request.right = head;
head = request;
}
}
正如我声明的那样，如果在代码的第一行之后我将对象请求设置为null以便将其删除，那么接下来的代码行将移至一个null对象的开头.怎么解决呢?我假设我必须在下面的代码中使用一个临时的Request变量，但是我还没有弄清楚如何做到这一点.
As I state to the comment, if after the first line of code I set the object request to null in order to remove it, then the following lines of code will move to the head a null object. How to solve this? I assume I have to use a temporal Request variable in the following piece of code, but I haven't figured out yet how to do it.
推荐答案
为此变量 head 的工作是由一个虚拟变量初始化的:
For this to work variable head is initialized by a dummy:
head = new Request();
head.left = head;
head.right = head,
对于缓存命中，请先从列表中删除条目:
For the cache hit, remove the entry from the list first:
request.left.right = request.right;
request.right.left = request.left,
然后将其添加到列表头:
Then add it to the list head:
request.left = head;
request.right = head.right;
request.right.left = request;
head.right = request;
也许可以在这里看到一些实际的实现: https://github.com/headissue/cache2k/blob/master/core/src/main/java/org/cache2k/impl/LruCache.java
Maybe see some real world implementation here: https://github.com/headissue/cache2k/blob/master/core/src/main/java/org/cache2k/impl/LruCache.java
祝你好运！
这篇关于从头开始具有双链表的LRU缓存-moveToHead(Java)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
