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? |
