二维网格划分 LRU缓存设计

这篇具有很好参考价值的文章主要介绍了二维网格划分 LRU缓存设计。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

背景

  1. 有大量的二维矩形需要存储
  2. 查看点在哪些矩形中
  3. 给定一个矩形 查看与哪些矩阵相交
  4. 项目背景与图形图像基本无关,只涉及大文件分块读取,所以不用实现游戏行业中的物理引擎

设计思路

  1. 使用空间划分算法:二维栅格将整个空间划分为多个小区域。每个小区域中包含若干个矩形,以方便进行快速的范围查询。所以必须初始化网格大小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*>>

  1. 采用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文章来源地址https://www.toymoban.com/news/detail-625572.html

到了这里,关于二维网格划分 LRU缓存设计的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】LRU缓存的简单模拟实现(leetcode力扣146LRU缓存)

    LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。 Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。

    2024年02月03日
    浏览(43)
  • 【算法】用JAVA代码实现LRU 【缓存】【LRU】

    LRU(Least Recently Used)是一种常见的缓存淘汰策略,用于在缓存空间不足时确定哪些数据应该被淘汰。其基本原则是淘汰最近最少被访问的数据。 工作原理 : 最近使用优先 : LRU算法基于这样的思想:最近被使用的数据很可能在短时间内还会被使用,因此保留这些数据有助于

    2024年01月23日
    浏览(46)
  • 35、链表-LRU缓存

            首先要了解LRU缓存的原理,首先定下容量,每次get请求和put请求都会把当前元素放最前/后面,如果超过容量那么头部/尾部元素就被移除,所以最近最少使用的元素会被优先移除,保证热点数据持续存在。 不管放在头部还是尾部都可以。看你怎么定义         那

    2024年04月23日
    浏览(38)
  • 【LeetCode】146.LRU缓存

    请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。 实现  LRUCache  类: LRUCache(int capacity)  以  正整数  作为容量  capacity  初始化 LRU 缓存 int get(int key)  如果  key  存在于缓存中,则返回的值,否则返回  -1  。 void put(int key, int value)  如果

    2024年02月09日
    浏览(43)
  • LRU 缓存结构

    优先去除最久没有访问到的数据。 通过组合哈希表(Hash Table)和双向链表(Doubly Linked List)实现 LRU 缓存。并且以 O(1) 的时间复杂度执行 get 和 put 操作 核心是对节点的新增、访问都会让节点移动到双向链表头部,当容量超过时,直接删除尾部节点即可

    2024年02月15日
    浏览(49)
  • LRU 缓存淘汰算法

    Least Recently Used(LRU) 是缓存淘汰一种常用的策略,内存满了则优先删除最久没被使用的数据。 接收一个参数 capacity 作为缓存的最大容量 实现一个函数 put() 添加数据到缓存 实现一个函数 get() 查询缓存中的数据 以上函数应该在 (O(1)) 的时间内完成 满足以上需求的数据结构 —

    2024年02月11日
    浏览(60)
  • LeetCode刷题---LRU缓存

    LRU是Least Recently Used的缩写,即最近最少使用,是一种内存管理算法,也可以用作缓存淘汰策略。 这种算法的核心思想是:如果数据最近被访问过,那么将来被访问的几率也更高。 因此,当内存或缓存容量有限,需要淘汰部分数据时,LRU算法会优先淘汰那些最长时间未被访问

    2024年02月22日
    浏览(38)
  • leetcode 146. LRU 缓存

             本题核心就是要将map中,最近最少操作的那个key给剔除掉,于是我们可以使用双端链表LinkedList 来维护每个元素的操作情况,最近操作的元素就将其移至表头,越久没操作的元素,自然就会沉到表尾。  一旦缓存满了,将表尾元素剔除即可。  java代码如下:

    2024年02月08日
    浏览(43)
  • LRU 缓存

    LRU 缓存 如果插入操作导致数量超过 capacity ,则应该 逐出 最久未使用的 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行 如果想以O(1)的速度进行get,则需要将对应的key、value存到map中 如果想以O(1)的速度进行put,又因为插入的时候可能由于空间已满需要将最久未

    2024年02月16日
    浏览(33)
  • HOT35-LRU缓存

            leetcode原题链接 :LRU缓存         上一篇 :HOT34-合并K个升序链表        下一篇 :HOT36-二叉树的中序遍历        请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。 实现  LRUCache  类: LRUCache(int capacity)  以  正整数  作为容量  capacity  初始

    2024年02月12日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包