当前位置：首页 > news >正文

并查集LRU cache

news 来源：原创 2024/9/22 6:35:40

并查集的定义

将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union find set)

并查集的抽象描述

struct UnionFindSet
属性
数个不相交的集合,通过数组管理 vector
方法
检查两个元素是否属于同一个集合 bool inSameSet(e1,e2);
寻找集合的根元素 e findEigen(e) ;
合并两个元素所在的集合 void merge(e1,e1);
计算当前集合个数 size_t getCnt();

如何表示同一个集合的元素：
可以借助数组抽象结构的方法对同一集合的元素进行分类，为了方便，后续把代表某个集合的元素成为特征元素
首先把每一个元素都被映射成了一个唯一的编号id，id同时也作为数组的下标
规定每一个下标所对应值为集合中其他元素的编号id，如果数组中某一个id位置的值为-x，代表它是一个特征元素,并且集合中有x个元素

![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/acbe9e49efa14b8d80c19692a2c4e07e.png

并查集具体实现

//此处代码忽略了映射关系的构建，数组下标值就是对应的真实元素值
class UnionFindSet
{
private:vector<int> ufs;
public:UnionFindSet(unsigned int n=0):ufs(n,-1){}  //初始状态所有的元素都各自为一个集合，元素之间没有任何关系unsigned int getCnt(){unsigned int cnt=0;for(int x:ufs) if(x==-1) ++cnt;return cnt;}	//统计ufs数组中-1的个数即可获得集合个数unsigned int findEigen(unsigned int e){	unsigned int eigenval=e;while(ufs[eigenval]>=0) eigenval=ufs[eigenval];return eigenval;}	//迭代向上寻找，直至数组中的值为-1bool inSameSet(unsigned int e1,unsigned int e2){return findEigen(e1)==findEigen(e2);}void merge(unsigned int e1,unsigned int e2){unsigned int eigen1=findEigen(e1);unsigned int eigen2=findEigen(e2);if(eigen1!=eigen2) {ufs[eigen1]+=ufs[eigen2];ufs[eigen2]=eigen1;}//把e2所在集合的特征元素对应的值改为e1所在集合的特征元素即可完成2个集合的合并}
};

优化合并与查找

合并优化：小集合合并到大集合中，做到更多的元素能在短时间内找到特征元素
在这里插入图片描述

void merge(unsigned int e1,unsigned int e2)
{unsigned int eigen1=findEigen(e1);unsigned int eigen2=findEigen(e2);if(eigen1!=eigen2){if(ufs[eigen1]>ufs[eigen2]) swap(eigen1,eigen2); //统一规定集合eigen1的元素个数更大ufs[eigen1]+= ufs[eigen2];ufs[eigen2]=eigen1;}
}

查找优化：最理想的情况是每一个节点至多一次找到所在集合的特征元素
在这里插入图片描述
可以考虑每一次进行findEigen查找时对集合元素关系进行调整，使得每一个元素在集合中更接近特征元素

unsigned int findEigen(unsigned int e) 
{unsigned int eigen = e, prev = -1;while (_ufs[eigen] >= 0) {int tmp = ufs[eigen];//向上查找if (prev>=0) ufs[prev] = tmp;prev = eigen;eigen = tmp;}return eigen;
}

上述代码未经测试，可能存在bug，经测试版代码请参考https://gitee.com/chxchenhaixiao/test_c/blob/master/UnionFindSet/UnionFindSet.h

LRU cache

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法
简单地说就是淘汰长久未使用的数据，cache的大小是固定有限的，当空间满时如果还需要加入数据就必须淘汰部分先前的数据

可以把每一个数据块通过一个双向链表级联，人为规定链表尾节点为长时间未使用即将被淘汰的资源，链表头节点为最近使用的数据，借助哈希表实现对各个数据块的快速定位，达到增删查改的时间复杂度均为O（1）
在这里插入图片描述

在这里插入图片描述

代码实现：

class LRUCache {size_t _size=0; //链表当前长度size_t _capacity; //cache最大容量list<pair<int,int>> _list;typedef list<pair<int,int>>::iterator iterator;unordered_map<int,iterator> _map;
public:LRUCache(int capacity) :_capacity(capacity){}int get(int key) {if(!_map.count(key)) return -1;iterator it=_map[key];int val=it->second;_list.push_front(*it);_list.erase(it);_map[key]=_list.begin();return val;}void put(int key, int value) {if(_map.count(key)) //更新节点{iterator it=_map[key];it->second=value;_list.push_front(*it);_list.erase(it);_map[key]=_list.begin();}else{if(_size<_capacity){++_size;_list.push_front({key,value});_map[key]=_list.begin();}else{auto& last=_list.back(); //获取链表尾节点_map.erase(last.first); //删除map中指向尾的映射关系_list.pop_back();   //删除链表尾节点_list.push_front({key,value}); //头插_map[key]=_list.begin(); //更新map}}}
};