PHP实现LRU算法的示例代码

本篇文章主要给大家介绍了PHP的相关知识,LRU是Least Recently Used 近期最少使用算法, 内存管理的一种页面置换算法,下面将详解LRU算法的原理以及实现,下面一起来看一下,希望对大家有帮助。

本篇文章主要给大家介绍了PHP的相关知识,LRU是Least Recently Used 近期最少使用算法, 内存管理的一种页面置换算法,下面将详解LRU算法的原理以及实现,下面一起来看一下,希望对大家有帮助。

PHP实现LRU算法的示例代码

原理

LRU是Least Recently Used 近期最少使用算法。 内存管理的一种页面置换算法,对于在内存中但又不用的数据块(内存块)叫做LRU,操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。

什么是LRU算法?LRU是Least Recently Used的缩写,即最近最久未使用,常用于页面置换算法,是为虚拟页式存储管理服务的。

关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是研究的重要方向。而内存的虚拟存储管理,是现在最通用,最成功的方式—— 在内存有限的情况下,扩展一部分外存作为虚拟内存,真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能,极大地提高了计算机的并发度。

虚拟页式存储管理,则是将进程所需空间划分为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理方式。

然而,有利就有弊,虚拟页式存储管理减少了进程所需的内存空间,却也带来了运行时间变长这一缺点:进程运行过程中,不可避免地要把在外存中存放的一些信息和内存中已有的进行交换,由于外存的低速,这一步骤所花费的时间不可忽略。

因而,采取尽量好的算法以减少读取外存的次数,也是相当有意义的事情。

基本原理

假设 序列为 4 3 4 2 3 1 4 2物理块有3个 则首轮 4调入内存 4次轮 3调入内存 3 4之后 4调入内存 4 3之后 2调入内存 2 4 3之后 3调入内存 3 2 4之后 1调入内存 1 3 2(因为最少使用的是4,所以丢弃4)之后 4调入内存 4 1 3(原理同上)最后 2调入内存 2 4 1

规律就是,如果新存入或者访问一个值,则将这个值放在队列开头。如果存储容量超过上限cap,那么删除队尾元素,再存入新的值。

整体设计

用数组保存缓存对象(Node);

缓存对象(Node)之间通过nextKey,preKey组成一个双向链表;

保存链表头 跟尾;

处理流程

PHP实现LRU算法的示例代码

主要代码

Node 节点类

/**
* 缓存值保存类,
* Class Node
* @package app\common\model
*/
class Node{
private $preKey=null;//链表前一个节点
private $nextKey=null;//链表后一个节点
private $value=null;//当前的值
private $key=null;//当前key

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

public function setPreKey($preValue){
$this->preKey=$preValue;
}
public function setNextKey($nextValue){
$this->nextKey=$nextValue;
}

public function getPreKey(){
return $this->preKey;
}

public function getNextKey(){
return $this->nextKey;
}

public function getValue(){
return $this->value;
}

public function setValue($value){
$this->value=$value;
}

public function setKey(string $key){
$this->key=$key;
}

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

缓存类

/**
* 实现lru缓存
* Class LruCache
* @package app\common\model
*/
class LruCache
{
public $cacheTable =[];
private $headNode=null;
private $lastNode=null;
private $cacheCount=0;
private $cacheMax=100;

/**
* 测试输出使用
*/
public function dumpAllData(){
if (!empty($this->headNode)){
$node=$this->headNode;
while (!empty($node)){
echo ;key=;.$node->getKey().; nextKey=;.(empty($node->getNextKey())?;null;:$node->getNextKey()->getKey()).; preKey=;.(empty($node->getPreKey())?;null;:$node->getPreKey()->getKey()).; value=;.$node->getValue().;</br>;;
$node=$node->getNextKey();
}
}
}

/**
* @param int $count
*/
public function setCacheMax(int $count){
$this->cacheMax=$count;
}

/**
* @param string $key
* @param $value
* @return bool
*/
public function set(string $key,$value){

//设置值为null,则认为删除缓存节点
if ($value===null){
$this->del($key);
return true;
}

//判断是否存在表中,存在则更新连表
if (!empty($this->cacheTable[$key])){
$this->updateList($key);
return true;
}

//先判断是否要删除
$this->shiftNode();
$this->addNode($key,$value);
return true;

}

/**
* @param string $key
* @return bool
*/
public function del(string $key){
if (!empty($this->cacheTable[$key])){
$node=&$this->cacheTable[$key];

//摘出节点
$this->jumpNode($node);
//置空删除
$node->setPreKey(null);
$node->setNextKey(null);
unset($this->cacheTable[$key]);
return true;
}

return false;
}

/**
* @param string $key
* @return null
*/
public function get(string $key){
if (!empty($this->cacheTable[$key])){
$this->updateList($key);
return $this->cacheTable[$key]->getValue();
}

return null;
}

//直接添加节点
private function addNode($key,$value){
$addNode=new Node($key,$value);
if (!empty($this->headNode)){
$this->headNode->setPreKey($addNode);
}
$addNode->setNextKey($this->headNode);

//第一次保存最后一个节点为头节点
if ($this->lastNode==null){
$this->lastNode=$addNode;
}
$this->headNode=$addNode;
$this->cacheTable[$key]=$addNode;
$this->cacheCount++;
}

//主动删超出的缓存
private function shiftNode(){
while ($this->cacheCount>=$this->cacheMax){
if (!empty($this->lastNode)){
if (!empty($this->lastNode->getPreKey())){
$this->lastNode->getPreKey()->setNextKey(null);
}
$lastKey=$this->lastNode->getKey();
unset($this->cacheTable[$lastKey]);
}
$this->cacheCount–;
}

}

//更新节点链表
private function updateList($key){
//这里需要使用引用传值
$node=&$this->cacheTable[$key];

//当前结点为头结点 直接不用处理
if ($this->headNode===$node){
return true;
}

//摘出结点
$this->jumpNode($node);
//跟头结点交换
$node->setNextKey($this->headNode);
$this->headNode->setPreKey($node);
$node->setPreKey(null);
$this->headNode=$node;

return true;

}

//将某个节点摘出来
private function jumpNode(Node &$node){
if (!empty($node->getPreKey())){
$node->getPreKey()->setNextKey($node->getNextKey());
}

if (!empty($node->getNextKey())){
$node->getNextKey()->setPreKey($node->getPreKey());
}

//如果是最后一个节点,则更新最后节点为它的前节点
if ($node->getNextKey()==null){
$this->lastNode=$node->getPreKey();
}

//如果是头结点
if ($node->getPreKey()==null){
$this->headNode=$node->getNextKey();
}
}

}

测试代码

public function tt(){
$cath=model(;LruCache;);
$cath->setCacheMax(3);
$cath->set(;aa;,;aaaaaaaaaaa;);
$cath->set(;bb;,;bbbbbbbbbbbb;);
$cath->set(;cc;,;ccccccccccccc;);
$cath->get(;aa;);

// $cath->dumpAllData();
$cath->set(;dd;,;ddddddddddddd;);
// $cath->del(;cc;);
// var_dump($cath->cacheTable);
$cath->dumpAllData();
exit();

}

其实php的数组就是有序的,也可以直接用php数组实现,这里只是提供一个实现的思路,仅供参考

(推荐教程:PHP视频教程)

php正则能匹配数组。在php中,可以利用preg_grep()函数来使用正则表达式匹配数组中的元素;该函数可以搜索数组中的每一个元素,并返回与正则表达式匹配的所有元素所组成的数组,语法“preg_grep(正则表达式,数组,$flags)”;参数“$flags”是可选的,当值设置为“PREG_GREP_INVERT”,则会返回数组中与与正则表达式不匹配的元素组成的数组。

PHP实现LRU算法的示例代码

本教程操作环境:windows7系统、PHP8.1版、DELL G3电脑

php正则能匹配数组。

在php中,说到正则匹配就想到字符串。其实使用正则表达式除了可以匹配字符串外,还可以匹配数组。

在php中,可以利用preg_grep()函数来使用正则表达式匹配数组中的元素。

preg_grep() 函数可以搜索数组中的所有元素,并返回与正则表达式匹配的所有元素所组成的数组。该函数的语法格式如下:

preg_grep($pattern, $input [, $flags = 0 ])

参数说明如下:

  • $pattern:要搜索的模式,也就是定义好的正则表达式;
  • $input:要搜索的数组;
  • $flags:可选参数,可以设置为 PREG_GREP_INVERT,这时函数会返回数组中与给定模式 $pattern 不匹配的元素组成的数组。

perg_grep() 函数将遍历 $input 数组中的每一个元素,让该元素与模式 $pattern 进行匹配,然后将匹配成功或者匹配失败的元素返回。

示例1:返回数组中指定匹配的元素

<?php
header('content-type:text/html;charset=utf-8');
$array = array(1, 2, 3.4, 53, 7.9);
echo "原数组:";
var_dump($array);

// 返回所有包含浮点数的元素
$fl_array = preg_grep("/^(\d+)?\.\d+$/", $array);
echo "返回所有包含浮点数的元素:";
var_dump($fl_array);
?>

PHP实现LRU算法的示例代码

示例2:

<?php
header('content-type:text/html;charset=utf-8');
$test_arr = array(
'PHP中文网',
'http://www.php.cn/',
'php教程',
'abcdefg'
);
$preg = '/^[a-z]/';
$preg_arr_1 = preg_grep($preg, $test_arr);
$preg_arr_2 = preg_grep($preg, $test_arr, PREG_GREP_INVERT);
echo '<pre>';
var_dump($preg_arr_1);
var_dump($preg_arr_2);
?>

PHP实现LRU算法的示例代码

以上就是php正则能不能匹配数组的详细内容,更多请关注钦钦技术栈其它相关文章!

转载至:php中文网【www.php.cn】

版权声明:本文(即:原文链接:https://www.qin1qin.com/catagory/22940/)内容由互联网用户自发投稿贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 630367839@qq.com 举报,一经查实,本站将立刻删除。

(0)
上一篇 2022年9月18日 下午2:42
下一篇 2022年9月18日 下午2:43
软件定制开发公司

相关阅读

发表回复

登录后才能评论
通知:禁止投稿所有关于虚拟货币,币圈类相关文章,发现立即永久封锁账户ID!