【经典算法】C/C++ 实现 LRU 算法 【已实测】_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("\n");
}

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\n", get(cache, 3));
    printCache(cache);
    printf("%d\n", get(cache, 4));
    printCache(cache);
    printf("%d\n", get(cache, 5));
    printCache(cache);
    printf("%d\n", get(cache, 6));
    printCache(cache);
    printf("%d\n", get(cache, 7));
    printCache(cache);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

该示例代码实现了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算法可以通过优化数据结构、引入时间因素、考虑缓存块大小和并发访问等方面进行改进，以更好地适应不同的应用场景。