Optimal Offline Caching

4/December/2015 by Valkryst, Updated 29/June/2017

The following post is derived from notes taken while reading through this textbook.

Assumptions and Statements:

Because this is an offline cache, we know the full sequence of requests. This allows us to make an algorithm that produces an optimal result.

Algorithm:

Algorithm - optimalOfflineCaching(Item[] items, int cacheSize)

Input - An array representing a sequence of items to be requested in the order that they appear in the array. The size of the cache.

Output - The number of cache misses.

    
        Item[] cache = new Item[cacheSize]
        misses = 0

        for (i = 0 to items.length)
            wasInCache = false

            for (k = 0 to cache.length)
                if(cache[k] == item[i])
                    wasInCache = true
                end
            end

            if (wasInCache == false)
                misses++

                for (k = 0 to cache.length)
                    if (k == cache.length && cache[k] is full)
                        Replace the cached, item that will be used furthest in the future,
                        with item[i].
                    else if (cache[k] is empty)
                        cache[k] = item[i]
                        break
                    end
                end
            end
        end

        return misses