札记之PHP实现LRU算法

LRU(least recently used, 最近最少使用),LRU算法的设计原则是：

• 当数据在最近一段时间经常被访问，那么它在以后也会经常被访问。这就意味着，如果经常访问的数据，我们需要让其能够快速命中，而不常访问的数据，我们在容量超出限制内，要将其淘汰。

LRU的实现：链表 数组

• 数组：查询比较快，插入，删除的时间复杂度O(n)
• 链表：查询比较慢，但是对于增删来说十分方便，时间复杂度O(n)O(1)
• 链表和HashTable：HashTable主要用于查找数据，保证通过key访问数据的时间复杂度为O(1)，而链表用来保存缓存数据。

算法的实现过程如图所示：

步骤：

• 当访问的数据命中缓存，遍历得到这个数据对应的结点,并将其从原来的位置删除，然后再插入到链表的头部；(修改链表指针O(1))
• 如果此数据没有在缓存链表中,分为两种情况：
• 如果此时缓存未满，则将此结点直接插入到链表的头部；
• 如果此时缓存已满，则遍历至链表尾结点将其删除，将新的数据结点插入链表的头部。

如图所示[attach detach]

PHP代码实现

class ListNode
{
    public $data = NULL;
    public $prev = NULL;
    public $next = NULL;
    public $key = NULL;

    public function __construct($key, $data = NULL)
    {
        $this->key = $key;
        $this->data = $data;
    }
    public function __get($var)
    {
        return $this->$var;
    }
    public function __set($var, $val)
    {
        return $this->$var = $val;
    }
}

class LRUCache
{
    private $head;
    private $tail;
    private $capacity;
    private $hashmap;

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

        $this->hashmap = array();
        $this->head = new ListNode(NULL, NULL);
        $this->tail = new ListNode(NULL, NULL);

        $this->head->next = $this->tail;
        $this->tail->next = $this->head;
    }

    public function get($key) 
    {
        if (!isset($this->hashmap[$key])) {
            return false; 
        }
        $node = $this->hashmap[$key];
        if (count($this->hashmap) == 1) {
            return $node->data; 
        }
        print_r($this->hashmap);
        //调用后，将数据移动到链表头部
        $this->detach($node);
        $this->attach($this->head, $node);
        return $node->data;
    }

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

        if (empty($this->hashmap[$key])) {
            $newNode = new ListNode($key, $data);
            $this->hashmap[$key] = $newNode;
            $this->attach($this->head, $newNode);

            // 如果缓存满了，则删除尾部值
            if (count($this->hashmap) > $this->capacity) {
                $nodeToRemove = $this->tail->prev;
                $this->detach($nodeToRemove);
                unset($this->hashmap[$nodeToRemove->key]);
            }
        } else {
            //缓存命中，则将数据移动到头部
            $newNode = $this->hashmap[$key];
            $this->detach($newNode);
            $this->attach($this->head, $newNode);
            $newNode->data = $data;
        }
        return true;
    }

    public function remove($key) 
    {
        if (empty($this->hashmap[$key])) {
            return false; 
        }
        $nodeToRemove = $this->hashmap[$key];
        $this->detach($nodeToRemove);
        unset($this->hashmap[$nodeToRemove->key]);
        return true;
    }

    private function detach($node) 
    {
        $node->prev->next = $node->next;
        $node->next->prev = $node->prev;
    }

    private function attach($head, $newNode) 
    {
        $newNode->prev = $head;
        $newNode->next = $head->next;
        $newNode->next->prev = $newNode;
        $newNode->prev->next = $newNode;
    }
}
$lru = new LRUCache(4);
$lru->put(1, 1111);
$lru->put(2, 2222);
$lru->put(3, 3333);
$lru->put(3, 3333);
print_r($lru->get(3));

运行结果

Array
	(
		[1] => ListNode Object(
			[data] => 1111[prev] => ListNode Object(
				[data] => 2222[prev] => ListNode Object(
					[data] => 3333[prev] => ListNode Object(
						[data] => [prev] => [next] => ListNode Object *
						RECURSION * [key] =>
					)

					[next] => ListNode Object *
					RECURSION * [key] => 3
				)

				[next] => ListNode Object *
				RECURSION * [key] => 2
			)

			[next] => ListNode Object(
				[data] => [prev] => ListNode Object *
				RECURSION * [next] => ListNode Object(
					[data] => [prev] => [next] => ListNode Object(
						[data] => 3333[prev] => ListNode Object *
						RECURSION * [next] => ListNode Object(
							[data] => 2222[prev] => ListNode Object *
							RECURSION * [next] => ListNode Object *
							RECURSION * [key] => 2
						)

						[key] => 3
					)

					[key] =>
				)

				[key] =>
			)

			[key] => 1
		)

		[2] => ListNode Object(
			[data] => 2222[prev] => ListNode Object(
				[data] => 3333[prev] => ListNode Object(
					[data] => [prev] => [next] => ListNode Object *
					RECURSION * [key] =>
				)

				[next] => ListNode Object *
				RECURSION * [key] => 3
			)

			[next] => ListNode Object(
				[data] => 1111[prev] => ListNode Object *
				RECURSION * [next] => ListNode Object(
					[data] => [prev] => ListNode Object *
					RECURSION * [next] => ListNode Object(
						[data] => [prev] => [next] => ListNode Object(
							[data] => 3333[prev] => ListNode Object *
							RECURSION * [next] => ListNode Object *
							RECURSION * [key] => 3
						)

						[key] =>
					)

					[key] =>
				)

				[key] => 1
			)

			[key] => 2
		)

		[3] => ListNode Object(
			[data] => 3333[prev] => ListNode Object(
				[data] => [prev] => [next] => ListNode Object *
				RECURSION * [key] =>
			)

			[next] => ListNode Object(
				[data] => 2222[prev] => ListNode Object *
				RECURSION * [next] => ListNode Object(
					[data] => 1111[prev] => ListNode Object *
					RECURSION * [next] => ListNode Object(
						[data] => [prev] => ListNode Object *
						RECURSION * [next] => ListNode Object(
							[data] => [prev] => [next] => ListNode Object *
							RECURSION * [key] =>
						)

						[key] =>
					)

					[key] => 1
				)

				[key] => 2
			)

			[key] => 3
		)

	)