題目

前面提到過LFU，這裡就不重複一次啦。

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.
Follow up:
Could you do both operations in O(1) time complexity?

解法

Data structures

unordered_map<int, list<int>> freq_list; 
unordered_map<int, tuple<int, int, list<int>::iterator>> cache; 
int min_freq;
int cache_cap;

• 因為要求O(1)，所以最直接聯想到的就是Hash table，那C++ STL中的unordered_map底層就是Hash table
• freq_list:考慮LFU需要紀錄在cache中各key-value pair的使用頻率，這裡用一個hash table，索引值為使用頻率，能以O(1)找到對應頻率的linked list。那為什麼要這樣做?
  • 使用linked list是要儲存進去才分配空間，比較節省。
  • 每個使用頻率都建立一個linked list，在淘汰時，就去淘汰最低頻率的list中的key-value pair即可。
  • 此外要更新使用頻率，就將其移至對應頻率的linked list即可。
• cache: 為達到更新使用頻率，不用遍歷linked list去找key(這樣就要O(n)，不符題目)，我們儲存key-value pair的hash table要額外儲存一些資訊。
  • 另一個hash table就是以key為索引，那儲存的東西為一個tuple。
  • tuple中儲存3個東西，分別是value、使用頻率、儲存在對應頻率中list的那個key的iterator。
  • 這樣就等於直接有了那個node，可以直接刪掉，之後使用頻率+1，就能用快速對應到另一個list，然後將key，push進去，完成更新使用頻率的動作。
• min_freq: 則紀錄當前在cache裡所有的key-value pairs中的最低使用頻率是多少
  • 要淘汰最低頻率的key-value pair就靠他啦。
• cache_cap則是記cache的容量。

Functions

1. constructor

LFUCache(int capacity) {
    cache_cap = capacity;
}

• 因為是class，建構式很簡單，就是記容量。

2. put

void put(int key, int value) {
    if (cache_cap <= 0)
        return;

    if (cache.count(key)) {
        update_freq(key);
        std::get<0>(cache[key]) = value;
        return;
    }

    if (cache.size() == cache_cap) {
        cache.erase(freq_list[min_freq].back());
        freq_list[min_freq].pop_back();
    }

    min_freq = 1;
    freq_list[min_freq].push_front(key);
    cache[key] = make_tuple( value, min_freq, freq_list[min_freq].begin() ); 
}

• 第一個if，leetcode的極端情況，測資capacity會給0，雖然我不知道為什麼要給0，但就處理一下。
• 第二個if，看key是否在Cache中，如果存在，就只需要更新使用頻率與value便能return，不用考慮淘汰誰的問題。
  • 使用unordered_map中提供的count
    • count:給一個key，搜索鍵為key的元素，並返回元素數
    • unordered_map規定key不能重複，所以只會返回1或0。1代表存在，0就代表不存在。
  • 存在則更新使用頻率與value
    • update_freq函式後面會提到。
    • std::get能用於tuple，而cache[key]索引到的是一個tuple
      • std::get<0>表示返回tuple第0個值的參考(reference)。
      • std::get<1>表示返回tuple第1個值的參考(reference)。類推
      • 因為返回的是參考，所以直接修改，就相當於修改裡面的值囉。
• 第三個if，則是cache滿了，需要淘汰人
  • 那我們就直接用min_freq去索引到對應的list，list是儲存屬於這個頻率的key，我們挑在list最後面的key
  • 拿這個key去刪除在cache中的key-value pair
  • 再刪掉在list裡的那個key。
• 接著該做的都做了。就來put新的key-value pair吧
  • min_freq自然就變1，因為有新的key-value第一次使用。
  • 將key插入到頻率1的list中。
  • 建構tuple，儲存需要的資訊，並插入到hash table中。

3. get

int get(int key) {
    if (cache.count(key) == 0)
        return -1;

    update_freq(key);

    return std::get<0>(cache[key]);
}

• get就沒什麼特別的，就是看key有沒有存在，不存在返回-1，存在則更新使用頻率，並返回value。

4. update_freq

void update_freq(int key) {
    int& freq = std::get<1>(cache[key]);
    list<int>::iterator& itr = std::get<2>(cache[key]);

    freq_list[freq].erase(itr);
    if (freq_list[freq].empty() && min_freq == freq)
        min_freq++;

    freq = freq + 1;
    itr = freq_list[freq].insert(freq_list[freq].begin(), key);
}

• 要將key更新到另外一個頻率的list
• 首先取出tuple中後面2個額外儲存的資訊: 使用頻率、儲存在對應頻率中list的那個key的iterator。
  • 這裡是取其記憶體位址哦，所以修改就直接改tuple裡的值了。
• 有key的iterator那就能從list中直接刪掉key，不用遍歷。
• 接著判斷一下如果此頻率(freq)的list已空沒儲存東西且又與最低使用頻率(min_freq)相同，意味著min_freq要+1。因為此頻率的key-value pair沒了~應該很好懂。
• 接著使用頻率(freq)+1
• 在對應頻率的list插入key，並將其新的iterator儲存進tuple。

完整Code

class LFUCache {
public:
    unordered_map<int, list<int>> freq_list;
    unordered_map<int, tuple<int, int, list<int>::iterator>> cache;
    int min_freq;
    int cache_cap;
    
    LFUCache(int capacity) {
        cache_cap = capacity;
    }
    
    void update_freq(int key) {
        int& freq = std::get<1>(cache[key]);
        list<int>::iterator& itr = std::get<2>(cache[key]);
        
        freq_list[freq].erase(itr);
        if (freq_list[freq].empty() && min_freq == freq)
            min_freq++;
        
        freq = freq + 1;
        itr = freq_list[freq].insert(freq_list[freq].begin(), key);
    }
    
    int get(int key) {
        if (cache.count(key) == 0)
            return -1;
        
        update_freq(key);
        
        return std::get<0>(cache[key]);
    }
    
    void put(int key, int value) {
        if (cache_cap <= 0)
            return;
        
        if (cache.count(key)) {
            update_freq(key);
            std::get<0>(cache[key]) = value;
            return;
        }
        
        if (cache.size() == cache_cap) {
            cache.erase(freq_list[min_freq].back());
            freq_list[min_freq].pop_back();
        }
    
        min_freq = 1;
        freq_list[min_freq].push_front(key);
        cache[key] = make_tuple( value, min_freq, freq_list[min_freq].begin() ); 
    }
};