并查集LRU cache

并查集的定义

将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;
	}	//迭代向上寻找，直至数组中的值为-1
	bool 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
            }
        }
    }
};