6月 05

lru算法, least recently used最近最少使用算法

在做 词语大全的时候,要展示最近访问的数据

本来想写一个双向链表来实现的.但是后来一考虑,我的应用场景中,最多只保留10条数据,而且都是string,那么感觉真没这个必要了

一个List其实就可以搞定了

所以就有了这个简易版本

记录下来,等以后网站发展了再完善了

using System;   
using System.Collections.Generic;   
using System.Linq;   
using System.Text;   
       
namespace blog.wx6.org   
{   
    public class LRUHelper   
    {   
        private int Max = 10;   
        public LRUHelper(int max=10)   
        { this.Max = max; }   
       
        private List<string> Items = new List<string>();   
       
        private object obj = new object();   
       
       
        public void Add(string key) {   
            lock (obj)   
            {   
                Items.Remove(key);   
                Items.Insert(0, key);   
            }   
            if (Items.Count > this.Max)   
            {   
                lock (obj)   
                {   
                    this.Items = this.Items.GetRange(0, this.Max);   
                }   
            }   
        }   
       
        public List<string> GetList()   
        {   
            return this.Items;   
        }   
    }    
}

2013.12.24记录

改进版,可以存储一个泛型数据

加锁防止发,测试了一下

效率也不算太差,目前www.wx6.org 的阶段这么用完全没有问题

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using HeYang.Framework.Helper;
 
namespace HeYang.Framework.Collect
{
    /// <summary>
    /// LRU算法
    /// Author : Ocean
    /// blog.wx6.org
    /// </summary>
    /// <typeparam name="Key"></typeparam>
    /// <typeparam name="Value"></typeparam>
    public class LRUHelper<Key, Value>
    {
 
        private object obj = new object(); 
 
        private int Max = 10;
        public LRUHelper(int max)
        {
            this.Max = max;
        }
 
        private List<Key> keys = new List<Key>();
        private Dictionary<Key, Value> values = new Dictionary<Key, Value>(); 
 
        public void Add(Key key, Value value)
        {
            lock (obj)
            {
                keys.Remove(key);
                keys.Insert(0, key);
 
                values.Remove(key);
                values.Add(key, value);
 
                if (keys.Count > this.Max)
                {
                    Key lastOne = keys[keys.Count - 1];
                    keys.RemoveAt(keys.Count - 1);
                    values.Remove(lastOne);
                }
            }
        } 
        public List<Value> GetList(int top=100)
        {
            lock (obj)
            {
                List<Value> result = new List<Value>();
                for (int index = 0; index < keys.Count && index<top; index++)
                {
                    result.Add(values[keys[index]]);
                } 
                return result;
            }
        }
    }
}

written by ocean