缓存置换算法和双向链表的实现（二）

#! -*- encoding=utf-8 -*-


# FIFO先进先出页面缓存置换算法
# 1、当需要淘汰缓存时，把最先进入列表的字块淘汰
from node.Node import Node,DoubleLinkedList
class FIFO(object):
  def __init__(self,capacity):
    self.capacity = capacity
    self.size = 0
    self.map = {}
    self.list = DoubleLinkedList(self.capacity)


  def get(self,key):
    if key not in self.map:
      return -1
    else:
      return self.map.get(key).value


  def put(self,key,value):
    if self.capacity == 0:
      return
    if key in self.map:
      node = self.map.get(key)
      self.list.remove(node)
      node.value = value
      self.list.append(node)
    else:
      if self.size == self.capacity:
        node = self.list.pop()
        del self.map[node.key]
        self.size -= 1
      node = Node(key,value)
      self.list.append(node)
      self.map[key] = node
      self.size += 1


  def print(self):
    self.list.print()




# 测试逻辑
if __name__ == '__main__':
  cache = FIFO(2)
  cache.put(1,1)
  cache.print()
  cache.put(2,2)
  cache.print()
  print(cache.get(1))
  cache.print()
  cache.put(3,3)
  cache.print()
  print(cache.get(2))
  cache.print()
  cache.put(4,4)
  cache.print()
  print(cache.get(1))
# exit()
# print(__name__)
# print(__name__)

<?php 
require_once 'node/Node.php';




# FIFO先进先出页面缓存置换算法
# 1、当需要淘汰缓存时，把最先进入列表的字块淘汰
class FIFO extends DoubleLinkedList{
  public $capacity;
  public $size = 0;
  public $map = [];
  public $list = [];


  public function __construct($capacity){
    $this->capacity = $capacity;
    $this->list = new DoubleLinkedList($capacity);
  }


  public function get($key){
    if(!array_key_exists($key,$this->map)) return -1;
    return $this->map[$key]->value;
  }
  public function put($key,$value){
    if($this->capacity == 0) return;
    if(array_key_exists($key,$this->map)){
      $node = $this->map[$key];
      $this->list->remove($node);
      $node->value = $value;
      $this->list->append($node);
    }else{
      if($this->size == $this->capacity){
        $node = $this->list->pop();
        unset($this->map[$node->key]);
        $this->size -= 1;  
      }
      $node = new Node($key,$value);
      $this->list->append($node);
      $this->map[$key] = $node;
      $this->size += 1;
    }
  }
  public function console(){
    $this->list->console();
  }
}




//逻辑测试
$cache = new FIFO(2);
$cache->put(1,1);
$cache->console();
$cache->put(2,2);
$cache->console();
print($cache->get(1));
$cache->console();
$cache->put(3,3);
$cache->console();
print($cache->get(2));
$cache->console();
$cache->put(4,4);
$cache->console();
print($cache->get(1));
$cache->console();
print($cache->get(4));
$cache->console();


?>

#! -*- encoding=utf-8 -*-


# LRU最近最少使用页面置换算法
# 剔除最少使用的字块，将最近使用的字块提前到链表头部
from node.Node import Node,DoubleLinkedList


class LRU(object):
  def __init__(self,capacity):
    self.capacity = capacity
    self.map = {}
    self.list = DoubleLinkedList(self.capacity)
    self.size = 0


  def get(self,key):
    if key in self.map:
      node = self.map[key]
      self.list.remove(node)
      self.list.append_front(node)
      return node.value 
    else:
      return -1 


  def put(self,key,value):
    if key in self.map:
      node = self.map.get(key)
      self.list.remove(node)
      node.value = value
      self.list.append_front(node)
      # pass
    else:
      node = Node(key,value)
      if self.size >= self.capacity:
        old_node = self.list.remove()
        self.map.pop(old_node.key)
        self.size -= 1
      self.list.append_front(node)
      self.map[key] = node
      self.size += 1
      # pass
  
  def print(self):
    self.list.print()


# 测试逻辑
if __name__ == '__main__':
  cache = LRU(2)
  cache.put(2,2)
  cache.print()
  cache.put(1,1)
  cache.print()
  cache.put(3,3)
  cache.print()
  print(cache.get(1))
  cache.print()
  print(cache.get(2))
  cache.print()
  print(cache.get(3))
  cache.print()

<?php 
require_once 'node/Node.php';




# LRU最近最少使用页面置换算法
# 剔除最少使用的字块，将最近使用的字块提前到链表头部
class LRU extends DoubleLinkedList{
  public $capacity;
  public $size = 0;
  public $map = [];
  public $list = [];


  public function __construct($capacity){
    $this->capacity = $capacity;
    $this->list = new DoubleLinkedList($this->capacity);
  }


  public function get($key){
    if(!array_key_exists($key,$this->map)) return -1;
    $node = $this->map[$key];
    $this->list->remove($node);
    $this->list->append_front($node);
    return $node->value;
  }


  public function put($key,$value){
    if(array_key_exists($key,$this->map)){
      $node = $this->map[$key];
      $this->list->remove($node);
      $node->value = $value;
      $this->list->append_front($node);
    }else{
      $node = new Node($key,$value);
      if($this->size >= $this->capacity){
        $old_node = $this->list->remove();
        unset($this->map[$old_node->key]);
        $this->size -= 1;
      }


      $this->list->append_front($node);
      $this->map[$key] = $node;
      $this->size += 1;
    }
  }
  public function console(){
    $this->list->console();
  }
}


//逻辑测试
$cache = new LRU(2);
$cache->put(2,2);
$cache->console();
$cache->put(1,1);
$cache->console();
$cache->put(3,3);
$cache->console();
print($cache->get(1));
$cache->console();
print($cache->get(2));
$cache->console();
print($cache->get(3));
$cache->console();