Friday, October 06, 2017

lfu cache of n items

lfu cache with O(logn) get, add, delete.
lfuCache:
    map
    minheap
    n
    
    ctor(n):
        if n < 0:
            throw
        n = n
        map = new map(capacity: n)
        minheap = new minheap(n, item => item.frequency)
    
    value get(key):
        if key == null: throw
        // do not throw if key no exists
        if !has(key):
            return null // default(value)
        item = map[key]
        item.frequency++ // possible overflow
        minheap.heapify()
        return item.value
    
    add(key, value):
        if key == null: throw
        if has(key):
            item = map[key]
            item.value = value
            item.frequency = 0
            minheap.heapify()
            return
        item = {key, value, frequency: 0} // deleted item have -1 frequency
        if isfull():
            lfuitem = minheap.displace(item)
        else:
            minheap.push(item)
        map[key] = item
    
    bool delete(key):
        if key == null: throw
        // do not throw if key no exists
        if !has(key):
            return false
        item = map[key]
        item.frequency = -1 // new items have 0 frequency
        minheap.heapify()
        minheap.pop()
        return true
    
    bool has(key):
        if key == null: throw
        return map.haskey(key)
    
    int count():
        return minheap.count()
    int isfull():
        return count() == n

// heapify x by keySelector
minheap:
    ctor(n, keySelector):
        n = n
        keySelector = keySelector
    push(x):
    x pop():
    // uses siftdown
    heapify():
    // returns top, replacing with x, heapify
    x displace(x):
    int count():

item:
    value
    frequency // unsigned to reduce overflow chance

No comments:

Post a Comment