用哈希表和和双向链表的代码模板实现LFU

字数统计: 2.3k字 | 阅读时长: 11分

2022-11-26

摘要: 实现 LFU

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 LRU：维护最近访问/插入的元素中，我们基于 C++ STL 以及 Python OrderedDict 实现了 LRU 的插入和查询。在文章 LFU：维护最频繁访问的元素中我们基于 C++ STL 实现了 LFU 的插入和查询。本文我们基于 CloseHashTable 和 DoubleCircleList 实现 LFU。

在文章 OrderedDict：维护插入顺序的有序字典中，我们已经基于 CloseHashTable 和 DoubleCircleList 实现了 OrderedDict 的增删改查，在实现 LRU 和 LFU 的时候也可以借鉴，其中 LRU 比较简单，只需要在 OrderedDict 基础上做少量修改。参考文章用哈希表和和双向链表的代码模板实现LRU。

LFU 在 LRU 基础上的变化

460. LFU 缓存

LFU 在 LRU 基础上的变化：

put 中如果达到 capacity 需要删除访问次数最低的节点，当访问次数最低的节点有多个时，删最早访问的那个。
get 时，如果有值，则需要将访问次数加 1 并将对应的链表节点调度到表头。

数据结构设计

(1) 桶

维护频率顺序可以用一个桶结构，桶按照频率大小的顺序排列。用动态数组维护，如果频率非常稀疏可以考虑用链表维护。

这里桶用数组维护。用链表维护频率的桶参考全O(1)的数据结构：哈希表计数，支持查询计数最大与最小的键。

桶的数据结构如下，这是一个动态数组，空间提前算好，不触发扩容：

1	DoubleCircleList *buckets;

(2) 链表

链表的容量用一个默认的很大的值。即不带容量限制和扩容。

链表的数据类型为自定义类型，其中持有 key 和 cnt，key 是哈希表的键，cnt 是该 key 的访问次数，也是桶的下标。

struct DLType
{
    int key;
    int cnt;
    DLType(int key=-1, int cnt=-1):key(key),cnt(cnt){}
    bool operator==(const DLType& v) const
    {
        return v.cnt == cnt && key == v.key;
    }
    bool operator!=(const DLType& v) const
    {
        return !(*this == v);
    }
    friend ostream& operator<< (ostream& os, const DLType& v);
};
ostream& operator<< (ostream& os, const DLType& v)
{
    cout << "(" << v.key << " " << v.cnt << ") "; 
    return os;
}
const DLType DLTypeNULL(-1, -1);
const int MAX_LEN = 2e5;

(3) 哈希表

哈希表用比哈希表模板，容量提前计算好，不带扩容和重哈希。

哈希表的键为 int，值为自定义类型 ValueType，持有 int 类型的值和链表节点的指针。

const int INF = 1e9;
typedef int HashType;
struct ValueType
{
    int value;
    DLNode *list_node;
    ValueType(int v=-1, DLNode *node=nullptr):value(v),list_node(node){}
    bool operator==(const ValueType& v) const
    {
        return value == v.value && list_node == v.list_node;
    }
    bool operator!=(const ValueType& v) const
    {
        return !(*this == v);
    }
};
ValueType VALUENULL(-1, nullptr);

带频率顺序和访问顺序的字典 (LFU) 的整体数据结构：

CloseHashTable mapping;
// 如果频率稀疏的话，可以改为链表维护桶
DoubleCircleList *buckets;
int buckets_capacity;
int size;
int capacity;

代码 (C++，模板)

LFUCache 为带频率顺序和访问顺序的字典。

参数设置如下：

1
2
3

MAX_LEN = 2e5 // 链表容量
sizetable = 99991 // 哈希表容量
buckets_cap = 1e3 // 桶的动态数组容量

运行时间与用 STL 的代码基本一样，都是 450 ms。

struct DLType
{
    int key;
    int cnt;
    DLType(int key=-1, int cnt=-1):key(key),cnt(cnt){}
    bool operator==(const DLType& v) const
    {
        return v.cnt == cnt && key == v.key;
    }
    bool operator!=(const DLType& v) const
    {
        return !(*this == v);
    }
    friend ostream& operator<< (ostream& os, const DLType& v);
};
ostream& operator<< (ostream& os, const DLType& v)
{
    cout << "(" << v.key << " " << v.cnt << ") ";
    return os;
}
const DLType DLTypeNULL(-1, -1);
const int MAX_LEN = 2e5;

struct DLNode
{
    DLType val;
    DLNode *next;
    DLNode *prev;
    DLNode(DLType x) : val(x), next(nullptr), prev(nullptr) {}
};

class DoubleCircleList
{
private:
    // head 一直指向 dummy
    // tail 在空表时指向 dummy，否则指向 head 的前一个节点
    DLNode *head, *tail;
    int length;
    int capacity;

public:
    DoubleCircleList(int N=MAX_LEN)
    {
        head = new DLNode(DLTypeNULL);
        head -> next = head;
        head -> prev = head;
        tail = head;
        length = 0;
        capacity = N;
    }

    bool removeHead()
    {
        if(isEmpty())
            return false;
        remove(get_head());
        return true;
    }

    bool removeTail()
    {
        if(isEmpty())
            return false;
        remove(get_tail());
        return true;
    }

    DLType getHead() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_head() -> val;
    }

    DLType getTail() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_tail() -> val;
    }

    DLNode* insertHead(DLType val)
    {
        if(isFull())
            return nullptr;
        return insert(head, val);
    }

    bool insertTail(DLType val)
    {
        if(isFull())
            return false;
        insert(tail, val);
        return true;
    }

    DLNode* insert(DLNode *pos, DLType val)
    {
        if(!pos || isFull())
            return nullptr;
        DLNode *cur = new DLNode(val);
        cur -> next = pos -> next;
        cur -> prev = pos;
        pos -> next -> prev = cur;
        pos -> next = cur;
        if(tail == pos)
            tail = cur;
        ++length;
        return cur;
    }

    DLType get(DLNode *pos) const
    {
        if(!pos || is_dummy(pos))
            return DLTypeNULL;
        return pos -> val;
    }

    DLNode* remove(DLNode *pos)
    {
        if(!pos || is_dummy(pos) || isEmpty())
            return nullptr;
        if(tail == pos)
            tail = tail -> prev;
        --length;
        pos -> prev -> next = pos -> next;
        pos -> next -> prev = pos -> prev;
        DLNode *result = pos -> next;
        delete pos;
        pos = nullptr;
        if(isEmpty())
            return nullptr;
        if(is_dummy(result))
            result = result -> next;
        return result;
    }

    bool change(DLNode* pos, DLType val)
    {
        if(!pos || is_dummy(pos))
            return false;
        pos -> val = val;
        return true;
    }

    DLNode* get_next(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_tail(pos))
            return get_head();
        return pos -> next;
    }

    DLNode* get_prev(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_head(pos))
            return get_tail();
        return pos -> prev;
    }

    bool is_dummy(DLNode *pos) const
    {
        return pos == head;
    }

    bool is_head(DLNode *pos) const
    {
        return (!isEmpty() && pos == head -> next);
    }

    bool is_tail(DLNode *pos) const
    {
        return (!isEmpty() && pos == tail);
    }

    DLNode* get_tail() const
    {
        if(isEmpty())
            return nullptr;
        return tail;
    }

    DLNode* get_head() const
    {
        if(isEmpty())
            return nullptr;
        return head -> next;
    }


    bool isEmpty() const
    {
        return head == tail;
    }

    int size() const
    {
        return length;
    }

    bool isFull() const
    {
        return length >= capacity;
    }

    void traverse() const
    {
        auto iter = head -> next;
        while(iter != head)
        {
            cout << iter -> val << " ";
            iter = iter -> next;
        }
        cout << endl;
    }
};

const int INF = 1e9;
typedef int HashType;
struct ValueType
{
    int value;
    DLNode *list_node;
    ValueType(int v=-1, DLNode *node=nullptr):value(v),list_node(node){}
    bool operator==(const ValueType& v) const
    {
        return value == v.value && list_node == v.list_node;
    }
    bool operator!=(const ValueType& v) const
    {
        return !(*this == v);
    }
};
ValueType VALUENULL(-1, nullptr);

class CloseHashTable
{
private:
    struct Node
    {
        HashType data;
        ValueType item;
        int state;
        // 0: Empty  -1: deleted
        // >0: cnt / active
        Node()
        {
            state = 0;
        }
    };

    Node *arraytable;
    int sizetable;
    int (*key)(const HashType& x); // 将 key 变成一个整数，如果 key 本身是整数直接返回
    const double A = 0.6180339887;

    static int defaultKey(const int &k)
    {
        return k;
    }

    int hash1(const HashType& x) const
    {
        if(key(x) < 0)
            return key(x) % sizetable;
        return (key(x) + INF) % sizetable;
    }

    int hash2(const HashType& x) const
    {
        double d;
        if(key(x) < 0)
            d = (key(x) + INF) * A;
        else
            d = (key(x)) * A;
        return (int)(sizetable * (d - (int)d));
    }

public:
    CloseHashTable(int length=99991, int (*f)(const HashType &x)=defaultKey)
    {
        sizetable = length;
        arraytable = new Node[sizetable];
        key = f;
    }

    ~CloseHashTable()
    {
        delete [] arraytable;
    }

    ValueType& findx(const HashType& x) const;
    bool insertx(const HashType& x, const ValueType& v);
    bool removex(const HashType& x);
    void rehash();
};

ValueType& CloseHashTable::findx(const HashType &x) const
{
    int initPos = hash2(x);
    int pos = initPos;

    do
    {
        if(arraytable[pos].state == 0)
            return VALUENULL;
        if(arraytable[pos].state > 0 && key(arraytable[pos].data) == key(x))
            return arraytable[pos].item;
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return VALUENULL;
}

bool CloseHashTable::insertx(const HashType& x, const ValueType& v)
{
    int initPos = hash2(x);
    int pos = initPos;

    do{
        if(arraytable[pos].state <= 0)
        {
            arraytable[pos].data = x;
            arraytable[pos].item = v;
            arraytable[pos].state = 1;
            return true;
        }
        else if(arraytable[pos].state > 0 && arraytable[pos].data == x)
        {
            // 有重映射将用新值覆盖 item 改为将新值插入 items
            arraytable[pos].item = v;
            return true;
        }
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return false;
}

bool CloseHashTable::removex(const HashType &x)
{
    int initPos = hash2(x);
    int pos = initPos;

    do
    {
        if(arraytable[pos].state == 0)
            return false;
        if(arraytable[pos].state > 0 && arraytable[pos].data == x)
        {
            // 有重映射改为将节点下的所有 item 删掉，将 arraytable[pos].state 改为 -1 后返回
            arraytable[pos].state = -1;
            return true;
        }
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return false;
}

void CloseHashTable::rehash()
{
    Node *tmp = arraytable;
    arraytable = new Node[sizetable * 2];

    for(int i = 0; i < sizetable; ++i)
        if(tmp[i].state > 0)
            insertx(tmp[i].data, tmp[i].item);

    sizetable *= 2;
    delete [] tmp;
}

class LFUCache
{
public:
    LFUCache(int capacity, int buckets_cap=1e3):capacity(capacity)
    {
        CloseHashTable mapping;
        buckets_capacity = buckets_cap;
        buckets = new DoubleCircleList[buckets_capacity];
        size = 0;
    }

    ~LFUCache()
    {
        delete [] buckets;
    }

    void put(int key, int value) {
        if(capacity == 0)
            return;
        ValueType &v = mapping.findx(key);
        if(v != VALUENULL)
        {
            v.value = value;
            DLNode *node = v.list_node;
            int cnt = (node -> val).cnt;
            buckets[cnt].remove(node);
            DLNode *new_node = buckets[cnt + 1].insertHead(DLType(key, cnt + 1));
            v.list_node = new_node;
            return;
        }
        if(capacity == size)
            remove_bottom();
        // 省略了扩容
        // 如果用链表维护桶，可以考虑扩容
        DLNode *node = buckets[0].insertHead(DLType(key, 0));
        mapping.insertx(key, ValueType(value, node));
        ++size;
    }

    int get(int key)
    {
        ValueType &v = mapping.findx(key);
        if(v == VALUENULL)
            return -1;
        else
        {
            int ans = v.value;
            DLNode *node = v.list_node;
            int cnt = (node -> val).cnt;
            buckets[cnt].remove(node);
            DLNode *new_node = buckets[cnt + 1].insertHead(DLType(key, cnt + 1));
            v.list_node = new_node;
            return ans;
        }
    }

    bool remove(int key)
    {
        ValueType v = mapping.findx(key);
        if(v != VALUENULL)
        {
            int cnt = v.list_node -> val.cnt;
            buckets[cnt].remove(v.list_node);
            mapping.removex(key);
            --size;
            return true;
        }
        else
            return false;
    }

    bool remove_bottom()
    {
        // 删掉访问次数最少且上次访问最早的 key
        if(size == 0)
            return false;

        int cnt = 0;
        while(cnt < buckets_capacity && buckets[cnt].isEmpty())
            ++cnt;
        int key = buckets[cnt].getTail().key;
        DLNode *node = buckets[cnt].get_tail();
        buckets[cnt].remove(node);
        mapping.removex(key);
        --size;
        return true;
    }

protected:
    CloseHashTable mapping;
    // 如果频率稀疏的话，可以改为链表维护桶
    DoubleCircleList *buckets;
    int buckets_capacity;
    int size;
    int capacity;
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法数据结构