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
    add(key, value):
        if map.has(key):
            // update value, move node to end of dq
            item = map[key]
            item.value = value
            dq.movetoend(item.node)
            return
        if count == n:
            // remove lru item
            count--
            lrukey = dq.dequeue()
            map.remove(lrukey)
        // add key
        count++
        node = dq.enqueue(key)
        map.add(key, {node, value})
    remove(key):
        if !map.has(key):
            return // or throw "error"
        count--
        item = map[key]
        dq.remove(item.node)
        map.remove(key)
    has(key):
        return map.has(key)
    get(key):
        if !map.has(key):
            return null
        // move node to end of dq
        item = map[key]
        dq.movetoend(item.node)
        // map does not change
        return item.value
    count():
        return count
    
// deque interface
dq:
    // enqueue(key), remove(node), movetoend(node) are used 
    // for removal in O(1) time
    node enqueue(key):
    key dequeue():
    remove(node):
    movetoend(node):

No comments:

Post a Comment