LRU 算法

有时候我们需要在后台长时间运行一些脚本,在这些脚本运行的过程中需要在内存中缓存一些数据。

这就用到了 LRU 算法。

什么是 LRU 算法

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

算法实现

使用一个链表保存缓存数据。

1. 新数据插入到链表头部;

2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;

3. 当链表满的时候,将链表尾部的数据丢弃。

基于 PHP 的数组实现了下面这个类

<?php 
class MemoryCache
{
	protected static $instance;
	private $stores = [];
	private $maxItem = 0;
	public static function getInstance()
    {
        if (is_null(self::$instance)) {
        	$maxItem = 1000;
            static::$instance = new static($maxItem);
        }
        return static::$instance;
    }
    private function __construct($maxItem)
    {
    	$this->maxItem = $maxItem;
    	$this->doClean();
    }
    public function doGet($key)
    {
    	if(isset($this->stores['items'][$key])) {
			$item = $this->stores['items'][$key];
    		if($item['timeout'] >= time()) {
    			$this->moveToStart($key);
    			return $item['value'];
    		}
			$this->doForget($key);
    	}
    	return null;
    }
    public function doClean()
    {
    	$this->stores = [
    		'start' => null,
    		'items' => [],
    		'end' => null
    	];
    	return true;
    }
    public function doPut($key, $val, $minute) 
    {
    	$startKey = $this->stores['start'];
    	$endKey = $this->stores['end'];
    	if(isset($this->stores['items'][$key])) {
    		$this->doForget($key);
    	}
    	$this->stores['items'][$key] = [
    		'value' => $val,
    		'timeout' => time() + ($minute*60),
    		'next' => $startKey,
    		'prev' => null,
    	];
    	$this->setStartKey($key);
    	if(count($this->stores['items']) > $this->maxItem) {
    		$this->doForget($endKey);
    	}
    	return true;
    }
    public function doForget($key)
    {
    	if($key && isset($this->stores['items'][$key])) {
    		$this->removeKey($key);
			unset($this->stores['items'][$key]);
    		return true;
    	}
    	return false;
    }
    private function setStartKey($key)
    {
    	if($key && isset($this->stores['items'][$key])) {
	    	$startKey = $this->stores['start'];
	    	if($startKey) {
	    		$this->stores['items'][$startKey]['prev'] = $key;
	    	} else {
	    		$this->stores['end'] = $key;
	    	}
	    	$this->stores['start'] = $key;
	    	$this->stores['items'][$key]['prev'] = null;
	    	$this->stores['items'][$key]['next'] = $startKey;
	    	return true;
	    }
	    return false;
    }
    private function moveToStart($key)
    {
    	$item = $this->removeKey($key);
    	if($item) {
    		return $this->setStartKey($key);
    	}
    	return false;
    }
    private function removeKey($key)
    {
    	if($key && isset($this->stores['items'][$key])) {
    		$item = $this->stores['items'][$key];
    		$nextKey = $item['next'];
    		$prevKey = $item['prev'];
    		if($prevKey == null) {
    			$this->stores['start'] = $nextKey;
    		} else {
    			$this->stores['items'][$prevKey]['next'] = $nextKey;
    		}
    		if ($nextKey == null) {
    			$this->stores['end'] = $prevKey;
    		} else {
    			$this->stores['items'][$nextKey]['prev'] = $prevKey;
    		}
    		return $item;
    	}
    	return false;
    }
    public static function get($key)
    {
    	return static::getInstance()->doGet($key);
    }
    public static function put($key,$val, $minute)
    {
    	return static::getInstance()->doPut($key,$val,$minute);	
    }
    public static function forget($key)
    {
    	return static::getInstance()->doForget($key);
    }
    public static function cleanAll()
    {
    	return static::getInstance()->doClean();
    }
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注