一、LRU缓存

ops/2024/12/19 19:21:52/

LRU缓存

1.LRU缓存介绍

LRU是Least Recently Used 的缩写，意为“最近最少使用”。它是一种常见的缓存淘汰策略，用于在缓存容量有限时，决定哪些数据需要被删除以腾出空间。
LRU 缓存的基本原则是：
①优先保留最近被访问的数据，因为这些数据在近期被再次访问的概率更高。
②淘汰最近最少使用的数据，因为它们被再次访问的可能性较小。

2.LRU缓存实现

接下来我将通过c语言中的glib库来实现一个LRU缓存结构。
首先给出结构体定义：

struct lruCache {GList *elem_queue;  // 使用 GList 作为双向链表存储缓存元素。int max_size;       // 缓存最大容量，<0 表示无限大小（INFI_Cache）。int size;           // 当前缓存已使用的大小。double hit_count;   // 命中次数统计。double miss_count;  // 未命中次数统计。void (*free_elem)(void *);                  // 用户定义的释放元素函数。int (*hit_elem)(void* elem, void* user_data); // 判断命中元素的回调函数。
};

需要实现如下功能：

struct lruCache* new_lru_cache(int size, void (*free_elem)(void *),int (*hit_elem)(void* elem, void* user_data));
// 创建一个新的 LRU 缓存，指定容量和自定义的释放与命中回调函数。void free_lru_cache(struct lruCache*);
// 释放缓存及其中的所有元素。void* lru_cache_lookup(struct lruCache*, void* user_data);
// 查找元素，若命中，将其移到链表头部；未命中返回 NULL。void* lru_cache_lookup_without_update(struct lruCache* c, void* user_data);
// 查找元素但不更新其在链表中的顺序。void* lru_cache_hits(struct lruCache* c, void* user_data,int (*hit)(void* elem, void* user_data));
// 模拟命中某个元素，满足自定义命中条件后将元素移到链表头部。void lru_cache_kicks(struct lruCache* c, void* user_data,int (*func)(void* elem, void* user_data));
// 删除满足用户自定义条件的元素。void lru_cache_insert(struct lruCache *c, void* data,void (*victim)(void*, void*), void* user_data);
// 插入新数据到缓存，若缓存已满则淘汰最久未使用的元素，并调用 victim 函数处理被淘汰的数据。int lru_cache_is_full(struct lruCache*);
// 检查缓存是否已满，已满返回 1，未满返回 0。

具体实现代码：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "lru_cache.h"struct lruCache* new_lru_cache(int size, void (*free_elem)(void *),int (*hit_elem)(void* elem, void* user_data)) {struct lruCache* c = (struct lruCache*) malloc(sizeof(struct lruCache));c->elem_queue = NULL;c->max_size = size;c->size = 0;c->hit_count = 0;c->miss_count = 0;c->free_elem = free_elem;c->hit_elem = hit_elem;return c;
}void free_lru_cache(struct lruCache *c) {if (c == NULL) return;  // 防止对 NULL 指针调用if (c->elem_queue != NULL) {// 确保对每个元素调用释放函数g_list_free_full(c->elem_queue, c->free_elem);c->elem_queue = NULL;  // 清空队列，防止重复释放}// 清理 lruCache 结构体本身free(c);
}/* find a item in cache matching the condition */
void* lru_cache_lookup(struct lruCache* c, void* user_data) {// 获取链表的第一个节点（链表头部）GList* elem = g_list_first(c->elem_queue);// 遍历链表，查找匹配的元素while (elem) {/** 使用回调函数 hit_elem 判断当前节点的数据是否与 user_data 匹配。* 回调函数由用户提供，自定义匹配逻辑。*/if (c->hit_elem(elem->data, user_data))break;  // 找到匹配的元素，退出循环// 继续遍历下一个节点elem = g_list_next(elem);}// 如果找到匹配的元素if (elem) {/** 将命中的元素移到链表头部，保持 LRU 缓存的访问顺序。* 1. 先从链表中移除该元素。* 2. 将该元素连接到链表头部。*/c->elem_queue = g_list_remove_link(c->elem_queue, elem);c->elem_queue = g_list_concat(elem, c->elem_queue);// 增加缓存命中计数c->hit_count++;// 返回命中元素的数据return elem->data;} else {// 如果未找到匹配的元素，增加缓存未命中计数c->miss_count++;return NULL;  // 返回 NULL 表示未命中}
}void* lru_cache_lookup_without_update(struct lruCache* c, void* user_data) {GList* elem = g_list_first(c->elem_queue);while (elem) {if (c->hit_elem(elem->data, user_data))break;elem = g_list_next(elem);}if (elem) {return elem->data;} else {return NULL;}
}/** Hit an existing elem for simulating an insertion of it.*/
void* lru_cache_hits(struct lruCache* c, void* user_data,int (*hit)(void* elem, void* user_data)) {GList* elem = g_list_first(c->elem_queue);while (elem) {if (hit(elem->data, user_data))break;elem = g_list_next(elem);}if (elem) {c->elem_queue = g_list_remove_link(c->elem_queue, elem);c->elem_queue = g_list_concat(elem, c->elem_queue);return elem->data;} else {return NULL;}
}/** We know that the data does not exist!*/
void lru_cache_insert(struct lruCache *c, void* data,void (*func)(void*, void*), void* user_data) {void *victim = NULL; // 存储被淘汰的数据// 检查缓存是否已满if (c->max_size > 0 && c->size == c->max_size) {// 获取链表尾部的节点（最久未使用的数据）GList *last = g_list_last(c->elem_queue);// 从链表中移除尾部节点c->elem_queue = g_list_remove_link(c->elem_queue, last);// 保存被淘汰的数据victim = last->data;// 释放链表节点（但不释放节点内的数据）g_list_free_1(last);// 更新缓存大小c->size--;}// 将新数据插入到链表头部（表示最近使用）c->elem_queue = g_list_prepend(c->elem_queue, data);// 更新缓存大小c->size++;// 如果有被淘汰的数据if (victim) {// 调用用户自定义回调函数处理被淘汰的数据（如果提供了 func）if (func)func(victim, user_data);// 调用 free_elem 回调释放被淘汰的数据c->free_elem(victim);}
}/** 从缓存中移除符合用户定义条件的元素。* * 参数:*   c          - 指向 lruCache 结构体的指针。*   user_data  - 用户自定义的数据，用于传递给回调函数 func。*   func       - 用户自定义的回调函数，用于判断当前元素是否需要被移除。*                返回非 0（true）表示移除该元素，返回 0（false）继续遍历。*/
void lru_cache_kicks(struct lruCache* c, void* user_data,int (*func)(void* elem, void* user_data)) {// 从链表尾部开始遍历（最久未使用的数据）GList* elem = g_list_last(c->elem_queue);// 遍历链表，向前移动，查找符合条件的节点while (elem) {/** 调用用户提供的回调函数 func，判断当前节点的数据是否符合移除条件。* 参数:*   elem->data  - 当前节点存储的数据。*   user_data   - 用户提供的上下文数据。*/if (func(elem->data, user_data)) break; // 如果找到符合条件的节点，退出循环elem = g_list_previous(elem); // 移动到前一个节点}// 如果找到了符合条件的节点if (elem) {/** 1. 从链表中移除该节点（但不释放节点内存和数据）。*    g_list_remove_link 返回移除后的链表。*/c->elem_queue = g_list_remove_link(c->elem_queue, elem);/** 2. 释放节点中存储的数据。*    调用用户提供的 free_elem 函数，确保数据被正确释放，防止内存泄漏。*/c->free_elem(elem->data);/** 3. 释放链表节点本身的内存。*    注意：g_list_free_1 只释放 GList 结构，不释放节点数据。*/g_list_free_1(elem);// 4. 更新缓存大小c->size--;}
}int lru_cache_is_full(struct lruCache* c) {return c->size >= c->max_size ? 1 : 0;
}

简单测试代码：

#include <stdio.h>
#include <stdlib.h>
#include "lru_cache.h"// 自定义释放函数：释放节点数据
void free_data(void* data) {printf("Freeing data: %d\n", *(int*)data);free(data);
}// 自定义匹配函数：判断数据是否匹配用户输入
int match_data(void* elem, void* user_data) {return (*(int*)elem == *(int*)user_data);
}// 主函数：测试 LRU 缓存
int main() {printf("---- Testing LRU Cache ----\n");// 创建一个容量为 3 的 LRU 缓存struct lruCache* cache = new_lru_cache(3, free_data, match_data);// 插入测试数据int* a = malloc(sizeof(int)); *a = 1;int* b = malloc(sizeof(int)); *b = 2;int* c = malloc(sizeof(int)); *c = 3;int* d = malloc(sizeof(int)); *d = 4;printf("Inserting: 1, 2, 3\n");lru_cache_insert(cache, a, NULL, NULL);lru_cache_insert(cache, b, NULL, NULL);lru_cache_insert(cache, c, NULL, NULL);// 查找数据：命中情况int target = 2;int* result = lru_cache_lookup(cache, &target);if (result) {printf("Cache hit: %d\n", *result);} else {printf("Cache miss: %d\n", target);}// 插入数据 4，导致数据 1 被淘汰printf("Inserting: 4 (This should evict 1)\n");lru_cache_insert(cache, d, NULL, NULL);// 再次查找数据 1：应该未命中target = 1;result = lru_cache_lookup(cache, &target);if (result) {printf("Cache hit: %d\n", *result);} else {printf("Cache miss: %d\n", target);}// 查找数据 3：应该命中target = 3;result = lru_cache_lookup(cache, &target);if (result) {printf("Cache hit: %d\n", *result);} else {printf("Cache miss: %d\n", target);}// 释放缓存free_lru_cache(cache);printf("---- LRU Cache Test Complete ----\n");return 0;
}

测试结果：
在这里插入图片描述
这是一个非常简单的测试代码，其实上面的LRU缓存实现是和数据类型无关的，因为我们通过函数指针提供了对数据的操作抽象，例如：
free_elem 回调：
允许用户自定义如何释放节点中的数据，可以适配不同类型的内存管理。
hit_elem 回调：
允许用户自定义数据匹配逻辑，适配任意类型的比较需求。
这些设计使得我们的缓存可以支持任意类型的数据，而不仅仅是局限在int类型。
下面我们来一个自定义数据类型的测试代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "lru_cache.h"// 自定义数据类型：Person
typedef struct {char* name;int age;
} Person;// 自定义释放函数：释放 Person 类型的数据
void free_person(void* data) {Person* person = (Person*)data;printf("[Free] Name = %s, Age = %d\n", person->name, person->age);free(person->name); // 释放 name 字符串free(person);       // 释放 Person 结构体
}// 自定义匹配函数：根据姓名匹配 Person
int match_person(void* elem, void* user_data) {Person* person = (Person*)elem;char* target_name = (char*)user_data;return strcmp(person->name, target_name) == 0;
}// 工具函数：创建 Person 对象
Person* create_person(const char* name, int age) {Person* person = malloc(sizeof(Person));person->name = strdup(name); // 分配并复制 nameperson->age = age;return person;
}// 测试函数：打印缓存的命中率统计信息
void print_cache_stats(struct lruCache* cache) {printf("Cache Stats: Hits = %.0f, Misses = %.0f, Hit Rate = %.2f%%\n",cache->hit_count,cache->miss_count,cache->hit_count / (cache->hit_count + cache->miss_count) * 100.0);
}int main() {printf("---- Comprehensive LRU Cache Test ----\n");// 创建容量为 3 的 LRU 缓存struct lruCache* cache = new_lru_cache(3, free_person, match_person);// 插入数据：Person 结构体printf("Inserting: Alice, Bob, Charlie\n");lru_cache_insert(cache, create_person("Alice", 25), NULL, NULL);lru_cache_insert(cache, create_person("Bob", 30), NULL, NULL);lru_cache_insert(cache, create_person("Charlie", 35), NULL, NULL);// 查找数据：命中 Bobprintf("Looking up: Bob\n");char* target_name = "Bob";Person* result = (Person*)lru_cache_lookup(cache, target_name);if (result) {printf("[Hit] Found: Name = %s, Age = %d\n", result->name, result->age);} else {printf("[Miss] Not found: %s\n", target_name);}// 插入新数据 Dave，触发淘汰最久未使用的数据 Aliceprintf("Inserting: Dave (Evicts Alice)\n");lru_cache_insert(cache, create_person("Dave", 40), NULL, NULL);// 查找 Alice：未命中printf("Looking up: Alice\n");target_name = "Alice";result = (Person*)lru_cache_lookup(cache, target_name);if (result) {printf("[Hit] Found: Name = %s, Age = %d\n", result->name, result->age);} else {printf("[Miss] Not found: %s\n", target_name);}// 查找 Charlie：命中printf("Looking up: Charlie\n");target_name = "Charlie";result = (Person*)lru_cache_lookup(cache, target_name);if (result) {printf("[Hit] Found: Name = %s, Age = %d\n", result->name, result->age);} else {printf("[Miss] Not found: %s\n", target_name);}// 打印缓存的命中率统计信息print_cache_stats(cache);// 释放缓存printf("Freeing the cache...\n");free_lru_cache(cache);printf("---- LRU Cache Test Complete ----\n");return 0;
}

测试结果：
在这里插入图片描述
上面的LRU缓存代码其实是一个设计精巧、功能全面的缓存实现，具有高度的通用性和灵活性。通过将缓存管理逻辑与数据操作解耦，提供了标准化的接口，包括 元素插入、查找、淘汰、命中统计等功能，同时通过回调函数支持任意数据类型的自定义释放和匹配逻辑。
核心优势总结：
①模块化设计：通过free_elem和hit_elem回调函数，适配不同数据类型，用户无需修改核心代码即可实现各种缓存需求。
②功能丰富：支持 LRU 淘汰策略，自动移除最久未使用的数据。提供查找、插入、条件删除、命中模拟等多种操作接口。统计命中次数和未命中次数，便于分析缓存性能。
③内存管理安全：使用 free_elem 回调释放数据，确保内存不会泄漏。
④易于扩展：代码逻辑清晰，接口简单易用，方便进一步添加功能，如并发支持、过期数据清理等

3.LRU缓存总结

接下来我将通过两个表格来简要描述一下LRU缓存的应用以及优缺点。

3.1 LRU 缓存的应用

应用场景描述作用
操作系统内存管理用于页面置换机制，替换最久未使用的内存页。提高内存利用率，减少磁盘 I/O。
数据库缓存缓存频繁访问的数据，淘汰不常用的数据。提高查询性能，减少查询延迟。
Web 浏览器缓存缓存网页资源（如 HTML、图片、CSS 等），加快访问速度。减少重复下载，提升用户体验。
CDN 内容分发网络缓存热点内容，替换最少访问的资源。减少带宽消耗，加速内容传输。
嵌入式系统管理资源受限设备中的数据缓存。提高执行效率，优化内存占用。
数据流处理与缓存临时缓存大数据处理中间结果，腾出空间以继续处理新的数据。提升处理速度，避免重复计算。

3.2 LRU 缓存的优缺点

类别描述
优点1. 实现简单：逻辑清晰，易于实现。
2. 适应时间局部性：能很好处理最近访问的数据，提高缓存命中率。
3. 广泛适用：适用于多种缓存管理场景，如内存、数据库、浏览器等。
缺点1. 空间开销大：需额外使用链表和哈希表维护数据顺序，增加内存消耗。
2. 性能瓶颈：若未优化，查找和移动数据时间复杂度较高（O(N)）。
3. 非最佳策略：在数据访问均匀分布或随机的情况下，命中率较低，效果不佳。
4. 线程安全问题：在多线程环境下，需要额外加锁保护，影响性能。

总结：LRU 缓存在操作系统、数据库、Web 浏览器等场景中具有广泛应用，优点是实现简单、适应时间局部性，但也存在空间开销和性能瓶颈等缺点。


http://www.ppmy.cn/ops/143270.html

相关文章

mysql,创建数据库和用户授权核心语句

mysql,创建数据库和用户授权核心语句

一.库操作1.创建库create database if not exists 库名 default 字符集 default 校对规则2.删除库drop database if exists 库名3.修改库的,字符集,校对规则alter databse 库名 default 字符集 default 校对规则4.查看当前使用的库seclect databse();5.查看库show databases;…
阅读更多...
MTU MSS

MTU MSS

目录 一、MTU\MSS是什么二、为什么三次握手协商MSS 一、MTU\MSS是什么 MTU : Maximum Transmission Unit,即最大传输单元&#xff0c;表示数据链路层可以传输的最大数据包&#xff08;不包含帧首部和尾部&#xff09;。 MSS : Maximum Segment Size,即最大报文段长度。MSS是TC…
阅读更多...
最新ubuntu20.04安装docker流畅教程

最新ubuntu20.04安装docker流畅教程

最新ubuntu20.04安装docker流畅教程 使用清华镜像源 //编辑/etc/apt/sources.list # 默认注释了源码镜像以提高 apt update 速度&#xff0c;如有需要可自行取消注释 deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ focal main restricted universe multiverse # deb-sr…
阅读更多...
MySQL学习之DML操作

MySQL学习之DML操作

目录 插入 删除 修改 数据库事务 事务的特征&#xff08;ACID原则&#xff09; 原子性 一致性 隔离性 持久性 事务隔离级别 读未提交 读已提交 可重复读 序列化 脏读 虚读 幻读 插入 insert into 表名 values(); 要求插入数据的数量&#xff0c;类型要和定义…
阅读更多...
虚拟现实喷漆训练解决方案，为喷漆行业提供全新高效的培训方式

虚拟现实喷漆训练解决方案，为喷漆行业提供全新高效的培训方式

虚拟现实喷漆训练方案为喷漆操作员的培训与评估提供创新途径。此方案不仅能导入数据&#xff0c;还能定制专属的培训环境&#xff0c;从而大幅降低培训时间、材料及人力等资源消耗所带来的成本压力。 虚拟现实控制器与带触觉执行器的喷枪的组合&#xff0c;更是将操作的真实感提…
阅读更多...
修改ubuntu apt 源及apt 使用

修改ubuntu apt 源及apt 使用

视频教程:修改ubuntu apt 源和apt 使用方法_哔哩哔哩_bilibili 1 修改apt源 1.1 获取阿里云ubuntu apt 源 https://developer.aliyun.com/mirror/ubuntu?spma2c6h.13651102.0.0.3e221b11mqqLBC 1.2 修改apt 源 vim /etc/apt/sources.list deb https://mirrors.aliyun.com/ub…
阅读更多...
es build 使用配置详解：快速、可扩展的 JavaScript 打包器

es build 使用配置详解：快速、可扩展的 JavaScript 打包器

引言 es build 是一个快速、可扩展的 JavaScript 打包器和压缩器&#xff0c;它的目标是成为最快的打包器。它使用 Go 编写&#xff0c;可以在几乎瞬间内完成大多数项目的构建。在本文中&#xff0c;我们将深入了解 es build&#xff0c;并探讨其如何实现如此出色的性能。 什…
阅读更多...
Python Web 开发实战：构建 FastAPI 在线商店系统

Python Web 开发实战：构建 FastAPI 在线商店系统

Python Web 开发实战&#xff1a;构建 FastAPI 在线商店系统 目录 &#x1f6cd;️ 商品管理&#x1f6d2; 购物车与结算&#x1f4b3; 支付集成&#xff08;模拟支付&#xff09;⚙️ 系统拓展与优化建议 &#x1f6cd;️ 1. 商品管理 商品管理是任何在线商店系统的核心功能…
阅读更多...
最新文章

Copyright @ 2022~2023