gpt4 book ai didi

c# - C# 中的 LFU 缓存?

转载 作者:太空狗 更新时间:2023-10-30 00:13:08 27 4
gpt4 key购买 nike

C# 中是否有现成的 LFU 缓存?

最佳答案

我相信还有其他人。

这是一个基本的 LFU 实现,用于 C# 老化,我刚刚敲了敲它,它并不完美,但它是一个很好的起点:注意:此实现不是线程安全的。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LFU {

class LFUCache<TKey,TValue> {

Dictionary<TKey, LinkedListNode<CacheNode>> cache = new Dictionary<TKey, LinkedListNode<CacheNode>>();
LinkedList<CacheNode> lfuList = new LinkedList<CacheNode>();

class CacheNode {
public TKey Key { get; set; }
public TValue Data { get; set; }
public int UseCount { get; set; }
}

int size;
int age = 0;
int agePolicy;

public LFUCache(int size) : this(size, 1000) {
}


/// <summary>
///
/// </summary>
/// <param name="size"></param>
/// <param name="agePolicy">after this number of gets the cache will take 1 off all UseCounts, forcing old stuff to expire.</param>
public LFUCache(int size, int agePolicy) {
this.agePolicy = 1000;
this.size = size;
}

public void Add(TKey key, TValue val) {
TValue existing;
if (!TryGet(key, out existing)) {
var node = new CacheNode() {Key = key, Data = val, UseCount = 1};
if (lfuList.Count == size) {
cache.Remove(lfuList.First.Value.Key);
lfuList.RemoveFirst();
}

var insertionPoint = Nodes.LastOrDefault(n => n.Value.UseCount < 2);

LinkedListNode<CacheNode> inserted;

if (insertionPoint == null) {
inserted = lfuList.AddFirst(node);
} else {
inserted = lfuList.AddAfter(insertionPoint, node);
}
cache[key] = inserted;
}
}

IEnumerable<LinkedListNode<CacheNode>> Nodes {
get {
var node = lfuList.First;
while (node != null) {
yield return node;
node = node.Next;
}
}
}

IEnumerable<LinkedListNode<CacheNode>> IterateFrom(LinkedListNode<CacheNode> node) {
while (node != null) {
yield return node;
node = node.Next;
}
}

public TValue GetOrDefault(TKey key) {
TValue val;
TryGet(key, out val);
return val;
}

public bool TryGet(TKey key, out TValue val) {

age++;
if (age > agePolicy) {
age = 0;
foreach (var node in cache.Values) {
var v = node.Value;
v.UseCount--;
}
}

LinkedListNode<CacheNode> data;
bool success = false;

if (cache.TryGetValue(key, out data)) {
var cacheNode = data.Value;
val = cacheNode.Data;
cacheNode.UseCount++;

var insertionPoint = IterateFrom(data).Last(n => n.Value.UseCount <= cacheNode.UseCount);

if (insertionPoint != data) {
lfuList.Remove(data);
lfuList.AddAfter(insertionPoint, data);
}

} else {
val = default(TValue);
}

return success;
}
}

class Program {


public static void Assert(bool condition, string message) {
if (!condition) {
Console.WriteLine("Assert failed : " + message);
throw new ApplicationException("Test Failed");
}
}

public static void RunAllTests(Program prog){
foreach (var method in prog.GetType().GetMethods()) {
if (method.Name.StartsWith("Test")) {
try {
method.Invoke(prog, null);
Console.WriteLine("Test Passed: " + method.Name);
} catch (Exception) {
Console.WriteLine("Test Failed : " + method.Name);
}

}
}
}

public void TestItemShouldBeThereOnceInserted() {
var cache = new LFUCache<string, int>(3);

cache.Add("a", 1);
cache.Add("b", 2);
cache.Add("c", 3);
cache.Add("d", 4);

Assert(cache.GetOrDefault("a") == 0, "should get 0");
Assert(cache.GetOrDefault("b") == 2, "should get 2");
Assert(cache.GetOrDefault("c") == 3, "should get 3");
Assert(cache.GetOrDefault("d") == 4, "should get 4");
}

public void TestLFUShouldWorkAsExpected() {

var cache = new LFUCache<string, int>(3);

cache.Add("a", 1);
cache.Add("b", 2);
cache.Add("c", 3);

cache.GetOrDefault("a");
cache.GetOrDefault("a");
cache.GetOrDefault("b");

cache.Add("d", 4);
cache.Add("e", 5);


Assert(cache.GetOrDefault("a") == 1, "should get 1");
Assert(cache.GetOrDefault("b") == 2, "should get 0");
Assert(cache.GetOrDefault("c") == 0, "should get 0");
Assert(cache.GetOrDefault("d") == 0, "should get 4");
Assert(cache.GetOrDefault("e") == 5, "should get 5");

}


static void Main(string[] args) {
RunAllTests(new Program());
Console.ReadKey();
}


}
}

关于c# - C# 中的 LFU 缓存?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/953212/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com