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

class Node
{
    private $key;

    private $val;

    private $previous;

    private $next;

    public function __construct($key, $val)
    {
        $this->key = $key;
        $this->val = $val;
    }

    public function setVal($val)
    {
        $this->val = $val;
    }

    public function getKey()
    {
        return $this->key;
    }

    public function getVal()
    {
        return $this->val;
    }

    public function setPrevious($previous)
    {
        $this->previous = $previous;
    }

    public function getPrevious()
    {
        return $this->previous;
    }

    public function setNext($next)
    {
        $this->next = $next;
    }

    public function getNext()
    {
        return $this->next;
    }

}
class LRU
{
    private $hashmap = array();

    private $head;

    private $tail;

    private $cacheNum = 0;

    public function __construct($cacheNum)
    {
        $this->cacheNum = $cacheNum;

        $this->hashmap = array();

        $this->head = new Node(null, null);

        $this->tail = new Node(null, null);

        $this->head->setNext($this->tail);

        $this->tail->setPrevious($this->head);

    }

    public function get($key)
    {
        if (!isset($this->hashmap[$key])) {
            return null;
        }

        $node = $this->hashmap[$key];

        if (count($this->hashmap) == 1) {
            return $node->getVal();
        }

        //处理链表

        return $node->getVal();
    }

    public function put($key, $val)
    {
        if ($this->cacheNum <= 0) {
            return false;
        }

        if (isset($this->hashmap[$key]) && !empty($this->hashmap[$key])) {
            //更新数据
            $node = $this->hashmap[$key];

            $this->detach($node);

            $this->attach($this->head, $node);

            $node->setVal($val);
        } else {
            $node                = new Node($key, $val);
            $this->hashmap[$key] = $node;

            //处理数据
            $this->attach($this->head, $node);

            if (count($this->hashmap) > $this->cacheNum) {
                $nodeRemove = $this->tail->getPrevious();
                $this->detach($nodeRemove);

                unset($this->hashmap[$nodeRemove->getKey()]);
            }
        }
        return true;
    }

    private function attach($head, $node)
    {
        $node->setPrevious($head);
        $node->setNext($head->getNext());
        $node->getNext()->setPrevious($node);
        $node->getPrevious()->setNext($node);
    }

    private function detach($node)
    {
        $node->getPrevious()->setNext($node->getNext());
        $node->getNext()->setPrevious($node->getPrevious());
    }
}
error_reporting(0);
echo '开始内存:'.round(memory_get_usage()/1024/1024, 2)."\n";  

$numEntries = 100000;
$lru        = new LRU($numEntries);

while ($numEntries > 0) {
    $lru->put($numEntries - 99999, 'some value...' . $numEntries);
    $numEntries--;
}

echo '运行后内存:'.round(memory_get_usage()/1024/1024, 2)."\n";

results matching ""

    No results matching ""

    results matching ""

      No results matching ""