背景
- 有大量的二维矩形需要存储
- 查看点在哪些矩形中
- 给定一个矩形 查看与哪些矩阵相交
- 项目背景与图形图像基本无关,只涉及大文件分块读取,所以不用实现游戏行业中的物理引擎
设计思路
-
使用空间划分算法:二维栅格将整个空间划分为多个小区域。每个小区域中包含若干个矩形,以方便进行快速的范围查询。所以必须初始化网格大小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;//网格大小 高
};
实现文章来源:https://www.toymoban.com/news/detail-625572.html
#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文章来源地址https://www.toymoban.com/news/detail-625572.html
到了这里,关于二维网格划分 LRU缓存设计的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!