Chapter 4

These are the solutions to the .

1. In the first five steps, we fill up our cache with 5 values:

   ​	["c", "t", "h", "o", "p"]

   Technically, these are all cache misses, so we have 5 cache misses so far. When we then request the next "t" and "h", these are both cache hits since those values are currently in the cache.

   Next, we reach the first "z", which brings our cache miss tally to 6. This will evict the "c" since the "c" will never be requested again. Our cache currently looks like this:

   ​	["z", "t", "h", "o", "p"]

   The next request is the second "o", which is a cache hit. After that, we reach the "a", which is our 7th cache miss. This will evict the "o", which won’t ever be requested again.

   Our cache now looks like this:

   ​	["z", "t", "h", "a", "p"]

   The next two requests, namely the "p" and "t", are both cache hits. The "b" is our 8th cache miss. At this point, we can evict an arbitrary choice of the "t", "a", or "p" since we won’t be requesting those values again.

   The final two requests of "z" and "h" are both cache hits.

   So when all is said and done, we have a total of 8 cache misses.

2. We initially fill our cold cache with the first five requests. Because we’re now dealing with an LRU cache, we fill the cache in reverse order, with the first item representing the most recently used item:

   ​	[p, o, h, t, c]

   The next two requests, that is, the "t" and "h", are both cache hits. We move these items to the front of our cache, which means that our cache is now:

   ​	[h, t, p, o, c]

   The request after that, though, is our 6th cache miss since the "z" is not currently in the cache. We evict the "c" since that’s the LRU item, leaving our cache as:

   ​	[z, h, t, p, o]

   Our next request is "o", which is a cache hit. We move the "o" to the front of the cache:

   ​	[o, z, h, t, p]

   The next request is "a", which is our 7th cache miss. We evict the "p":

   ​	[a, o, z, h, t]

   Unfortunately, we next request a "p", which we literally just evicted. This is our 8th cache miss. We evict the "t":

   ​	[p, a, o, z, h]

   We next request a "t", which we also evicted in the previous step. This is our 9th cache miss. After evicting the "h", our cache is now:

   ​	[t, p, a, o, z]

   Our next request of "b" is our 10th cache miss. The cache now appears like this:

   ​	[b, t, p, a, o]

   Our last two requests are "z" and "h", which are also both cache misses. Our final cache miss tally, then, is 12.

3. The clear_bits_2 method might raise your coworkers’ eyebrows, but it does have better spatial locality. The problem with the other method, clear_bits_1, is that when it loads bit_box.red_bits[i], the computer caches the entire array of red bits.

   However, the next step of code doesn’t read from red bits; it reads from the array of blue bits instead! If your cache was just large enough to hold the red bits, you’ll have to evict the red bits and then cache the blue bits. Once again, though, the next step of code jumps to the green bits, for which your cache doesn’t help in any which way.

   This problem repeats itself when we start the loop again, for then the code reads from the red bits again, even though we only have the green bits in the cache.

   With clear_bits_2, though, once we perform our first read from the array of red bits and cache this array, our code continues to read all the red bits. The fact that we already have the red bits in the cache will give our code a performance boost.

   However, as we’ve learned, one shouldn’t simply write a method like clear_bits_2 without benchmarking it. Especially given that clear_bits_2 is a wonky way of writing code in that it’s more verbose, we’d better know for sure that it’s faster. In fact, when I’ve benchmarked this code, I’ve found that clear_bits_2 is slightly slower than clear_bits_1. This may be because, firstly, the spatial locality may not matter here since my cache may be large enough to fit all the data (from red, blue, and green bits together). Therefore, clear_bits_1 benefits from the cache just as clear_bits_2 does. On top of that, clear_bits_2 has to initiate 3 separate loops, which may slow things down slightly.

   It turns out that not every algorithm that enjoys better spatial locality is faster than competing algorithms with worse spatial locality.

4. A hash table provides for O(1) searches and O(1) insertions, but doesn’t easily allow us to choose a random element.

   An array, on the other hand, allows us to sample a random element in O(1) time since we can choose a random index in one step. An array can even allow us to insert new elements in O(1) time—if we append new data at the end of the array. However, an array does not allow for O(1) searches. Linear search of an array takes O(N) time, and even binary search (if the array is sorted) takes O(log N) time.

   So, how can we get the best of both worlds?

   Well, one approach is to combine a hash table together with an array. Here’s what I mean:

   Each time we insert a new element, we insert that element into both the hash table and the array. We can insert the element as a key in the hash table, and simply make the value True or the like. At the same time, we also append the element to the end of the array. Yes, there’s duplicate data, but the exercise didn’t restrict that. In any case, we’ve achieved O(1) insertion.

   Since the data is present in the hash table, we can also pull off O(1) searches. That is, each time we conduct a search, we always do so from the hash table, which allows us to search in O(1) time.

   However, when we perform a random sample, we do so from the array. Again, a typical hash table doesn’t allow you to pick a key at random. But since we have all the data in the array as well, we can choose a random element from the array in O(1) time.