Python, need optimization suggestions.


  • 0
    J

    Hello,
    Doing the dict/doubly linked list algorithm. Any ideas why my code takes so long? Bottom 20 percentile.

    class LRUCache(object):
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.cache = {}
            self.ll = LRUCache.DubLL()
            self.capacity = capacity
    
        class DubNode:
            def __init__(self, key, val, prev=None, next=None):
                self.key = key
                self.val = val
                self.prev = prev
                self.next = next
        
        class DubLL:
            def __init__(self):
                self.length = 0
                self.head = None
                self.tail = None
            
            # add node to the end of list (most recent)
            def add(self, node):
                self.length += 1
                
                if self.head == None:
                    # lazy init head and tail
                    self.head = node
                    self.tail = node
                else:
                    # append to end
                    node.prev = self.tail
                    node.next = None
                    self.tail.next = node
                    self.tail = self.tail.next
            
            # remove node from the list
            def remove(self, node):
                self.length -= 1
                
                # update head and/or tail
                if self.head == node:
                    self.head = self.head.next
                if self.tail == node:
                    self.tail = self.tail.prev
                
                # detach node from list
                if node.prev:
                    node.prev.next = node.next
                if node.next:
                    node.next.prev = node.prev
            
            # remove and add to end of list        
            def update(self, node):
                self.remove(node)
                self.add(node)
            
            # pop least recently used
            def pop(self):
                result = self.head
                self.remove(self.head)
                return result
    
        def get(self, key):
            """
            :rtype: int
            """
            if key in self.cache:
                node = self.cache[key]
                self.ll.update(node)
                return node.val
            return -1
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: nothing
            """
            if key not in self.cache:
                if self.ll.length >= self.capacity:
                    del self.cache[self.ll.pop().key]
                node = LRUCache.DubNode(key, value)
                self.cache[key] = node
                self.ll.add(node)
            else:
                node = self.cache[key]
                self.ll.update(node)
                node.val = value
    
    

Log in to reply
 

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