Exercises

The following exercises provide you with the opportunity to practice with caching. The solutions to these exercises are found in the section .

Say that we have a cache that holds up to 5 values. How many cache misses occur for this sequence if our cache uses the clairvoyant eviction policy?
"c", "t", "h", "o", "p", "t", "h", "z", "o", "a", "p", "t", "b", "z", "h"
How many cache misses will occur if our cache uses the LRU eviction policy for the prior sequence?

Following is a Python class representing a rather contrived concept that I call a “Bit Box”:

	class BitBox:
	def __init__(self):
	self.red_bits = [1] * 10000
	self.blue_bits = [1] * 10000
	self.green_bits = [1] * 10000

Basically, each Bit Box is a storage container for the integers 0 and 1. Each Bit Box contains an array of 10,000 “red” bits, 10,000 “blue” bits, and 10,000 “green” bits. When each Bit Box is created, all the bits are set to 1.

The next bit of code creates a single Bit Box:

bit_box = BitBox()

Following are two different methods that count all the 1 bits in a Bit Box. Which of these methods has better spatial locality?

	def count_bits_1(bit_box):
	sum = 0

	for i in range(10000000):
	sum += bit_box.red_bits[i]
	sum += bit_box.blue_bits[i]
	sum += bit_box.green_bits[i]

	return sum


	def count_bits_2(bit_box):
	sum = 0

	for i in range(10000000):
	sum += bit_box.red_bits[i]
	for i in range(10000000):
	sum += bit_box.blue_bits[i]
	for i in range(10000000):
	sum += bit_box.green_bits[i]

	return sum

Puzzle: Here’s an exercise where it might help to combine two data structures together to produce an efficient solution. (Yes, that was a hint.)

Create a data structure that allows for O(1) searches, O(1) insertions, but also allows for O(1) random samples. In this context, a random sample means that we pick at random a single value from the data set. As always, each value must have an equal chance of being chosen. The trick here is how to achieve O(1) for reads, insertions, and random samples.