p********7 发帖数: 549 | 1 [1] Design a layer in front of a system which cache the last n requests and
the responses to them from the system.
what data structure would you use to implement the cache in the later to
support following operations.
[a] When a request comes look it up in the cache and if it hits then return
the response from here and do not pass the request to the system
[b] If the request is not found in the cache then pass it on to the system
[c] Since cache can only store the last n requests, Insert the n+1 |
h**k 发帖数: 3368 | 2 链表中的元素的顺序是他们进入cache的先后顺序?
我觉得你的想法是对的。
and
return
request
【在 p********7 的大作中提到】 : [1] Design a layer in front of a system which cache the last n requests and : the responses to them from the system. : what data structure would you use to implement the cache in the later to : support following operations. : [a] When a request comes look it up in the cache and if it hits then return : the response from here and do not pass the request to the system : [b] If the request is not found in the cache then pass it on to the system : [c] Since cache can only store the last n requests, Insert the n+1
|
l******e 发帖数: 12192 | 3 不用doublelinked。
and
return
request
【在 p********7 的大作中提到】 : [1] Design a layer in front of a system which cache the last n requests and : the responses to them from the system. : what data structure would you use to implement the cache in the later to : support following operations. : [a] When a request comes look it up in the cache and if it hits then return : the response from here and do not pass the request to the system : [b] If the request is not found in the cache then pass it on to the system : [c] Since cache can only store the last n requests, Insert the n+1
|
p********7 发帖数: 549 | 4 恩,就是LRU算法的改进版
【在 h**k 的大作中提到】 : 链表中的元素的顺序是他们进入cache的先后顺序? : 我觉得你的想法是对的。 : : and : return : request
|
x******3 发帖数: 245 | 5 如果把【c]改成
[c] Since cache can only store the last n requests, Insert the n+1th request
in the cache and delete the oldest request from the cache
是不是就没法o(1)了,应该要maintain一个heap like的东西来track oldest request |
A*********r 发帖数: 564 | 6 假如有一个hit, 通过hashtable直接找到了链表的节点,所有的LRU值理论上要被更新
,这个不是O(1)了。。
不知道你的LRU值是什么?
and
return
request
【在 p********7 的大作中提到】 : [1] Design a layer in front of a system which cache the last n requests and : the responses to them from the system. : what data structure would you use to implement the cache in the later to : support following operations. : [a] When a request comes look it up in the cache and if it hits then return : the response from here and do not pass the request to the system : [b] If the request is not found in the cache then pass it on to the system : [c] Since cache can only store the last n requests, Insert the n+1
|
h**k 发帖数: 3368 | 7 把它从链表中删除,再重新插到链表最后就行了。因为是doubly link,操作是O(1)。
【在 A*********r 的大作中提到】 : 假如有一个hit, 通过hashtable直接找到了链表的节点,所有的LRU值理论上要被更新 : ,这个不是O(1)了。。 : 不知道你的LRU值是什么? : : and : return : request
|
A*********r 发帖数: 564 | 8 你指的是插到链表头吧?如果到最后,这个插入的时间也不是O(1)了,除非再maintain
一个tail指针 (不过默认的链表都是只有head指针的吧)。
我看见paul说hashtable除了保存链表指针,还要保存LRU值,常见的LRU值都要求每进
入一个新的页面,重新update所有的其它LRU值(比如清零之类的)。
在这里,不需要额外的LRU值貌似也能实现题目中要求的三种操作,所以我很困惑paul
同学的LRU值是什么。。
【在 h**k 的大作中提到】 : 把它从链表中删除,再重新插到链表最后就行了。因为是doubly link,操作是O(1)。
|
h**k 发帖数: 3368 | 9 他用的是doubly linked list。一般是有一个专门指向tail的指针。
LRU值不是必须的,但是你必须知道request的先后顺序。
maintain
paul
【在 A*********r 的大作中提到】 : 你指的是插到链表头吧?如果到最后,这个插入的时间也不是O(1)了,除非再maintain : 一个tail指针 (不过默认的链表都是只有head指针的吧)。 : 我看见paul说hashtable除了保存链表指针,还要保存LRU值,常见的LRU值都要求每进 : 入一个新的页面,重新update所有的其它LRU值(比如清零之类的)。 : 在这里,不需要额外的LRU值貌似也能实现题目中要求的三种操作,所以我很困惑paul : 同学的LRU值是什么。。
|
t*****j 发帖数: 1105 | 10 我思路和你的一样,还要加个variable,记录该链表中已经存有多少个
请求,server刚开始运行的时候用。
requests
and
to
return
system
request
【在 p********7 的大作中提到】 : [1] Design a layer in front of a system which cache the last n requests and : the responses to them from the system. : what data structure would you use to implement the cache in the later to : support following operations. : [a] When a request comes look it up in the cache and if it hits then return : the response from here and do not pass the request to the system : [b] If the request is not found in the cache then pass it on to the system : [c] Since cache can only store the last n requests, Insert the n+1
|
b*********r 发帖数: 302 | 11 how about hashtable + queue? |