昨晚和今晚,我尝试了几种不同的方法,并提出了一种与Jeff在下面提出的方法类似的方法(我什至已经完成了他在更新中所建议的方法,并结合了自己的简单LL实现以获得更多 yield )。这是代码,到目前为止,它看起来还不是特别干净,但是我已经经历了无数次修改任何我可以提高性能的事情了。
public class NewLRU2<K, V> where V : class
{
int m_iMaxItems;
Dictionary<K, LRUNode<K, V>> m_oMainDict;
private LRUNode<K,V> m_oHead;
private LRUNode<K,V> m_oTail;
private LRUNode<K,V> m_oCurrent;
public NewLRU2(int iSize)
{
m_iMaxItems = iSize;
m_oMainDict = new Dictionary<K, LRUNode<K,V>>();
m_oHead = null;
m_oTail = null;
}
public V this[K key]
{
get
{
m_oCurrent = m_oMainDict[key];
if (m_oCurrent == m_oHead)
{
//do nothing
}
else if (m_oCurrent == m_oTail)
{
m_oTail = m_oCurrent.Next;
m_oTail.Prev = null;
m_oHead.Next = m_oCurrent;
m_oCurrent.Prev = m_oHead;
m_oCurrent.Next = null;
m_oHead = m_oCurrent;
}
else
{
m_oCurrent.Prev.Next = m_oCurrent.Next;
m_oCurrent.Next.Prev = m_oCurrent.Prev;
m_oHead.Next = m_oCurrent;
m_oCurrent.Prev = m_oHead;
m_oCurrent.Next = null;
m_oHead = m_oCurrent;
}
return m_oCurrent.Value;
}
}
public void Add(K key, V value)
{
if (m_oMainDict.Count >= m_iMaxItems)
{
//remove old
m_oMainDict.Remove(m_oTail.Key);
//reuse old
LRUNode<K, V> oNewNode = m_oTail;
oNewNode.Key = key;
oNewNode.Value = value;
m_oTail = m_oTail.Next;
m_oTail.Prev = null;
//add new
m_oHead.Next = oNewNode;
oNewNode.Prev = m_oHead;
oNewNode.Next = null;
m_oHead = oNewNode;
m_oMainDict.Add(key, oNewNode);
}
else
{
LRUNode<K, V> oNewNode = new LRUNode<K, V>(key, value);
if (m_oHead == null)
{
m_oHead = oNewNode;
m_oTail = oNewNode;
}
else
{
m_oHead.Next = oNewNode;
oNewNode.Prev = m_oHead;
m_oHead = oNewNode;
}
m_oMainDict.Add(key, oNewNode);
}
}
public bool Contains(K key)
{
return m_oMainDict.ContainsKey(key);
}
}
internal class LRUNode<K,V>
{
public LRUNode(K key, V val)
{
Key = key;
Value = val;
}
public K Key;
public V Value;
public LRUNode<K, V> Next;
public LRUNode<K, V> Prev;
}
有一些看起来/感觉很奇怪的部分-就像在执行添加操作时重用旧节点-但我能够从中显着提高性能。对于从节点上的实际属性切换到仅公共(public)变量所产生的差异,我也感到有些惊讶,但是我想这就是它的本质。在这一点上,上面的代码几乎完全受字典操作的性能限制,所以我不确定将它们混在一起会有更多的好处。我将继续考虑并研究一些回应。原始帖子的解释:
大家好。
因此,我编写了一个用于压缩库的简单轻量级LRU实现(我正在使用它来基于LZW样式的哈希在输入中查找匹配的字节字符串),并且我正在寻找方法来制作它更快。
最佳答案
更新#2
这减少了在链接列表“删除”上遍历列表的需要。它引入了一个既具有键又具有值的LruCacheNode。该键仅在修剪缓存时使用。如果编写自己的链表实现,则每个节点本质上都是一个LruCacheNode以及一个Next和Back引用,则可以获得更好的性能。这是LinkedHashMap的功能(请参阅these two问题)。
public class LruCache<K, V>
{
private readonly int m_iMaxItems;
private readonly Dictionary<K, LinkedListNode<LruCacheNode<K, V>>> m_oMainDict;
private readonly LinkedList<LruCacheNode<K, V>> m_oMainList;
public LruCache(int iSize)
{
m_iMaxItems = iSize;
m_oMainDict = new Dictionary<K, LinkedListNode<LruCacheNode<K, V>>>();
m_oMainList = new LinkedList<LruCacheNode<K, V>>();
}
public V this[K key]
{
get
{
return BumpToFront(key).Value;
}
set
{
BumpToFront(key).Value = value;
}
}
public void Add(K key, V value)
{
LinkedListNode<LruCacheNode<K, V>> newNode = m_oMainList.AddFirst(new LruCacheNode<K, V>(key, value));
m_oMainDict.Add(key, newNode);
if (m_oMainList.Count > m_iMaxItems)
{
m_oMainDict.Remove(m_oMainList.Last.Value.Key);
m_oMainList.RemoveLast();
}
}
private LruCacheNode<K, V> BumpToFront(K key)
{
LinkedListNode<LruCacheNode<K, V>> node = m_oMainDict[key];
if (m_oMainList.First != node)
{
m_oMainList.Remove(node);
m_oMainList.AddFirst(node);
}
return node.Value;
}
public bool Contains(K key)
{
return m_oMainDict.ContainsKey(key);
}
}
internal sealed class LruCacheNode<K, V>
{
private readonly K m_Key;
private V m_Value;
public LruCacheNode(K key, V value)
{
m_Key = key;
m_Value = value;
}
public K Key
{
get { return m_Key; }
}
public V Value
{
get { return m_Value; }
set { m_Value = value; }
}
}
您必须概要分析事情,看看这是否对您的环境有所改善。
次要更新:我更新了BumpToFront以检查Tim Stewart的注释是否已将该节点放在最前面。