Go語言實現LRU算法

       LRU 通常使用hash map + doubly linked list實現。在Golange中很簡單，使用List保存數據,Map來做快速訪問即可.  具體實現了下面幾個函數:

    func NewLRUCache(cap int)(*LRUCache)  
    func (lru *LRUCache)Set(k,v interface{})(error)  
    func (lru *LRUCache)Get(k interface{})(v interface{},ret bool,err error)  
    func (lru *LRUCache)Remove(k interface{})(bool)  

    package main


//LRU Cache  
//author:Xiong Chuan Liang  
//date:2015-2-3  

import (  
    "fmt"  
    "github.com/xcltapestry/xclpkg/algorithm"    
)  

func main(){  

    lru := algorithm.NewLRUCache(3)  

    lru.Set(10,"value1")  
    lru.Set(20,"value2")  
    lru.Set(30,"value3")  
    lru.Set(10,"value4")  
    lru.Set(50,"value5")  

    fmt.Println("LRU Size:",lru.Size())  
    v,ret,_ := lru.Get(30)  
    if ret  {  
        fmt.Println("Get(30) : ",v)  
    }  

    if lru.Remove(30) {  
        fmt.Println("Remove(30) : true ")  
    }else{  
        fmt.Println("Remove(30) : false ")  
    }  
    fmt.Println("LRU Size:",lru.Size())  
}  </pre><br />

運行結果: 
    LRU Size: 3  
    Get(30) :  value3  
    Remove(30) : true  
    LRU Size: 2  


具體的 實現源碼: 
    package algorithm  


    //LRU Cache  
    //author:Xiong Chuan Liang  
    //date:2015-2-3  
    //"github.com/xcltapestry/xclpkg/algorithm"    

    import (  
        "container/list"  
        "errors"      
    )  


    type CacheNode struct {  
        Key,Value interface{}     
    }  

    func (cnode *CacheNode)NewCacheNode(k,v interface{})*CacheNode{  
        return &CacheNode{k,v}  
    }  

    type LRUCache struct {  
        Capacity int      
        dlist *list.List  
        cacheMap map[interface{}]*list.Element  
    }  

    func NewLRUCache(cap int)(*LRUCache){  
        return &LRUCache{  
                    Capacity:cap,  
                    dlist: list.New(),  
                    cacheMap: make(map[interface{}]*list.Element)}  
    }  

    func (lru *LRUCache)Size()(int){  
        return lru.dlist.Len()  
    }  

    func (lru *LRUCache)Set(k,v interface{})(error){  

        if lru.dlist == nil {  
            return errors.New("LRUCache結構體未初始化.")         
        }  

        if pElement,ok := lru.cacheMap[k]; ok {       
            lru.dlist.MoveToFront(pElement)  
            pElement.Value.(*CacheNode).Value = v  
            return nil  
        }  

        newElement := lru.dlist.PushFront( &CacheNode{k,v} )  
        lru.cacheMap[k] = newElement  

        if lru.dlist.Len() > lru.Capacity {        
            //移掉最后一個  
            lastElement := lru.dlist.Back()  
            if lastElement == nil {  
                return nil  
            }  
            cacheNode := lastElement.Value.(*CacheNode)  
            delete(lru.cacheMap,cacheNode.Key)  
            lru.dlist.Remove(lastElement)  
        }  
        return nil  
    }  


    func (lru *LRUCache)Get(k interface{})(v interface{},ret bool,err error){  

        if lru.cacheMap == nil {  
            return v,false,errors.New("LRUCache結構體未初始化.")         
        }  

        if pElement,ok := lru.cacheMap[k]; ok {       
            lru.dlist.MoveToFront(pElement)       
            return pElement.Value.(*CacheNode).Value,true,nil  
        }  
        return v,false,nil  
    }  


    func (lru *LRUCache)Remove(k interface{})(bool){  

        if lru.cacheMap == nil {  
            return false  
        }  

        if pElement,ok := lru.cacheMap[k]; ok {  
            cacheNode := pElement.Value.(*CacheNode)  
            delete(lru.cacheMap,cacheNode.Key)        
            lru.dlist.Remove(pElement)  
            return true  
        }  
        return false  
    }  


 附注: 
1.key記錄在map

2.對于set/get添加或命中的元素移到鏈表頭

3.如總個數大于Cache容量(cap),則將最末的元素移除. 



MAIL: xcl_168@aliyun.com 
BLOG:http://blog.csdn.net/xcl168