lfu算法c语言

以下是 C 语言实现的 LFU 算法示例：

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

#define CACHE_SIZE 5

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

typedef struct {
    Node *head;
    Node *tail;
} List;

typedef struct {
    int size;
    int capacity;
    List *freq_list;
    Node **cache;
} LFUCache;

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

List *create_list() {
    List *list = (List *)malloc(sizeof(List));
    list->head = NULL;
    list->tail = NULL;
    return list;
}

LFUCache *create_cache(int capacity) {
    LFUCache *cache = (LFUCache *)malloc(sizeof(LFUCache));
    cache->size = 0;
    cache->capacity = capacity;
    cache->freq_list = (List *)malloc(sizeof(List) * (CACHE_SIZE + 1));
    cache->cache = (Node **)calloc(capacity, sizeof(Node *));
    return cache;
}

void delete_node(LFUCache *cache, Node *node) {
    List *list = &cache->freq_list[node->freq];
    if (node->prev == NULL) {
        list->head = node->next;
    } else {
        node->prev->next = node->next;
    }
    if (node->next == NULL) {
        list->tail = node->prev;
    } else {
        node->next->prev = node->prev;
    }
    cache->size--;
    free(node);
}

void insert_node(LFUCache *cache, Node *node) {
    List *list = &cache->freq_list[node->freq];
    if (list->head == NULL) {
        list->head = node;
        list->tail = node;
    } else {
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    cache->size++;
}

void update_node(LFUCache *cache, Node *node) {
    delete_node(cache, node);
    node->freq++;
    insert_node(cache, node);
}

void remove_least_frequent_node(LFUCache *cache) {
    int i = 1;
    List *list;
    while (i <= CACHE_SIZE && (list = &cache->freq_list[i])->head == NULL) {
        i++;
    }
    if (i > CACHE_SIZE) {
        return;
    }
    Node *node = list->tail;
    delete_node(cache, node);
    cache->cache[node->key] = NULL;
}

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

void put(LFUCache *cache, int key, int value) {
    if (cache->capacity == 0) {
        return;
    }
    Node *node = cache->cache[key];
    if (node == NULL) {
        if (cache->size == cache->capacity) {
            remove_least_frequent_node(cache);
        }
        node = create_node(key, value);
        cache->cache[key] = node;
        insert_node(cache, node);
    } else {
        node->value = value;
        update_node(cache, node);
    }
}

int main() {
    LFUCache *cache = create_cache(2);
    put(cache, 1, 1);
    put(cache, 2, 2);
    printf("%d\n", get(cache, 1)); // 1
    put(cache, 3, 3);
    printf("%d\n", get(cache, 2)); // -1
    printf("%d\n", get(cache, 3)); // 3
    put(cache, 4, 4);
    printf("%d\n", get(cache, 1)); // -1
    printf("%d\n", get(cache, 3)); // 3
    printf("%d\n", get(cache, 4)); // 4
    return 0;
}

该示例中，LFUCache 结构体表示 LFU 缓存，它包含了缓存的大小、容量、频率列表和缓存数组。Node 结构体表示缓存中的节点，它包含了键、值、频率以及前驱和后继节点。List 结构体表示频率列表，它包含了头节点和尾节点。create_node() 函数用于创建节点，create_list() 函数用于创建列表，create_cache() 函数用于创建缓存。delete_node() 函数用于删除节点，insert_node() 函数用于插入节点，update_node() 函数用于更新节点，remove_least_frequent_node() 函数用于删除最不经常使用的节点。get() 函数用于获取缓存中指定键的值，put() 函数用于向缓存中插入指定键值对。

示例中的 put() 函数实现比较复杂，需要分别处理插入新节点和更新已有节点的情况，还需要删除最不经常使用的节点以腾出空间。因此，put() 函数的时间复杂度为 O(log n)，其中 n 为缓存的容量。get() 函数的实现相对简单，只需要更新节点的频率即可，因此时间复杂度为 O(1)。