gpt4 book ai didi

java - 从头开始使用双向链表的 LRU 缓存 - moveToHead (Java)

转载 作者:行者123 更新时间:2023-12-01 13:19:06 25 4
gpt4 key购买 nike

我已经实现了一个简单的 LRU 缓存,作为从头开始手动编写的双向链表。缓存中充满了通过数字(整数)ID 区分的对象请求。这些 Request 对象作为一组 N < L 预定义 Request 对象的 L 个随机独立且相同分布的请求流生成,并一个接一个地到达缓存(即以串行方式)。然后,我检查缓存命中或未命中,以及当前缓存大小是否已达到最大缓存大小,然后根据情况,将请求的项目插入到缓存中,或者从请求的项目中替换 LRU 缓存的项目。

缓存的操作之一如下:当我命中缓存时,如果请求的项不在头部,则必须将其移动到那里。

举个例子,假设缓存的最大大小 M = 4,并且其在给定时间的内容如下:

项目:7 | 3 | 4 | 5

缓存位置索引:0 | 1 | 2 | 3(0为头,3为尾)

现在,如果我们有第 4 项的缓存命中,由于该项不位于缓存的头部,因此应该将其移动到那里,结果将是:

项目:4 | 7 | 3 | 5

缓存位置索引:0 | 1 | 2 | 3(0为头,3为尾)

但是,当我运行代码时,结果是这样的:

项目:4| 7 | 3 | 4 | 5

缓存位置索引:0 | 1 | 2 | 3 | 4(0为头,4为尾)

换句话说,相关项(在本例中为项 4)并没有从缓存中删除然后添加到头部,而是简单地添加到头部。因此,缓存大小增加1(在本例中,它变为5,大于最大缓存大小M = 4)。

这是相关代码,以及显示我认为问题本质的评论:

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;

}

}

正如我在评论中所说,如果在第一行代码之后我将对象请求设置为空以将其删除,那么以下代码行将移动到空对象的头部。怎么解决这个问题呢?我假设我必须在下面的代码中使用临时请求变量,但我还没有弄清楚如何做到这一点。

最佳答案

为此,变量 head 由虚拟变量初始化:

head = new Request();
head.left = head;
head.right = head,

对于缓存命中,首先从列表中删除条目:

request.left.right = request.right;
request.right.left = request.left,

然后将其添加到列表头:

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

祝你好运!

关于java - 从头开始使用双向链表的 LRU 缓存 - moveToHead (Java),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22196377/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com