LRU-K c语言

### LRU-K 缓存算法概述 LRU-K 是一种扩展的缓存淘汰策略，其中 K 表示在判断一个对象是否为最近使用时考虑的历史访问次数。相比于传统的 LRU（K=1），LRU-K 能够更好地处理局部性和随机访问模式。具体来说，LRU-K 记录每个缓存项在过去 K 次访问中的时间戳，并根据这些历史信息决定淘汰顺序。 以下是基于 C 语言实现的一个简化版本的 LRU-K 缓存算法： --- ### 数据结构定义 为了支持高效的插入、删除和查询操作，可以结合哈希表和双向链表来构建缓存系统。以下是核心数据结构的设计[^3]： ```c #include <stdio.h> #include <stdlib.h> #define CACHE_SIZE 5 #define MAX_KEY_LEN 20 typedef struct CacheNode { char key[MAX_KEY_LEN]; int value; int access_count; // 当前节点的访问计数 (用于 LRUK 的 K 值) double last_access_time; // 上次访问的时间戳 struct CacheNode* prev; struct CacheNode* next; } CacheNode; typedef struct LRUCache { CacheNode* head; CacheNode* tail; size_t count; } LRUCache; // 辅助函数声明 CacheNode* create_node(const char* key, int value); void add_to_head(LRUCache* cache, CacheNode* node); void remove_node(CacheNode* node); void move_to_head(LRUCache* cache, CacheNode* node); int get_cache_value(LRUCache* cache, const char* key); void set_cache_value(LRUCache* cache, const char* key, int value); ``` --- ### 核心逻辑实现 #### 创建新节点 创建一个新的缓存节点并初始化其属性： ```c CacheNode* create_node(const char* key, int value) { CacheNode* new_node = malloc(sizeof(CacheNode)); strncpy(new_node->key, key, MAX_KEY_LEN - 1); new_node->value = value; new_node->access_count = 1; // 初始化访问计数为 1 new_node->last_access_time = time(NULL); // 设置当前时间为初始时间戳 new_node->prev = NULL; new_node->next = NULL; return new_node; } ``` #### 将节点添加到头部 将指定节点移动到链表头位置，表示它是最新访问过的节点： ```c void add_to_head(LRUCache* cache, CacheNode* node) { if (!cache->head) { // 如果链表为空，则直接设置头尾指针 cache->head = cache->tail = node; } else { node->next = cache->head; cache->head->prev = node; cache->head = node; } } ``` #### 删除节点 从链表中移除某个节点： ```c void remove_node(CacheNode* node) { if (node->prev) { node->prev->next = node->next; } if (node->next) { node->next->prev = node->prev; } if (node == node->list->head) { node->list->head = node->next; } if (node == node->list->tail) { node->list->tail = node->prev; } } ``` #### 移动节点到头部 更新已有节点的位置至链表头部： ```c void move_to_head(LRUCache* cache, CacheNode* node) { if (cache->head != node) { remove_node(node); add_to_head(cache, node); } } ``` #### 获取缓存值 尝试从缓存中获取指定键对应的值，如果命中则调整该节点的位置；如果没有找到，则返回 -1： ```c int get_cache_value(LRUCache* cache, const char* key) { CacheNode* current = cache->head; while (current) { if (strcmp(current->key, key) == 0) { move_to_head(cache, current); current->access_count++; // 更新访问计数 current->last_access_time = time(NULL); // 更新最后访问时间 return current->value; } current = current->next; } return -1; // 键不存在于缓存中 } ``` #### 插入或替换缓存值 向缓存中插入新的键值对，或者覆盖已有的键值对。如果缓存容量达到上限，则按照 LRU-K 策略淘汰最不常使用的节点： ```c void set_cache_value(LRUCache* cache, const char* key, int value) { CacheNode* existing_node = cache->head; while (existing_node && strcmp(existing_node->key, key) != 0) { existing_node = existing_node->next; } if (existing_node) { // 已存在此键，更新其值 existing_node->value = value; move_to_head(cache, existing_node); existing_node->access_count++; existing_node->last_access_time = time(NULL); } else { // 新增键值对 if (cache->count >= CACHE_SIZE) { // 容量不足，需淘汰旧节点 CacheNode* lru_node = cache->tail; while (lru_node && lru_node->access_count > 1) { // 找到满足条件的 LRU-K 节点 lru_node = lru_node->prev; } if (lru_node) { remove_node(lru_node); free(lru_node); cache->count--; } } CacheNode* new_node = create_node(key, value); add_to_head(cache, new_node); cache->count++; } } ``` --- ### 总结 上述代码实现了基本的 LRU-K 缓存机制，通过维护 `access_count` 和 `last_access_time` 来跟踪每个缓存项的访问频率及时效性。这种设计能够有效应对复杂的访问模式，同时保持较高的运行效率[^4]。 ---