哈尔滨微信网站建设,wordpress最新文章id,桂林北站时刻表,python基础教程电子书百度网盘背景
有大量的二维矩形需要存储查看点在哪些矩形中给定一个矩形 查看与哪些矩阵相交项目背景与图形图像基本无关#xff0c;只涉及大文件分块读取#xff0c;所以不用实现游戏行业中的物理引擎
设计思路 使用空间划分算法#xff1a;二维栅格将整个空间划分为多个小区域。…背景
有大量的二维矩形需要存储查看点在哪些矩形中给定一个矩形 查看与哪些矩阵相交项目背景与图形图像基本无关只涉及大文件分块读取所以不用实现游戏行业中的物理引擎
设计思路 使用空间划分算法二维栅格将整个空间划分为多个小区域。每个小区域中包含若干个矩形以方便进行快速的范围查询。所以必须初始化网格大小int gridSize 数据索引为网格中的位置(x,y)即给定int xStart, int yStart, int width, int height, 计算给定数据块占整个空间哪些网格 for (int i xStart/gridSize; i (xStartwidth )/gridSize; i) {for (int j yStart/gridSize; j (yStart height)/gridSize; j) {pairint,int position(i,j);//这就是计算输入矩阵占整个空间哪些网格DataCacheMap[position] block;}}注意 因为本人 网格划分 与 文件划分保持一致所以不存在一个位置有多个block的情况。 如果以后有这种情况SrcDataCacheMap的类型要改成 std::unordered_mappairint, int, listLRULinkedNode*
采用LRU缓存设计使用双向链表LRULinkedNode和哈希表存储结构 i. 双向链表按照被使用的顺序存储了这些键值对靠近头部的键值对是最近使用的而靠近尾部的键值对是最久未使用的。 ii.哈希表即为普通的哈希映射HashMap通过缓存数据的键映射到其在双向链表中的位置。
代码
文件分块的数据保存在 block
class block
{
...
// 矩形数据其他业务数据自行添加int xStart,yStart, width, height;
}双向链表LRULinkedNode
struct LRULinkedNode {pairint, int key; //这里的key是指 数据block在网格中的坐标block* value; //自己的数据LRULinkedNode* prev;LRULinkedNode* next;LRULinkedNode() : key(make_pair(0, 0)), value(nullptr), prev(nullptr), next(nullptr) {}LRULinkedNode(pairint, 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(pairint, int key);
private:std::vectorLRULinkedNode* 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_mappairint, int, LRULinkedNode* m_SrcDataCacheMap;LRULinkedNode* m_head;LRULinkedNode* m_tail;int m_size;//当前缓存数量int m_capacity; //缓存上线int m_gridWidth; //网格大小 宽int m_gridHeight;//网格大小 高
};实现
#include SrcDataCacheManager.hLRUCache::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::vectorLRULinkedNode* 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){pairint, 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::vectorLRULinkedNode* LRUCache::findOverlappingRectangles(int xStart, int yStart, int width, int height)
{std::vectorLRULinkedNode* 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){pairint, int key(i,j);if (m_SrcDataCacheMap.count(key) 0){OverlappingBlockVec.push_back(m_SrcDataCacheMap[key]);}}}return OverlappingBlockVec;
}block* LRUCache::get(pairint, 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
