w*********t
发帖数: 170 | 1 class LRU{
private final static int MAX_SIZE= 3;
private Map map;
public LRU(){
map = new LinkedHashMap(MAX_SIZE,0.75F,true){
public boolean removeEldestEntry(Map.Entry eldest){
return map.size() > MAX_SIZE;
}
};
}
public void add(K k,V v){
map.put(k,v);
}
public V get(K k){
return map.get(k);
}
public void printLRU(){
for(V v:map.values()){
... 阅读全帖 |
|
k***t
发帖数: 276 | 2 参照网上的思路写了一个。哪位大拿给Review一下。谢了。
我平时只写C，不用C++。所以可能有初级错误：）
#include
#include // HashMap
#include
using namespace std;
// cache entry
struct Entry {
int v; // dummy structure
};
class LRU {
private:
list > mlist;
unordered_map >::iterator> mht;
int cnt;
const static int MAX_SIZE = 10000;
public:
LRU () {cnt=0;}
~LRU () {}
void addEntry (string mURL, Entry mEntry) {
mlist.push_fron... 阅读全帖
|
|
w****o
发帖数: 2260 | 3 如果用C++,到底实现 LRU 应该用什么 data structures?
谢谢！
还有在这个版看到 LRU, LRU Cache,他们是一回事，还是不同的东西？
LRU的应用context是memory access,还是硬盘访问的时候用的？
我的问题很弱，别见笑了。
谢谢！ |
|
r********7
发帖数: 102 | 4 之前面试 遇到过LRU 这道题，面试之前准备过，就直接说了 用hashmap 和
linkedlist。 但是实现起来发现很不好处理 删除命令。 由于是最后一题时间有限就
没在写下去。不过最后一再追问下，知道使用Doublelinkedlist。。。
不过感谢国人面试官，还是给过了。 再次鸣谢下。
然后看到leetcode有这道题（稍微有点不一样）就又做了下，还是问题重重，不得不感
叹自己实力的差距, 不过最后还是通过了，代码如下：
1.由于是菜鸟，代码很丑很啰嗦，希望大神们指点要怎么改进。
2.小弟有一事不明，为啥LRU 还要有（key,value）查询？ 现实中，不就只有一个
value吗？然后HashMap 存。 现实中的LRU 每个内存有key
这个值吗？
希望帮忙讲解下LRU。
public class LRUCache {
public HashMap table = new
HashMap阅读全帖 |
|
c****p
发帖数: 6474 | 5 一个set里的所有entry都设一个计数器，
每次访问这个set的时候，hit的那个entry的计数器清零，同set内的其他entry计数器加
1。
如果set内的访问miss，把计数器值最大的entry换出去。换入的entry计数器为零。
还有个psudo-LRU，硬件代价比LRU小得多，性能比LRU稍差一点儿。。ms现在不少都用的
psudo-LRU。 |
|
l*****g
发帖数: 685 | 6 最近Amazon面试好像喜欢问LRU (least recently used cache)的设计
我用doubly-linked list 和 hashtable 实现了一个简单的LRU, 抛砖引玉，供大家做
参考。祝大家都顺利拿到offer.
using System;
using System.Collections.Generic;
namespace LRU
{
public class Cache
{
public class Container
{
public Object obj;
public Container next;
public Container prev;
public Container(object o)
{
this.obj = o;
}
}
private const int MaxSize ... 阅读全帖 |
|
c****p
发帖数: 6474 | 7 数据结构前面说了，hashtable+list，C++的STL容器不太熟，见谅。。。
只要有类似于缓存的机制都会涉及到replacement算法，LRU是性能最接近理想性能的一
种。
cache line和page的replacement都会用到LRU，所以你说的那两个context都可以。
当然实际硬件实现上好像用的不是LRU，而是pLRU。【 在 winhao (勇敢的人) 的大作
中提到: 】 |
|
b**********5
发帖数: 7881 | 8 我觉得LRu是应该leetcode medium或者easy的难度。。。 现在的新题， 要比LRU难多
了。。 LRU是老题了。。
就像我10多年前， 面试， 人家问我how to check if there's a cycle in
linkedlist。。。
10多年前， 比较难。。。 现在这种根本就不是题目了。。 |
|
S*A
发帖数: 7142 | 9
everybody
但是你说的那个 Cache LRU 基本上没有被其他的 kernel 服务
用。仅仅是某个驱动自己带进来的。kernel 的 用到 cache 的模块
和代码很多。
你要是感兴趣，那个 struct page 的定义在这里，那个 double link list
的 lru 变量在 96行。
http://lxr.free-electrons.com/source/include/linux/mm_types.h?v
不知道你想问的是那个 table。 kernel MMU 有很多类似 table 的东西。
但是估计不是你想要的那种 lookup table。就我知道 MMU 里和 paging
LRU 绑一起的没有。要是你知道有欢迎指出来。 |
|
g*****n
发帖数: 31 | 10 LRU cache的insert都在头部。。。
按照LRU的常规做法，getObj之后要移到list的头上吧。。。 |
|
g*****n
发帖数: 31 | 11 LRU cache,如果已经满了 要insert一个新的 就要把lru(tail)那个干掉。。。
不是double link的话 就不知道下次哪个是tail了。。。
2 |
|
r*******k
发帖数: 1423 | 12 LRU用doubly linked list实现
而这个需要在读的时候锁定这个list
那怎么能做到高并发呢？
我知道memcached对不同大小的map都有各自的slab
有自己的LRU
但仅仅这样就足够了吗？ |
|
h*****n
发帖数: 209 | 13 【 以下文字转载自 Programming 讨论区 】
发信人: hanuman (天竺神猴), 信区: Programming
标 题: 为什么Cache LRU多用doubly linked list而不是single linked list来实现呢?
发信站: BBS 未名空间站 (Thu Oct 23 16:56:37 2014, 美东)
在Cache LRU实现的时候，为什么都是用doubly linked list而不是single linked
list呢？
请大牛赐教。 |
|
h*****n
发帖数: 209 | 14 【 以下文字转载自 Programming 讨论区 】
发信人: hanuman (天竺神猴), 信区: Programming
标 题: 为什么Cache LRU多用doubly linked list而不是single linked list来实现呢?
发信站: BBS 未名空间站 (Thu Oct 23 16:56:37 2014, 美东)
在Cache LRU实现的时候，为什么都是用doubly linked list而不是single linked
list呢？
请大牛赐教。 |
|
S*A
发帖数: 7142 | 15 用数组实现 LRU 有效率问题。
LRU 经常做的一件事是 update 里面的一个 entry。
如果entry 在 list 里面，拿出来，然后放到最前面。
用数组实现的话，添加在头容易，在头指针添加就可以了。
但是如果拿出来的话，原来的位置就会留下一个空洞。
空洞如果不清理，你的数组就会不断长大。如果每次清理，
就要把这个空洞填上，数组前面的元素后移动来填。
这个操作就比较昂贵，因为要移动最坏情况 N 个元素。 |
|
g*****g
发帖数: 34805 | 16 我说的是 LRU, LRU O1的访问时间是必须的。 |
|
S*A
发帖数: 7142 | 17 哦，明白。我还以为你还在说那个 circular buffer.
kernel 里面的比较大的 LRU 就是 active page 的 LRU。
拿个就是 double link list。没有另外的 hash table。
当然 kernel 也不需要访问第几个 item 这样的操作。 |
|
S*A
发帖数: 7142 | 18 你说的这个是另外的实现，kernel paging 没有用这个 lc_cache.
这个 lc_cache 找了一下 reference 大概就是 block driver 里面
某个驱动用了，比较明显的用户只有这一个。和我说的 MMU paging
的 LRU 不是一个东西。这个 LC 看上每个 entry 占内存挺多的。
应该不会用在 page 上面。
LRU 本身并不需要 hashmap。那个是 cache lookup 的时候用的。
这两个是相对独立的东西。说得不对欢迎指正啊。 |
|
f*****w
发帖数: 2602 | 19 LRU 按理该是怎么操作的？ 我看你的代码每次删掉 20％的数据 这样对么？ 按我
的理解 应该每次只有一个被踢出去才对 |
|
f**********t
发帖数: 1001 | 20 哇，这贴为啥会没回复？
同问。。。并且有没有好的LRU cache的code? 搜到很多但不知好不好 |
|
f**********t
发帖数: 1001 | 21 memcache的方法如何实现LRU呢？非分布式可以用double linkedlist + hashtable，但
现在分布在不同server上，能也用一个double linkedlist么？如果不能的话，如何找
到Least recently used？ |
|
j**y
发帖数: 462 | 22 An LRU (least recently used)
May I use LinkedHashMap for the question or I have to define my own data
structure ?
Thanks |
|
g**e
发帖数: 6127 | 23 you can use LinkedHashMap but you need to understand why it can work as LRU
cache |
|
j**y
发帖数: 462 | 24 Thanks, seems LinkedHashMap maintain a double linked list and delete/put
the latest access item to the head
LRU |
|
|
Y**B
发帖数: 144 | 26 How to use Double Linked List and Hashmap to implement a LRU cache? |
|
|
|
|
c********t
发帖数: 5706 | 30 啥是LRU? 为啥要用doubly linked list，而不用arraylist? |
|
|
e******i
发帖数: 106 | 32
我偷懒了，只是给了个general 的例子，具体关于LRU的解释可以看WIkihttp://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used
是种Cache的algorithm吧 |
|
w*******i
发帖数: 186 | 33 楼主早上发过问这道题的贴，没想到这会儿有发了后续问题了。钻研精神先赞一个！
按照rookiecode的结论，看来Iterator（包括ListIterator）这种用来指向对象逻辑地
址的类貌似不管用啊。可是Java偏偏又是屏蔽物理地址的。哎，要怪就怪Java没有提供
C++的list中类似splice的方法吧。。。
话说回来，要是非要展现自己对library的熟练程度，楼主可以考虑使用LinkedHashMap
，这个类专门用于实现LRU的思想。 |
|
|
w********p
发帖数: 948 | 35 lz概念混乱。
浏览器 和 LRU 没有关系。 |
|
D**C
发帖数: 6754 | 36 也没说是fifo阿
LRU在java的implementation就是linkedhashmap,跟fifo没啥关系 |
|
w********p
发帖数: 948 | 37 建议您google下 LRU, browser, fifo 和 stack |
|
a**********0
发帖数: 422 | 38 网上有人用你说的数据结构做LRU 我没仔细看 类似的代码一大堆
我估计我的代码一点错误也没有 只是超时而已 |
|
|
g***s
发帖数: 3811 | 40 java has LinkedHashMap, which supports LRU. |
|
|
d*****5
发帖数: 1920 | 42 昨天面试被问了LRU cache和Word ladder II。。。。 |
|
g********n
发帖数: 447 | 43 就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
该怎么做。
有没有其他类似的题，可以练习？ |
|
m******x
发帖数: 58 | 44 需要对ds比较熟悉。我觉得lru是无准备情况下最能考察ds熟悉程度的题目。
准备方法是详细了解每种ds的big o和实现细节。 |
|
g******i
发帖数: 16 | 45 说实话你静下心来读几个开源系统的代码就都会了。
举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。 |
|
g********n
发帖数: 447 | 46 就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
该怎么做。
有没有其他类似的题，可以练习？ |
|
m******x
发帖数: 58 | 47 需要对ds比较熟悉。我觉得lru是无准备情况下最能考察ds熟悉程度的题目。
准备方法是详细了解每种ds的big o和实现细节。 |
|
g******i
发帖数: 16 | 48 说实话你静下心来读几个开源系统的代码就都会了。
举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。 |
|
z******g
发帖数: 271 | 49 可以，没什么不对的
但注意lru不能用rw lock |
|
H******7
发帖数: 1728 | 50 实现lru用LinkedHashMap好么？
大家一般怎么弄？ |
|
