Python shitty O(1) solution with two dict and one linkedlist


  • 5
    M
    class ListNode(object):
        def __init__(self, key, val):
            self.prev = None
            self.next = None
            self.val = val
            self.key = key
    
        def connect(self, nextNode):
            self.next = nextNode
            nextNode.prev = self
    
    class LFUCache(object):
    
        def __init__(self, capacity):
            """
            
            :type capacity: int
            """
            self.cap = capacity
            self.head = ListNode(None, None)
            self.tail = ListNode(None, None)
            self.head.connect(self.tail)
            #use to record the first ListNode of this count number
            self.cnt = {0: self.tail}
            # key: key , value:[ListNode, visit count]
            self.kv = {None:[self.tail, 0]}
    
        def moveforward(self, key):
            node, cnt = self.kv[key]
            self.add('tmp', node.val, cnt + 1)
            self.remove(key)
            self.kv[key] = self.kv['tmp']
            self.kv[key][0].key = key
            del self.kv['tmp']
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            if key not in self.kv:
                return -1
            self.moveforward(key)
            return self.kv[key][0].val
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            if self.cap == 0:
                return
            if key in self.kv:
                self.kv[key][0].val = value
                self.moveforward(key)
                return
            if len(self.kv) > self.cap:
                self.remove(self.tail.prev.key)
            self.add(key, value, 0)
    
    
        def remove(self, key):
            node, cnt = self.kv[key]
            if self.cnt[cnt] != node:
                node.prev.connect(node.next)
            elif self.kv[node.next.key][1] == cnt:
                node.prev.connect(node.next)
                self.cnt[cnt] = self.cnt[cnt].next
            else:
                node.prev.connect(node.next)
                del self.cnt[cnt]
            del self.kv[key]
    
        def add(self, key, value, cnt):
            if cnt in self.cnt:
                loc = self.cnt[cnt]
            else:
                loc = self.cnt[cnt - 1]
            node = ListNode(key, value)
            loc.prev.connect(node)
            node.connect(loc)
            self.cnt[cnt] = node
            self.kv[key] = [node, cnt]
            
    
    
    # Your LFUCache object will be instantiated and called as such:
    # obj = LFUCache(capacity)
    # param_1 = obj.get(key)
    # obj.set(key,value)
    

  • 0
    P

    I found that using 1 dict + 1 bisect array would have 2x less Python code:

    class LFUCache(object):
        from bisect import bisect
        def __init__(self, capacity):
            self.clock = 0                     # to track least recent used
            self.key_arr = []                  # bisect array, to discard the least frequently used
            self.capacity = capacity
            self.h = {}    
        
        def get(self, key):
            if key in self.h:
                val, freq, clock  = self.h[key]
                self.key_arr.pop(bisect.bisect_left(self.key_arr, (freq, clock)))
                self.h[key] = (val, freq+1, self.clock)
                bisect.insort_left(self.key_arr, (freq+1, self.clock, key))
                self.clock += 1
                return val        
            return -1
                
        def put(self, key, value):
            if self.capacity ==0: return    
            if key in self.h:
                val, freq, clock = self.h[key]
                self.h[key] = (value, freq, clock)
                self.get(key)
            else:
                if len(self.h) == self.capacity:
                    del self.h[self.key_arr[0][2]]
                    self.key_arr.pop(0)
                self.h[key] = (value, 1, self.clock)
                bisect.insort_left(self.key_arr, (1, self.clock, key))
                self.clock += 1

  • 5
    Z

    Your code is elegant. But it is not O(1). the pop operation of self.key_arr is O(n).


  • 0
    This post is deleted!

  • 0
    V

    @zgkdzy Actually, I don't think it is.
    Dictionary Operations (Time Complexity)
    Delete | del d[k] | O(1) |
    Pop | d.pop(k) | O(1) |

    Source: https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt


  • 0

    The double list works very well except that it is not o(1), but it is the best python answer I see so far.

    @vikaasa said in Python shitty O(1) solution with two dict and one linkedlist:

    @zgkdzy Actually, I don't think it is.
    Dictionary Operations (Time Complexity)
    Delete | del d[k] | O(1) |
    Pop | d.pop(k) | O(1) |

    Source: https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

    I think the reference means pop() but not pop(0), which means that it is o(1) only if you are popping from the end of list. Since you are popping from the head, all elements after index 0 in the memory need to be moved, it is a o(n) operation.

    Source: https://wiki.python.org/moin/TimeComplexity


Log in to reply
 

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