phpstudy建设网站视频教程,零基础建设网站教程,建设购物网站的意义,wordpress直播功能插件LRU的概念
LRU#xff08;Least Recently Used#xff0c;最近最少使用#xff09;是一种常用的缓存淘汰策略#xff0c;主要目的是在缓存空间有限的情况下#xff0c;优先淘汰那些最长时间没有被访问的数据项。LRU 策略的核心思想是#xff1a; 缓存空间有限#xff1…
LRU的概念
LRULeast Recently Used最近最少使用是一种常用的缓存淘汰策略主要目的是在缓存空间有限的情况下优先淘汰那些最长时间没有被访问的数据项。LRU 策略的核心思想是 缓存空间有限缓存只能存储一定数量的数据项。 淘汰最不常用的数据当缓存满时优先淘汰那些最近最少被访问的数据项。 访问记录每次数据项被访问时都会更新其访问记录使得最近访问的数据项保留在缓存中。 数据替换当需要加载新数据项到缓存中但缓存已满时会根据LRU策略淘汰一个或多个数据项为新数据项腾出空间。 动态调整随着数据访问模式的变化LRU策略可以动态调整缓存中的数据项以适应访问模式的变化。
在实现LRU缓存时通常会使用数据结构如哈希表和双向链表。哈希表用于快速定位缓存中的数据项而双向链表则用于维护数据项的访问顺序。每次访问数据项时都会将其移动到链表的头部表示它是最近被访问的。当需要淘汰数据时直接从链表的尾部开始淘汰即可。
LRU策略在许多场景中都非常有用比如操作系统的页面置换、数据库的查询缓存、Web服务器的页面缓存等。它可以帮助系统更有效地利用有限的缓存资源提高系统的整体性能。 别急我们先学实现LRU要用的哈希表和双向链表
哈希表unordered_map
在C中unordered_map 是标准模板库STL中的一个关联容器它基于哈希表的实现。它存储了键值对允许通过键快速访问和修改值。unordered_map 提供了平均常数时间复杂度的访问、插入和删除操作。
主要特性
基于哈希表通过哈希函数将键映射到存储位置实现快速查找。键不重复每个键在容器中是唯一的。无序存储元素的存储顺序不依赖于插入顺序因此迭代器的遍历顺序可能与插入顺序不同。
常用操作 构造和初始化 unordered_map()创建一个空的 unordered_map。unordered_map(initializer_listvalue_type)使用初始化列表创建 unordered_map。 插入操作 insert(value_type)插入一个键值对。insert(initializer_listvalue_type)插入多个键值对。 访问操作 operator[]通过键访问对应的值如果键不存在则插入一个新元素。at(key)通过键访问对应的值如果键不存在则抛出 std::out_of_range 异常。 查找操作 find(key)查找键是否存在返回一个迭代器。count(key)返回键出现的次数对于 unordered_map 总是返回 0 或 1。 删除操作 erase(it)删除迭代器 it 指向的元素。erase(first, last)删除从 first 到 last不包括 last范围内的所有元素。erase(key)删除指定键的所有元素。 大小和容量 size()返回容器中元素的数量。empty()如果容器为空返回 true。 迭代器 begin()返回指向容器开始的迭代器。end()返回指向容器结束的迭代器。
示例代码
以下是使用 unordered_map 的一个简单示例
#include iostream
#include unordered_mapint main() {// 创建一个 unordered_map键为 int值为 stringunordered_mapint, string umap;// 插入元素umap[1] one;umap[2] two;umap[3] three;// 访问并打印元素for (const auto pair : umap) {std::cout pair.first : pair.second std::endl;}// 访问特定键的值try {std::cout Value for key 2: umap.at(2) std::endl;} catch (const std::out_of_range e) {std::cerr e.what() std::endl;}// 查找键是否存在auto it umap.find(3);if (it ! umap.end()) {std::cout Key 3 found, value: it-second std::endl;}// 删除元素umap.erase(2);std::cout After erasing key 2: std::endl;for (const auto pair : umap) {std::cout pair.first : pair.second std::endl;}return 0;
}输出
1: one
2: two
3: three
Value for key 2: two
Key 3 found, value: three
After erasing key 2:
1: one
3: three在这个示例中
创建了一个 unordered_map 并插入了一些键值对。遍历并打印了 unordered_map 中的所有元素。使用 at() 方法安全地访问特定键的值。使用 find() 方法查找键是否存在并访问对应的值。使用 erase() 方法删除了键为 2 的元素并再次打印了剩余的元素。
双向链表list
在C中list 是标准模板库STL中的一个容器类它提供了双向链表的实现。与数组或向量vector不同list 允许在任意位置高效地插入和删除元素而不需要移动其他元素。
以下是 list 的一些主要特性和常用操作
特性
双向链表每个元素都是链表中的一个节点可以从前向后或从后向前遍历。动态大小list 的大小可以根据需要动态变化不需要预先定义大小。插入和删除操作可以在常数时间内在任意位置插入或删除元素不需要像 vector 那样移动其他元素。
常用操作 插入操作 push_front(value)在链表头部插入一个元素。push_back(value)在链表尾部插入一个元素。insert(position, value)在指定位置插入一个元素。insert(position, n, value)在指定位置插入 n 个相同的元素。insert(position, first, last)在指定位置插入一个范围内的元素。 删除操作 pop_front()删除链表头部的元素。pop_back()删除链表尾部的元素。erase(position)删除指定位置的元素。erase(first, last)删除从 first 到 last不包括 last范围内的所有元素。 访问操作 front()返回链表头部的元素。back()返回链表尾部的元素。 迭代器 begin()返回指向链表头部的迭代器。end()返回指向链表尾部的迭代器。 大小和容量 size()返回链表中元素的数量。empty()如果链表为空返回 true。
示例代码
以下是使用 list 的一个简单示例
#include iostream
#include listint main() {listint myList;// 向链表中添加元素myList.push_back(10);myList.push_back(20);myList.push_front(5);// 访问并打印链表中的元素for (listint::iterator it myList.begin(); it ! myList.end(); it) {std::cout *it ;}std::cout std::endl;// 删除头部元素myList.pop_front();std::cout After popping front: ;for (auto it myList.begin(); it ! myList.end(); it) {std::cout *it ;}std::cout std::endl;// 删除尾部元素myList.pop_back();std::cout After popping back: ;for (auto it myList.begin(); it ! myList.end(); it) {std::cout *it ;}std::cout std::endl;return 0;
}输出
5 10 20
After popping front: 10 20
After popping back: 10 在这个示例中我们创建了一个 list 并添加了一些整数元素。然后我们遍历并打印链表中的元素删除头部和尾部的元素并再次打印链表中的元素。 到这里你已经掌握实现LRU缓存的两个条件了马上你就要成功了 真的不信你往下看
LRU缓存C
#include iostream
#include list
#include unordered_map// 使用 using namespace std; 来简化代码避免重复书写 std:: 前缀
using namespace std;// LRUCache 类定义
class LRUCache {
private:int capacity; // 缓存的容量listint keys; // 使用双向链表存储键保持访问顺序unordered_mapint, pairint, listint::iterator cache; // 存储键值对和对应的链表迭代器public:// 构造函数初始化缓存容量LRUCache(int capacity) : capacity(capacity) {}// 获取缓存中键对应的值int get(int key) {auto it cache.find(key);if (it cache.end()) {return -1; // 如果键不存在返回 -1}// 更新访问顺序将该键移动到链表头部keys.erase(it-second.second);keys.push_front(key);it-second.second keys.begin();return it-second.first; // 返回键对应的值}// 插入或更新缓存中的键值对void put(int key, int value) {if (cache.size() capacity cache.find(key) cache.end()) {// 如果缓存已满且键不存在淘汰最不常用的键链表尾部的键auto last keys.back();cache.erase(cache.find(last));keys.pop_back();}// 插入或更新键值对并更新访问顺序cache[key] {value, keys.insert(keys.begin(), key)};}
};int main() {// 创建一个容量为 2 的 LRU 缓存LRUCache cache(2);// 插入键值对 (1, 1)cache.put(1, 1);// 访问键 1输出其值cout get(1) cache.get(1) endl; // 返回 1// 插入键值对 (2, 2)cache.put(2, 2);// 访问键 2输出其值cout get(2) cache.get(2) endl; // 返回 2// 插入键值对 (3, 3)由于缓存已满键 1 被淘汰cache.put(3, 3);// 访问键 1由于已被淘汰返回 -1cout get(1) cache.get(1) endl; // 返回 -1// 访问键 3输出其值cout get(3) cache.get(3) endl; // 返回 3// 插入键值对 (4, 4)由于缓存已满键 2 被淘汰cache.put(4, 4);// 访问键 1由于已被淘汰返回 -1cout get(1) cache.get(1) endl; // 返回 -1// 访问键 3输出其值cout get(3) cache.get(3) endl; // 返回 3// 访问键 2由于已被淘汰返回 -1cout get(2) cache.get(2) endl; // 返回 -1// 访问键 4输出其值cout get(4) cache.get(4) endl; // 返回 4return 0;
}这段代码首先定义了一个 LRUCache 类该类使用 unordered_map 和 list 来实现 LRU 缓存机制。get 方法用于获取缓存中的值如果键存在则返回其值并更新访问顺序如果键不存在则返回 -1。put 方法用于插入或更新缓存中的键值对如果缓存已满则淘汰最不常用的键链表尾部的键。在 main 函数中创建了一个 LRUCache 对象并进行了一些操作来演示其功能。 什么看不懂没关系结合下面的过程看你应该就明白了
初始化状态
Cache: {}
Keys: []执行 cache.put(1, 1)
Cache: {1: (1, it1)}
Keys: [1]执行 cache.put(2, 2)
Cache: {1: (1, it1), 2: (2, it2)}
Keys: [2, 1] (2 最近使用1 最少使用)执行 cache.put(3, 3)
缓存已满淘汰键 1
Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2] (3 最近使用2 次之)执行 cache.get(1)
键 1 不存在返回 -1
Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2]执行 cache.get(3)
键 3 存在返回 3并更新为最近使用
Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2]执行 cache.put(4, 4)
缓存已满淘汰键 2
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3] (4 最近使用3 次之)执行 cache.get(1)
键 1 不存在返回 -1
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3]执行 cache.get(3)
键 3 存在返回 3并更新为最近使用
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [3, 4]执行 cache.get(2)
键 2 不存在返回 -1
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [3, 4]执行 cache.get(4)
键 4 存在返回 4并更新为最近使用
Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3]至此你就算没有台明白也一定了解LRU了。收藏可以方便下次巩固哦
