C++算法之LRU的原理是什么?

开课吧小白2021-07-13 11:57

算法需要积累,学会积累与运用比死记硬背强,如果在日常能遇到不同的场景,那么就在实践中记牢它,这样举一反三可以进一步掌握。今天就来讲讲C++的LRU实现原理。

它是采用双向链表和hash map来进行实现。这里采用双向链表的原因是:如果采用普通的单链表,则删除节点的时候需要从表头开始遍历查找,效率为O(n),采用双向链表可以直接改变节点的前驱的指针指向进行删除达到O(1)的效率。

使用hash map来保存节点的key、value值以及节点在双向链表中的迭代器位置,便于能在O(1)的时间查找元素。

#include <iostream>
#include <unordered_map>
#include <memory>
#include <string>

using namespace std;
// 双链表节点的定义
template<typename KEY, typename VALUE>
struct CacheNode
{
  int key;
  int value;
  CacheNode* prev {nullptr};
  CacheNode* next {nullptr};

  CacheNode(int key, int value) : key(key), value(value) {}
};

// 双向链表,构造函数需要指定容量大小
template<typename KEY, typename VALUE>
struct CacheList
{
  using CacheNode = CacheNode<KEY, VALUE>;
  using NodeUniquePtr = unique_ptr<CacheNode>;
private:
  int capacity;
  CacheNode* head {nullptr};
  CacheNode* tail {nullptr};

  unordered_map<KEY, NodeUniquePtr> CacheMap {};
public:
  CacheList(int capacity) : capacity(capacity) {}

private:
  // 双链表在头部插入节点
  void pushFront(CacheNode* newNode)
  {
    newNode->next = head;
    if(head != nullptr)
    {
      head->prev = newNode;
    }
    head = newNode;
    head->prev = nullptr;
    if(tail == nullptr)
    {
      tail = newNode;
      tail->next = nullptr;
    }
  }
  // 如果节点已经存在,更新节点位置
  void updateNodePosition(CacheNode* node)
  {
    if(node == head)
    {
      return ;
    }
    node->prev->next = node->next;
    if(node != tail)
    {
      node->next->prev = node->prev;
    }
    else
    {
      tail = node->prev;
    }
    node->next = head;
    node->prev = nullptr;

    head->prev = node;
    head = node;
  }
  // 双链表的删除尾节点
  void popBack()
  {
    CacheNode* newEnd = tail->prev;
    tail->prev->next = nullptr;
    tail->prev = nullptr;
    tail = newEnd;
  }

public:
  int currNum() const
  {
    return CacheMap.size();
  }

  // 增加节点
  void setNode(int key, int value)
  {
    auto it = CacheMap.find(key);
    if(it == CacheMap.end())
    {
      NodeUniquePtr newNode(new CacheNode(key, value));
      if(currNum() == capacity)
      {
        int latestNodeKey = tail->key;
        popBack();
        CacheMap.erase(latestNodeKey);
      }
      CacheMap.emplace(key, std::move(newNode));
      pushFront(CacheMap.at(key).get());
    }
    else
    {
      updateNodePosition(it->second.get());
    }
  }
  
  // 查找结点
  int getNode(int key)
  {
    auto it = CacheMap.find(key);
    if(it == CacheMap.end())
    {
      return -1;
    }
    updateNodePosition(it->second.get());
    return it->second.get()->value;
  }
  
  // 打印整个双向链表
  string printList() const
  {
    string str {""};
    if(CacheMap.empty())
    {
      return str;
    }
    else
    {
      CacheNode* node = head;
      while(node != nullptr)
      {
        str = str + "-" + std::to_string(node->key);
        node = node->next;
      }
    }
    return str;
  }
};

以上就是开课吧广场小编为大家整理发布的“C++算法之LRU的原理是什么?”一文,感兴趣的同学推荐听一下这节公开课,《掌握最简单的算法:穷举法》,点击下方图片领取。

C++

免责声明:本站所提供的内容均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用。如涉及版权问题,请联系本站管理员予以更改或删除。
有用
分享
全部评论快来秀出你的观点
登录 后可发表观点…
发表
暂无评论,快来抢沙发!
算法刷题核心能力提升营