cache

By#!/usr/bin/env python
# -*- coding: utf-8 -*-

CACHE_LEN = 5
CACHE = {}
INDEX = []


def expensive_function(val=0):
    # Inspired by Amazon prime day, today even
    # the expensive function is a bit cheaper
    return val + 1


def show_cache_and_lru_status():
    print "cache:", CACHE
    print "index:", INDEX, "\n"


def get_item_index_pos(item=0):
    for i in range(0, len(CACHE)):
        if INDEX[i] == item:
            return i

    return -1


def add_item_to_cache(item=0):
    # Drop last used item from the cache
    if len(CACHE) >= CACHE_LEN:
        last_used_item = INDEX[-1]
        print "cache is full, dropping last item, key:", last_used_item
        del CACHE[last_used_item]
        INDEX.pop()

    INDEX.insert(0, item)
    CACHE[item] = expensive_function(item)

    print "adding key:", item, "with value:", CACHE[item]
    show_cache_and_lru_status()


def get_item_value_from_cache(item=0):
    if item not in CACHE:
        raise Exception("No such item: " + str(item))
    else:
        item_pos_in_index = get_item_index_pos(item)
        value = CACHE[item]

        # Fix the order of items in the index

        if item_pos_in_index > 0:
            # Swap place with the 0th item in the index list, ie.
            # if the 3rd cache entry was accessed, then the new order
            # would be:
            #
            # 1        3
            # 2        2
            # 3   ->   1
            # 4        4
            # 5        5
            #
            # This won't keep the exact order of when the items in the
            # cache were accessed but it requires 1 swap only.
            #
            # Worst case scenario: with a full cache if the last used item
            # is accessed, and a new item arrives, then the 2nd most recently
            # used item (which just swapped place with the last item in the
            # index) is dropped from the cache.

            tmp = INDEX[0]
            INDEX[0] = INDEX[item_pos_in_index]
            INDEX[item_pos_in_index] = tmp

            # If the expensive function is really expensive, then it's worth to
            # keep the proper order in the index. With this approach the index
            # of the accessed item rises to the top (=0th position) like a
            # bubble at the cost of O(N) performance penalty.
            #
            # for i in reversed(range(0, item_pos_in_index)):
            #    tmp = INDEX[i+1]
            #    INDEX[i+1] = INDEX[i]
            #    INDEX[i] = tmp

        return value


def main():
    # Fill the cache
    for i in range(0, 2*CACHE_LEN):
        add_item_to_cache((i+1)*10)

    # Retrieve a few items to test how the order changes
    for item in (70, 90, 80):
        value = get_item_value_from_cache(item)
        print "After retrieving", item, "(value:", value, ") from cache"
        show_cache_and_lru_status()


if __name__ == "__main__":
    main()


************************************
Output:

adding key: 10 with value: 11
cache: {10: 11}
index: [10]

adding key: 20 with value: 21
cache: {10: 11, 20: 21}
index: [20, 10]

adding key: 30 with value: 31
cache: {10: 11, 20: 21, 30: 31}
index: [30, 20, 10]

adding key: 40 with value: 41
cache: {40: 41, 10: 11, 20: 21, 30: 31}
index: [40, 30, 20, 10]

adding key: 50 with value: 51
cache: {40: 41, 10: 11, 20: 21, 50: 51, 30: 31}
index: [50, 40, 30, 20, 10]

cache is full, dropping last item, key: 10
adding key: 60 with value: 61
cache: {40: 41, 50: 51, 20: 21, 60: 61, 30: 31}
index: [60, 50, 40, 30, 20]

cache is full, dropping last item, key: 20
adding key: 70 with value: 71
cache: {70: 71, 40: 41, 50: 51, 60: 61, 30: 31}
index: [70, 60, 50, 40, 30]

cache is full, dropping last item, key: 30
adding key: 80 with value: 81
cache: {70: 71, 40: 41, 80: 81, 50: 51, 60: 61}
index: [80, 70, 60, 50, 40]

cache is full, dropping last item, key: 40
adding key: 90 with value: 91
cache: {70: 71, 80: 81, 50: 51, 90: 91, 60: 61}
index: [90, 80, 70, 60, 50]

cache is full, dropping last item, key: 50
adding key: 100 with value: 101
cache: {100: 101, 70: 71, 80: 81, 90: 91, 60: 61}
index: [100, 90, 80, 70, 60]

After retrieving 70 (value: 71 ) from cache
cache: {100: 101, 70: 71, 80: 81, 90: 91, 60: 61}
index: [70, 90, 80, 100, 60]

After retrieving 90 (value: 91 ) from cache
cache: {100: 101, 70: 71, 80: 81, 90: 91, 60: 61}
index: [90, 70, 80, 100, 60]

After retrieving 80 (value: 81 ) from cache
cache: {100: 101, 70: 71, 80: 81, 90: 91, 60: 61}
index: [80, 70, 90, 100, 60]


The index order using the 2nd approach:

After retrieving 70 (value: 71 ) from cache
cache: {100: 101, 70: 71, 80: 81, 90: 91, 60: 61}
index: [70, 100, 90, 80, 60]

After retrieving 90 (value: 91 ) from cache
cache: {100: 101, 70: 71, 80: 81, 90: 91, 60: 61}
index: [90, 70, 100, 80, 60]

After retrieving 80 (value: 81 ) from cache
cache: {100: 101, 70: 71, 80: 81, 90: 91, 60: 61}
index: [80, 90, 70, 100, 60]