您现在的位置是:首页 >其他 >【经典算法】C/C++ 实现 LRU 算法 【已实测】网站首页其他

【经典算法】C/C++ 实现 LRU 算法 【已实测】

Michael_Good 2024-06-11 18:01:02
简介【经典算法】C/C++ 实现 LRU 算法 【已实测】

LRU 适用场景

  1. Web服务器缓存:Web服务器通常会缓存一些静态资源,如图片、CSS、JS等,以减少网络传输时间和服务器负载。LRU算法可以用于缓存淘汰,保留最近访问的资源,提高缓存命中率。
  2. 数据库缓存:数据库通常会缓存一些热点数据,如热门商品、用户信息等,以减少数据库查询时间和提高系统性能。LRU算法可以用于缓存淘汰,保留最近访问的数据,提高缓存命中率。
  3. 操作系统缓存:操作系统通常会缓存一些常用的文件和数据块,以减少磁盘读写时间和提高系统性能。LRU算法可以用于缓存淘汰,保留最近访问的文件和数据块,提高缓存命中率。

LRU 具体实现

#include <stdio.h>
#include <stdlib.h>

#define CACHE_SIZE 5

typedef struct Node {
    int key;
    int value;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct LRUCache {
    int size;
    int capacity;
    Node* head;
    Node* tail;
    Node** cache;
} LRUCache;

Node* createNode(int key, int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->value = value;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

void addNodeToHead(LRUCache* cache, Node* node) {
    node->next = cache->head;
    node->prev = NULL;
    if (cache->head != NULL) {
        cache->head->prev = node;
    }
    cache->head = node;
    if (cache->tail == NULL) {
        cache->tail = node;
    }
}

void removeNode(LRUCache* cache, Node* node) {
    if (node->prev != NULL) {
        node->prev->next = node->next;
    } else {
        cache->head = node->next;
    }
    if (node->next != NULL) {
        node->next->prev = node->prev;
    } else {
        cache->tail = node->prev;
    }
}

void moveToHead(LRUCache* cache, Node* node) {
    removeNode(cache, node);
    addNodeToHead(cache, node);
}

Node* removeTail(LRUCache* cache) {
    Node* node = cache->tail;
    removeNode(cache, node);
    return node;
}

LRUCache* createLRUCache(int capacity) {
    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));
    cache->size = 0;
    cache->capacity = capacity;
    cache->head = NULL;
    cache->tail = NULL;
    cache->cache = (Node**)malloc(sizeof(Node*) * capacity);
    for (int i = 0; i < capacity; i++) {
        cache->cache[i] = NULL;
    }
    return cache;
}

void put(LRUCache* cache, int key, int value) {
    Node* node = cache->cache[key % cache->capacity];
    if (node == NULL) {
        if (cache->size > cache->capacity) {
            Node* tail = removeTail(cache);
            cache->cache[tail->key % cache->capacity] = NULL;
            free(tail);
            cache->size--;
        }
        
        node = createNode(key, value);
        cache->cache[key % cache->capacity] = node;
        addNodeToHead(cache, node);
        cache->size++;   
    } else {
        node->value = value;
        moveToHead(cache, node);
    }
}

int get(LRUCache* cache, int key) {
    Node* node = cache->cache[key % cache->capacity];
    if (node == NULL) {
        return -1;
    }
    moveToHead(cache, node);
    return node->value;
}

void printCache(LRUCache* cache) {
    Node* node = cache->head;
    while (node != NULL) {
        printf("(%d, %d) ", node->key, node->value);
        node = node->next;
    }
    printf("
");
}

int main() {
    LRUCache* cache = createLRUCache(CACHE_SIZE);
    put(cache, 1, 1);
    put(cache, 2, 2);
    put(cache, 3, 3);
    put(cache, 4, 4);
    put(cache, 5, 5);
    printCache(cache);
    put(cache, 6, 6);
    printCache(cache);
    printf("%d
", get(cache, 3));
    printCache(cache);
    printf("%d
", get(cache, 4));
    printCache(cache);
    printf("%d
", get(cache, 5));
    printCache(cache);
    printf("%d
", get(cache, 6));
    printCache(cache);
    printf("%d
", get(cache, 7));
    printCache(cache);
    return 0;
}

该示例代码实现了LRU缓存淘汰算法,使用双向链表和哈希表实现。
其中,LRUCache结构体表示LRU缓存,Node结构体表示缓存中的节点。
createNode函数用于创建节点,addNodeToHead函数用于将节点添加到链表头部,removeNode函数用于删除节点,moveToHead函数用于将节点移动到链表头部,removeTail函数用于删除链表尾部的节点,createLRUCache函数用于创建LRU缓存,put函数用于向缓存中添加数据,get函数用于从缓存中获取数据,printCache函数用于打印缓存中的数据。在main函数中,演示了LRU缓存的使用过程。

LRU 优劣

LRU(Least Recently Used)算法是一种常见的缓存淘汰算法,其核心思想是淘汰最近最少使用的缓存块。其优点包括:

  1. 命中率高:LRU算法能够有效地利用缓存空间,提高缓存命中率,减少缓存未命中的情况,从而提高系统性能。

  2. 实现简单:LRU算法的实现相对简单,只需要维护一个链表和一个哈希表即可。

  3. 适用性广:LRU算法适用于各种类型的缓存,包括CPU缓存、磁盘缓存、数据库缓存等。

然而,LRU算法也存在一些缺点:

  1. 时间复杂度高:LRU算法需要维护一个链表和一个哈希表,每次访问缓存块都需要更新链表和哈希表,因此时间复杂度较高。

  2. 空间复杂度高:LRU算法需要维护一个链表和一个哈希表,占用的空间较大。

  3. 不适用于动态缓存:如果缓存大小不固定或者缓存访问模式不稳定,LRU算法可能会导致缓存命中率下降,从而影响系统性能。

综上所述,LRU算法是一种常见的缓存淘汰算法,具有高命中率和简单实现的优点,但也存在时间复杂度高、空间复杂度高和不适用于动态缓存等缺点。在实际应用中,需要根据具体情况选择合适的缓存淘汰算法。

LRU 改进

虽然LRU算法在缓存淘汰方面表现良好,但是在某些情况下,它可能会出现一些问题,需要进行改进。以下是一些可能的改进方向:

  1. 优化数据结构:LRU算法需要维护一个链表和一个哈希表,占用的空间较大,时间复杂度也较高。可以考虑使用其他数据结构,如跳表、红黑树等,来优化LRU算法的空间和时间复杂度。

  2. 引入时间因素:LRU算法只考虑了最近使用的情况,没有考虑到访问时间的因素。可以考虑引入时间因素,将最近使用和访问时间结合起来,来更好地决定缓存块的淘汰顺序。

  3. 考虑缓存块大小:LRU算法只考虑了缓存块的访问情况,没有考虑到缓存块的大小。可以考虑引入缓存块大小的因素,来更好地决定缓存块的淘汰顺序。

  4. 考虑并发访问:在并发访问的情况下,LRU算法可能会出现一些问题,如竞争条件、死锁等。可以考虑使用并发数据结构或者锁来解决这些问题。

综上所述,LRU算法可以通过优化数据结构、引入时间因素、考虑缓存块大小和并发访问等方面进行改进,以更好地适应不同的应用场景。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。