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


  • 4
    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


Log in to reply
 

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