Concise Python O(1) beats 95% using two maps.


  • 6
    X

    Two hashmaps: the freq_map keeps track of freq-> linked list of node.
    key_map tracks key->val

    PREV,NEXT,KEY,VAL,FREQ = 0,1,2,3,4
    class LFUCache(object):
    
        def __init__(self, capacity):
            self.capacity = capacity
            self.freq_map = {}
            self.key_map = {}
            self.min_freq = 1
    
        def get(self, key):
            key_map, freq_map = self.key_map, self.freq_map
            if key not in key_map:
                return -1
            else:
                val_node = key_map[key]
                val_node[PREV][NEXT],val_node[NEXT][PREV] = val_node[NEXT],val_node[PREV]
                if freq_map[self.min_freq] is freq_map[self.min_freq][NEXT]:
                    self.min_freq+=1
                freq = val_node[FREQ]
                root = freq_map.setdefault(freq+1,[])
                if not root:
                    root[:] = [root,root,None,None,freq+1]
                val_node[PREV],val_node[NEXT] = root[PREV],root
                val_node[FREQ]+=1
                root[PREV][NEXT] = root[PREV] = val_node
                return key_map[key][VAL]
    
        def set(self, key, value):
            key_map, freq_map, cap = self.key_map, self.freq_map, self.capacity
            if not cap:
                return
            if key in key_map:
                key_map[key][VAL] = value
                self.get(key)
            else:
                if len(key_map) == cap:
                    root = freq_map[self.min_freq]
                    node_evict = root[NEXT]
                    root[NEXT],node_evict[NEXT][PREV] = node_evict[NEXT], root
                    del key_map[node_evict[KEY]]
                self.min_freq = 1
                val_node = [None,None,key,value,1]
                root = freq_map.setdefault(1,[])
                if not root:
                    root[:] = [root,root,None,None,1]
                val_node[PREV],val_node[NEXT] = root[PREV],root
                root[PREV][NEXT] = root[PREV] = val_node
                key_map[key] = val_node
    

  • 1
    C

    Could you explain
    root = freq_map.setdefault(1,[])
    if not root:
    root[:] = [root,root,None,None,1]
    val_node[PREV],val_node[NEXT] = root[PREV],root

    what is root?


  • 2
    X

    @chenweisomebody
    "root" is a circular double linked list, represented by a list. At the initialization, root's PREV and NEXT point to itself.

    In python's collections.py, the LRU_Cache is implemented this way, from which I was inspired.


  • 0
    C

    @xiyayan Another question is why you need to do the copy, like
    key_map, freq_map = self.key_map, self.freq_map
    key_map, freq_map, cap = self.key_map, self.freq_map, self.capacity
    Couldn't you modify on self.map directly?


  • 1
    X

    @chenweisomebody
    That's is for performance consideration. Accessing local variable is always faster. I put it this way just out of a habit.


  • 0
    W

    Can you explain how to update the freq_map and keep track of the freq to node?
    Thank you!


  • 0
    This post is deleted!

  • 0

    @xiyayan said in Concise Python O(1) beats 95% using two maps.:

    @chenweisomebody
    "root" is a circular double linked list, represented by a list. At the initialization, root's PREV and NEXT point to itself.

    In python's collections.py, the LRU_Cache is implemented this way, from which I was inspired.

    +1 for referencing python source code :) the correct link is here


  • 0
    S

    Same idea except, but using "deque" (doubly linked list by python) to maintain LRU queue of frequencies -

    class LFUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.capacity   = capacity
            self.kvstore    = dict()
            self.freqstore  = collections.defaultdict(collections.deque)
            self.used       = 0
            self.minfreq    = 1
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            if key not in self.kvstore:
                return -1
            
            (value,freq) = self.kvstore[key]
            self.freqstore[freq].remove(key)
            if not self.freqstore[freq]:
                del self.freqstore[freq]
                if self.minfreq == freq:
                    self.minfreq = freq + 1
            self.kvstore[key] = (value,freq+1)
            self.freqstore[freq+1].append(key)
            return value
            
        def put(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            if self.capacity:
                if key not in self.kvstore:
                    while self.used >= self.capacity:
                        evicting_key = self.freqstore[self.minfreq].popleft()
                        if not self.freqstore[self.minfreq]:
                            del self.freqstore[self.minfreq]
                        del self.kvstore[evicting_key]
                        self.used -= 1
                    self.used += 1
                    self.kvstore[key] = (value,1)
                    self.freqstore[1].append(key)
                    self.minfreq = 1
                else:
                    oldvalue, freq = self.kvstore[key]
                    self.freqstore[freq].remove(key)
                    if not self.freqstore[freq]:
                        if freq == self.minfreq:
                            self.minfreq = freq + 1
                        del self.freqstore[freq]
                    self.kvstore[key] = (value,freq+1)
                    self.freqstore[freq+1].append(key)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.