Wednesday, May 13, 2015

lru cache for n items

lru cache for n items with O(1) add, remove, has, get.

With queue, add() is not O(1), get() is difficult/hacky to implement. So deque.
// caches n recently used items
lru-cache:
    n // items
    ctor(n):
        n = n
    count = 0
    
    map
    q
    add(key, value):
        if map.has(key):
            // update value, move node to end of dq
            item = map[key]
            item.value = value
            // difficult: item.node need to be put at end
            return
        if count == n:
            // remove lru item
            // handle delayed removal from queue
            lrukey = q.dequeue()
            while !map.has(lrukey):
                lrukey = q.dequeue()
            map.remove(lrukey)
            count--
        // add key
        count++
        q.enqueue(key)
        map.add(key, value)
    remove(key):
        if !map.has(key):
            return // or throw "error"
        count--
        // only remove from map, delay removal from queue during add
        map.remove(key)
    has(key):
        return map.has(key)
    get(key):
        // difficult/hacky to implement

    dq = new deque{key}()
    nodemap = new map{key, node{key}}()
    valuemap = new map{key, value}()

    add(key, value):
        if key == null || value == null: throw
        if has(key):
            // nodemap does not change
            dq.moveToEnd(nodemap[key])
            valuemap[key] = value
            return
        if count == n:
            // remove lru
            lrukey = dq.peek()
            removeInternal(lrukey)
        // add to end
        addInternal(key, value)
    
    value removeInternal(key):
        dq.removeNode(nodemap[key])
        nodemap.remove(key)
        value = valuemap[key]
        valuemap.remove(key)
        count--
        return value
    addInternal(key, value):
        node = dq.enqueue(key)
        nodemap[key] = node
        valuemap[key] = value
        count++
    
    bool remove(key):
        if key == null: throw
        // do not throw if key no exists
        if !has(key):
            return false
        removeInternal(key)
        return true
    
    value get(key):
        if key == null: throw
        // do not throw if key no exists
        if !has(key):
            return null // default(value)
        dq.moveToEnd(nodemap[key])
        return valuemap[key]
    
    bool haskey(key):
        if key == null: throw
        return valuemap.haskey(key)
    
    int count():
        return count
    
// deque interface
deque{key}:
    // for removal in O(1) time
    node{key} enqueue(key):
    removeNode(node{key})
    // moves dq node to end
    moveToEnd(node):
    key peek():
    // not used
    key dequeue():

No comments:

Post a Comment