This approach proved to be particularly effective with functions which recursively called itself more than once (such as a function to generate the nth Fibonacci number). In this way, we simply stored each and every input and return values of a memoized function.

If the memo did not contain the return value, it would compute the value by calling the actual function, and then indiscriminately store that value against the set of arguments, before returning the value back to the caller. I had implemented memoization such that whenever a memoized function was called with a given set of arguments, that function would first check if a return value for that set of arguments already existed in a dictionary called memo. Recall that memoization refers to the storage of return values of previous function-calls. In my previous post on memoization, I had implemented exactly this. In a world with infinite resources to store infinite amount of data, we can achieve a near-perfect hit ratio, as we can keep populating our cache with the data generated from previous requests, thereby restricting cache misses to only those requests that have never been created before. This makes the hit ratio of cache very crucial. Thus, it is clear that, ideally, the number of cache hits should, on an average, be greater than the number of cache misses.

When requests for those web-pages are generated by the user, the browser can simply retrieve the downloaded pages which will be much faster than loading other web-pages which are not cached. For example, a browser may download web-pages that are most-frequently used by the user. In the event of a cache miss, the data will need to be computed or located from a slower data source, which will take much longer time to generate, than a cache hit. On the other hand, a cache miss occurs when the requested data is not stored in the cache. When the data requested from a cache is successfully found, it is called a cache hit. Otherwise, it will generate that data, which will be stored in the cache for a future request. If yes, it will simply retrieve that data and access it. When an application needs to access some data (which is expected to be cached), it will first check if that data exists in its cache. What is cache?Ĭache refers to the storage of data that is likely to be requested in the future.

Also, inspired by this Clojure repository on Github, I attempt to implement some of the common cache replacement policies. In this post, I attempt to discuss what the term ‘cache’ actually means and delve into some of the common cache replacement policies. It is said that “There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors.” This post will be on the first one.

Cache replacement policy la gi