l*****g
发帖数: 685 | 1 最近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 = 100;
private Container start;
private Container end;
private Dictionary lookupTable;
public Cache()
{
lookupTable = new Dictionary();
}
public void PutObj(object obj)
{
Container newNode;
if (lookupTable.TryGetValue(obj, out newNode))
{
// object already exists in cache. no need to cache it again.
return;
}
newNode = new Container(obj);
if (lookupTable.Count == MaxSize)
{
// Purge 20% of the cache
for (int i = 0; i < MaxSize / 5; i++)
{
lookupTable.Remove(start.obj);
start = start.next;
start.prev = default(Container);
}
GC.Collect();
}
if (lookupTable.Count < 1)
{
end = start = newNode;
}
else
{
end.next = newNode;
newNode.prev = end;
end = end.next;
}
lookupTable.Add(obj, newNode);
}
public Container GetObj(Object obj)
{
Container tmpNode;
if (!lookupTable.TryGetValue(obj, out tmpNode))
{
// If the object doesn't exist in cache
return default(Container);
}
// if the object is at the end of cache list, no need to shift its position.
if (tmpNode != end)
{
if (tmpNode == start)
{
start = start.next;
start.prev = default(Container);
}
else
{
tmpNode.prev.next = tmpNode.next;
tmpNode.next.prev = tmpNode.prev;
}
tmpNode.prev = end;
end.next = tmpNode;
end = end.next;
end.next = default(Container);
}
return tmpNode;
}
}
} |
E***n
发帖数: 166 | 2 用minheap + hastable行吗？
这样可以在log n时间里找到时间最久的，然后删除
【在 l*****g 的大作中提到】
: 最近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
|
l*****g
发帖数: 685 | 3 用doubly linked list + hashtable, 找时间最久的object和任意一个object, 时间都
是O(1)
用min-heap当然也可以，不过你得给每个object加额外的timestamp，需要对timestamp
做很多比较操作
另外，因为min-heap里的element的index一直在变动，而hashtable却需要存比较固定
的index(或reference)来search, 所以这个min-heap不适合用常用的array来implement
；而只能用tree来implement；那样，跟doubly linked list相比就更没有优势，因为
min-heap的tree node需要保存
3个指针(left, right, parent).
综合起来，还是doubly linked list简单的多
【在 E***n 的大作中提到】
: 用minheap + hastable行吗？
: 这样可以在log n时间里找到时间最久的，然后删除
|
a******7
发帖数: 106 | 4 why double linked list. Will single list work? |
r*******e
发帖数: 7583 | 5 single list can not delete element in O(1) given a pointer to the element
【在 a******7 的大作中提到】
: why double linked list. Will single list work?
|
C***y
发帖数: 2546 | 6 单链表不好删除，需要知道前一个node的地址
如果不考虑效率，可以先把要删除的节点拷贝出来，然后把后一个节点拷贝到要删除的
节点，再删除后一个节点，比较麻烦
【在 a******7 的大作中提到】
: why double linked list. Will single list work?
|
a******7
发帖数: 106 | 7 I see. Single list can be delete in O(1) except the last node. Thank you,
guys. |
E***n
发帖数: 166 | 8 但是使用doubly linked list每插入一个元素，需要O(n）时间，
而minheap,插入新的元素只需要O(log n)时间（reheap）
timestamp
implement
【在 l*****g 的大作中提到】
: 用doubly linked list + hashtable, 找时间最久的object和任意一个object, 时间都
: 是O(1)
: 用min-heap当然也可以，不过你得给每个object加额外的timestamp，需要对timestamp
: 做很多比较操作
: 另外，因为min-heap里的element的index一直在变动，而hashtable却需要存比较固定
: 的index(或reference)来search, 所以这个min-heap不适合用常用的array来implement
: ；而只能用tree来implement；那样，跟doubly linked list相比就更没有优势，因为
: min-heap的tree node需要保存
: 3个指针(left, right, parent).
: 综合起来，还是doubly linked list简单的多
|
g*****n
发帖数: 31 | 9 LRU cache的insert都在头部。。。
按照LRU的常规做法，getObj之后要移到list的头上吧。。。 |
s*i
发帖数: 388 | 10 用single linkedlist也可以阿，就是datastrcture 不那么decent，你保存每次维护2
个pointer, prev, current,不就可以了？还省空间 |
|
|
g*****n
发帖数: 31 | 11 LRU cache,如果已经满了 要insert一个新的 就要把lru(tail)那个干掉。。。
不是double link的话 就不知道下次哪个是tail了。。。
2
【在 s*i 的大作中提到】
: 用single linkedlist也可以阿，就是datastrcture 不那么decent，你保存每次维护2
: 个pointer, prev, current,不就可以了？还省空间
|
l*****g
发帖数: 685 | 12 在这个特殊case里，插入元素总是发生在最后，所以你保存一个end指针就可以了，插
入就是O(1)时间
【在 E***n 的大作中提到】
: 但是使用doubly linked list每插入一个元素，需要O(n）时间，
: 而minheap,插入新的元素只需要O(log n)时间（reheap）
:
: timestamp
: implement
|
f*****w
发帖数: 2602 | 13 LRU 按理该是怎么操作的？ 我看你的代码每次删掉 20％的数据 这样对么？ 按我
的理解 应该每次只有一个被踢出去才对 |
s*i
发帖数: 388 | 14 thanks. ic .
【在 g*****n 的大作中提到】
: LRU cache,如果已经满了 要insert一个新的 就要把lru(tail)那个干掉。。。
: 不是double link的话 就不知道下次哪个是tail了。。。
:
: 2
|
P********l
发帖数: 452 | |
l*****g
发帖数: 685 | 16 这个属于设计细节，我觉得无关对错
等cache满了之后，如果你选择每加一个踢出去一个，当然可以，但那样cache就会始终
处于满负荷的状态。所以不妨等满了之后，清掉一定比例的obsolete data.
【在 f*****w 的大作中提到】
: LRU 按理该是怎么操作的？ 我看你的代码每次删掉 20％的数据 这样对么？ 按我
: 的理解 应该每次只有一个被踢出去才对
|
