二维网格划分 LRU缓存设计
背景
- 有大量的二维矩形需要存储
- 查看点在哪些矩形中
- 给定一个矩形 查看与哪些矩阵相交
- 项目背景与图形图像基本无关，只涉及大文件分块读取，所以不用实现游戏行业中的物理引擎
设计思路
-
使用空间划分算法：二维栅格将整个空间划分为多个小区域。每个小区域中包含若干个矩形，以方便进行快速的范围查询。所以必须初始化网格大小int gridSize
数据索引为网格中的位置(x,y)，即：给定int xStart, int yStart, int width, int height, 计算给定数据块占整个空间哪些网格for (int i = xStart/gridSize; i <= (xStart+width )/gridSize; i++) {for (int j = yStart/gridSize; j <= (yStart + height)/gridSize; j++) {pair<int,int> position(i,j);//这就是计算输入矩阵占整个空间哪些网格DataCacheMap[position] = block;}}
注意： 因为本人 网格划分 与 文件划分保持一致，所以不存在一个位置有多个block的情况。
如果以后有这种情况，SrcDataCacheMap的类型要改成 std::unordered_map<pair<int, int>, list<LRULinkedNode*>>
- 采用LRU缓存设计：使用双向链表LRULinkedNode，和哈希表存储结构
i. 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
ii.哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
代码
文件分块的数据保存在 block
class block
{
...
// 矩形数据，其他业务数据自行添加int xStart,yStart, width, height;
}
双向链表LRULinkedNode
struct LRULinkedNode {pair<int, int> key; //这里的key是指 数据block在网格中的坐标block* value; //自己的数据LRULinkedNode* prev;LRULinkedNode* next;LRULinkedNode() : key(make_pair(0, 0)), value(nullptr), prev(nullptr), next(nullptr) {}LRULinkedNode(pair<int, int> _key, block* _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {}
};
LRUCache设计
头文件
class LRUCache
{
public:LRUCache(int _capacity,int _gridWidth,int _gridHeight);~LRUCache();void insertBlock(int xStart, int yStart, int width, int height);block* get(pair<int, int> key);
private:std::vector<LRULinkedNode*> findOverlappingRectangles(int xStart, int yStart, int width,int height);void addToHead(LRULinkedNode* node);void removeNode(LRULinkedNode* node);void moveToHead(LRULinkedNode* node);LRULinkedNode* removeTail();private:std::unordered_map<pair<int, int>, LRULinkedNode*> m_SrcDataCacheMap;LRULinkedNode* m_head;LRULinkedNode* m_tail;int m_size;//当前缓存数量int m_capacity; //缓存上线int m_gridWidth; //网格大小 宽int m_gridHeight;//网格大小 高
};
实现
#include "SrcDataCacheManager.h"LRUCache::LRUCache(int _capacity, int _gridWidth, int _gridHeight, int _nZoomIn, int _nZoomOut, int _nNumSubLayer):m_capacity(_capacity), m_gridWidth(_gridWidth), m_gridHeight(_gridHeight), m_size(0)
{// 使用伪头部和伪尾部节点m_head = new LRULinkedNode();m_tail = new LRULinkedNode();m_head->next = m_tail;m_tail->prev = m_head;
}void LRUCache::insertSrcDataBlock(int xStart, int yStart, int width, int height)
{std::vector<LRULinkedNode*> OverlappingBlockVec= findOverlappingRectangles(xStart, yStart, width, height);if (OverlappingBlockVec.size() > 0) //如果存在{for (auto iter : OverlappingBlockVec){moveToHead(iter);//移到头部}}else{block* pBlock = new block;for (int i = xStart / m_gridWidth; i <= (xStart + width) / m_gridWidth; i++){for (int j = yStart / m_gridHeight; j <= (yStart + height) / m_gridHeight; j++){pair<int, int> key(i, j);LRULinkedNode* pNode = new LRULinkedNode(key, pBlock);// 添加进哈希表m_SrcDataCacheMap[key] = pNode;// 添加至双向链表的头部addToHead(pNode);++m_size;if (m_size > m_capacity) {// 如果超出容量，删除双向链表的尾部节点LRULinkedNode* removed = removeTail();// 删除哈希表中对应的项m_SrcDataCacheMap.erase(removed->key);// 防止内存泄漏delete removed;--m_size;}}}}
}std::vector<LRULinkedNode*> LRUCache::findOverlappingRectangles(int xStart, int yStart, int width, int height)
{std::vector<LRULinkedNode*> OverlappingBlockVec;//如果在插入时，查看数据是否已经缓存，此时插入的数据和已经缓存的数据和gridSize大小一致, 只会返回1个块或者0个for (int i = xStart / m_gridWidth; i <= (xStart + width) / m_gridWidth; i++){for (int j = yStart / m_gridHeight; j <= (yStart + height) / m_gridHeight; j++){pair<int, int> key(i,j);if (m_SrcDataCacheMap.count(key) > 0){OverlappingBlockVec.push_back(m_SrcDataCacheMap[key]);}}}return OverlappingBlockVec;
}block* LRUCache::get(pair<int, int> key)
{if (!m_SrcDataCacheMap.count(key)) {return nullptr;}// 如果 key 存在，先通过哈希表定位，再移到头部LRULinkedNode* node = m_SrcDataCacheMap[key];moveToHead(node);return node->value;
}void LRUCache::addToHead(LRULinkedNode* node) {node->prev = m_head;node->next = m_head->next;m_head->next->prev = node;m_head->next = node;
}void LRUCache::removeNode(LRULinkedNode* node)
{if (node->prev){node->prev->next = node->next; }if (node->next){node->next->prev = node->prev;}}void LRUCache::moveToHead(LRULinkedNode* node) {removeNode(node);addToHead(node);
}LRULinkedNode* LRUCache::removeTail() {LRULinkedNode* node = m_tail->prev;removeNode(node);return node;
}注意
【C++】std::pair 作为 std::unordered_map 的 key