TLE how to optimize following python codes?


  • 0
    C

    Thanks

    """
    ["LFUCache","put","put","get","put","get","get","put","get","get","get"]
    [[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
    ["LFUCache","put","get"]
    [[0],[0,0],[0]]
    ["LFUCache","put","put","put","put","get","get","get","get","put","get","get","get","get","get"]
    [[3],[1,1],[2,2],[3,3],[4,4],[4],[3],[2],[1],[5,5],[1],[2],[3],[4],[5]]
    """
    
    class Node(object):
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.fre = 0
            self.pre = None
            self.nxt = None
            
        def myprint(self):
            p = self
            ans = []
            while p:
                ans.append( (p.key, p.val, p.fre) )
                p = p.nxt
            print ans
            
    class LFUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.cap = capacity
            self.mp = {}
            self.head = Node(-1, -1)
            self.tail = Node(-1, -1)
            
            self.head.nxt = self.tail
            self.tail.pre = self.head
            self.head.fre = -1-sys.maxint
            self.tail.fre = sys.maxint
            #self.head.myprint()
    
        def get(self, key):
            """
            :rtype: int
            """
            if not key in self.mp:
                return -1
                
            cur = self.mp.get(key)
            self.updateFrequency(cur)
            #self.head.myprint()
            return cur.val
            
        def updateFrequency(self, cur):
            pre = cur.pre
            nxt = cur.nxt
            
            pre.nxt = nxt
            nxt.pre = pre
            
            cur.fre += 1
            p = pre
            while p.nxt.fre <= cur.fre:
                p = p.nxt
            
            # insert to position after p
            p.nxt.pre = cur
            cur.nxt = p.nxt
            p.nxt = cur
            cur.pre = p
            
        def put(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: nothing
            """
            if self.cap == 0:
                return
            
            # key already exists, value updated
            if self.get(key)!=-1:
                cur = self.mp[key]
                cur.val = value
                self.updateFrequency(cur)
                #self.head.myprint()
                return
            
            # then 1, if self.cap reached; 2, if self.cap not reached.
            if len(self.mp) == self.cap:
                # remove first one
                # print self.head.nxt.key, self.head.nxt is self.tail, len(self.mp), self.cap
                del self.mp[self.head.nxt.key]
                self.head.nxt = self.head.nxt.nxt
                self.head.nxt.pre = self.head
            tmp = Node(key, value)
            self.mp[key] = tmp
            self.addToHead(tmp)
            self.updateFrequency(tmp)
            #self.head.myprint()
                
        def addToHead(self, node):
            self.head.nxt.pre = node
            node.nxt = self.head.nxt
            node.pre = self.head
            self.head.nxt = node
            
    
    
    # Your LFUCache object will be instantiated and called as such:
    # obj = LFUCache(capacity)
    # param_1 = obj.get(key)
    # obj.put(key,value)
    

Log in to reply
 

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