10-10 LeetCode 460. LFU Cache

LFU Cache

Description

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

为最不频繁使用缓存技术设计一种数据结构，它需要支持get和put方法。

get(key) - 返回key对应的值如果key存在于缓存中，否则返回-1.

put(key, value) - 插入key, value键值对，当缓存区满了以后，需要删除最不频繁使用的key, value对。为了满足这个目的，当多个key有相同的频率时，上一次使用时间距离当前时间最长的key将被删除。

要求：
所有操作在O(1)时间复杂度内完成

知识补充

Least Frequently Used cache，如果我没记错的话，这是在学计算机组成原理时学到的一个知识。cpu对缓存区域的数据读取速度比对外存中的数据读取要快很多，所以为了提高cpu的运行速度，将一些常用的数据预先存入缓存，就可以减少数据读取的时间消耗，从而提高cpu运行效率。但是我们不可能提前知道cpu需要什么数据，缓存的大小也有限，不可能存下所有数据，所以设计一个算法来控制存入缓存中的数据是有必要的。想象一下，cpu每次取数据，缓存中都没有，都需要从外存中获取，那么这个缓存设计的就没有一点意义。所以需要提高cpu命中缓存中数据的几率。因此有很多相关的算法，可以上网搜索一下。

Solution 1:

这道题的难点就在于要求所有操作的时间复杂度都为O(1),于是我们很自然而然的就想到用哈希表这种数据结构，在python中字典就是这样的一种结构。不管数据量有多大，在字典中查询key值的时间复杂度都为O(1)。

但是光一个字典肯定是不够的，因为我们需要删除最不频繁使用的key。因此还需要一个字典来存储每一个频率下对应的key有哪些，例如频率1次的有key1,key2，频率3次的有key3...，

想到这我就开始写代码了，写完提交后才发现，这样的时间复杂度还是不能达到O(1)。因为通过key不能在O(1)时间内找到key对应的频率，所以还需要额外的一个字典来存储key以及key对应的频率。现在应该是很清晰了，我直接贴上代码，代码的大多数位置也有注释。

代码：

class LFUCache(object):

def __init__(self, capacity):
    """
    :type capacity: int
    """
    self.capacity = capacity
    self.cache = {} # 存放存入的键值对
    self.frequency = {} # 存放每个频率中出现的key，如{1：[key1,key2], 2:[key3]}
    self.cache_index = {} # 存放key对应的频率， 如{key1:1, key2:1, key3:2}

def get(self, key):
    """
    :type key: int
    :rtype: int
    """
    if key not in self.cache:
        return -1
    index = self.cache_index[key]
    self.frequency[index].remove(key)
    if self.frequency[index] == []:
        del self.frequency[index]
    if index+1 in self.frequency:
        self.frequency[index+1].append(key)
    else:
        self.frequency[index+1] = [key]
    self.cache_index[key] += 1
    return self.cache[key]
    

    

def put(self, key, value):
    """
    :type key: int
    :type value: int
    :rtype: void
    """
    if self.capacity <= 0:
        return 
    if key in self.cache:
        # 如果put一个已经存在的key,修改它的value和frequency
        self.cache[key] = value
        self.get(key)
        return
    if len(self.cache) == self.capacity:
        for times in self.frequency: # 因为字典有序，所以第一个肯定是频率最小的，删除后通过break退出循环
            key_of_cache = self.frequency[times][0] # 取出频率最小的key，并删除
            del self.cache[key_of_cache]
            del self.cache_index[key_of_cache]
            self.frequency[times] = self.frequency[times][1:]
            if self.frequency[times] == []:
                del self.frequency[times]
                break
    # 插入一个新值,频率初始值为1
    self.cache[key] = value
    if 1 in self.frequency:
        self.frequency[1].append(key)
    else:
        self.frequency[1] = [key]
    self.cache_index[key] = 1

感想

每天做这个还是耗费挺多时间的，因为水平不高，做一题就需要很长时间，然后还需要记录下来，我可能要减少发布的频率了...............