This chapter covers
- Avoiding computing things twice
- Introducing caching as a solution
- Describing different types of caches
- Designing an efficient solution for LRU cache
- Discussing MFU and other choices for handling priority
- Discussing caching strategies
- Reasoning about concurrency and synchronization
- Describing how caches can be applied in a sentiment analyzer’s pipeline
This chapter is going to be different from what you have seen so far in this book. We are not going to introduce a new data structure, but instead we will use the ones described in chapters 2–5 to create a more complex data structure. By using lists, queues, hash tables, and so on as building blocks, we will be able to create an advanced data structure that can be used to quickly access values and computed results that were recently accessed—although one could argue that a cache is more than just a data structure; it’s a sophisticated component with several moving parts. In its simplest form, a cache can be implemented as an associative array, but we will see during the course of this chapter that it can become as complex as a web service.