Optimizing External-Memory Algorithms
I’ve demonstrated how binary search works in the context of external memory. Now I’m going to present another example of this, but this time with a larger data set, as shown in the following illustration.
Say that we have a file containing a list of 110 elements, and that our computer’s block size is 10. This means we have 11 blocks of data in total. Each rectangle in the diagram that follows represents 10 items of the list; I simply can’t fit 110 values into this image:
Now, here’s a pop quiz for you (since I know you like them): what is the greatest number of I/Os we’d have to perform by executing binary search on this data set?
The answer is that we’d have to incur at most 4 I/Os. There are 11 blocks, and log2 11 is about 4.
This isn’t bad, but we can do better.
Let’s look at an optimization technique that will enable us to search our example file using no more than 2 I/Os. As you’ll see, the first iteration of this approach is only theoretical, but you’ll see later how it can be used practically. This approach, as well as everything I’ll discuss for the remainder of this chapter, will be based on what I call the key to optimizing external-memory algorithms.
The Key to Optimizing External-Memory Algorithms
Without further ado, the key to speeding up external-memory algorithms is to pack as much useful information as we can inside each block. Let’s take a look at what this means, first, in the context of binary search.
When we execute binary search on external memory and perform an I/O to transfer a block into main memory, how much of that block’s information is useful to us?
Well, it depends.
If the value we’re searching for is inside that block, we only care about that value. All the other data is simply the haystack that hides our needle.
But, if the value we’re searching for is not inside that block, then we only care about the first and last values of that block. By knowing those two values alone, we can determine whether the value we’re searching for is somewhere to the left of this block, or if it’s somewhere to the right of this block. So if our block size is 10, there are 8 elements of data that we don’t need, as we only need the first and last elements. In real life, a block may hold hundreds of pieces of data, so we’ve kind of wasted an I/O to transfer a whole lot of useless data.
To optimize this algorithm, we need to consider whether we can pack the block with more useful information—and the more, the better. It’s kind of like hiring a moving truck; we want to fill every cubic inch of that truck with as much stuff as we can. We don’t want to have to make extra trips if we can avoid it.
Indeed, in our case of searching data from an ordered list, there’s a theoretical way to pack a block of data with much more useful information. Here’s how.
Packing Blocks
Instead of performing binary search and using up an I/O to transfer the centermost block of our list into main memory, we can transfer a block that is made up of information drawn from across our list. Specifically, we’ll place into the block every 10th element from the list (except for the final value), like so:
Here, we’ve created a block of 10 elements from data evenly interspersed across the original list.
In other words, instead of using an I/O to transfer a block of contiguous data from the file, we use that I/O to transfer a block of data made up of every 10th value in the list.
Now, here’s the clincher. We’ve used just one I/O so far, but we only need one more I/O to find our desired value.
For example, let’s say that we’re searching for the integer 68. We’d look at the block we’ve loaded into main memory, and see that 68 would lie between the fourth value (the 60) and the fifth value (the 73). With this information, we’d know for certain that the 68 must be contained within the fifth block of the list as shown in the .
At this point, we only need to perform one more I/O to obtain the block where the 68 lives! We’ve successfully devised an algorithm that searches the ordered list in a maximum of 2 I/Os.
Now, the difference between 2 I/Os vs. the 4 I/Os may not seem like much. But in real life, when dealing with big data, our optimization can make a big difference.
For example, suppose we have a computer with a block size of 1,000. If we had a list of one billion elements and we make it so that our first I/O is a block comprised of every 1,000th element from the original list, we effectively break down the original list into about 1,000 sections, each of which contains one million elements. (Technically, it’s 1,001 sections.)
Note that in this case, unlike the previous example, these 1,000 sections aren’t equivalent to 1,000 blocks. For when we break up one billion elements into 1,000 sections, each section contains one million elements. And our block size is only 1,000.
That being said, after this first I/O, we can already pinpoint in which section our value lives. Again, this section contains one million elements, and our block size is 1,000, so we need to dig deeper.
We then take that section of one million values and create a second I/O comprising every 1,000th element, breaking up this section into 1,000 smaller sections, each of which contains 1,000 elements. At this point, each section is indeed the same size as a block.
By analyzing the block currently loaded into memory, we can now locate in which 1,000-element section (out of the one million elements that are in our search space) our desired value lives.
We can then use a third and final I/O to load that 1,000-element block into RAM and locate the desired value.
So, we only need 3 I/Os to find a value in a list of one billion elements! With our first approach of unoptimized external-memory binary search, this would have taken up to 20 I/Os.
For now, I’ll refer to this clever new algorithm as “Optimized Search.” In truth, it doesn’t have a name because it’s not used in real life for reasons you’ll see soon, but let’s run with it for now.
Back to Big O
We’ve seen that the speed of unoptimized external-memory binary search is O(logN/B) I/Os. As we’ll see soon, the Big O of Optimized Search is also, technically, O(logN/B) I/Os. But because both algorithms have the same Big O speed, it turns out that Big O doesn’t capture the performance gains of Optimized Search over its unoptimized counterpart.
If we want to articulate the speed of Optimized Search to show to what extent it’s faster than unoptimized external-memory binary search, we’d have to use a more fine-grained approach than Big O. And to do this, we first need to change up the way we’ve been expressing logarithms.
Throughout this book, we’ve been referring to “log N” without specifying the logarithm’s base. This is because Big O notation doesn’t care about the base, as the base is considered a constant.
However, in practice, the base will make a big difference in the context of our discussion of external-memory algorithms. So, in this chapter (as well as the next), I will make a point to specify a logarithm’s base.
With unoptimized external-memory binary search, we’d say that it performs log2 N/B I/Os. As I explained in Volume 1, Chapter 3, the way I like to think about this logarithm is: how many times do I need to divide a number by 2 until I end up with a result of 1? For example, log2 1,024 is 10 since I have to divide 1,024 10 times until I end up with 1.
The question to consider now, though, is the precise number of I/Os that Optimized Search executes.
With Optimized Search, the way we cut down the list of blocks depends on the block size. If the block size is 10, for example, each I/O divides the original list into 11 sections. Each subsequent I/O takes one of those 11 sections and divides it into a list of 11 smaller subsections. We’d therefore say that this takes log11 N I/Os. Put another way: this is the number of times we need to divide the list by 11 until we get a result of 1.
If, however, the block size is 1,000, then each I/O reduces the original list into 1,001 small subsections. Accordingly, we’d say that it takes log1,001 N I/Os to find the value we’re looking for. Indeed, that’s why when we have a list of one billion elements, it takes just 3 I/Os to perform Optimized Search. That is, log1,001 of one billion is approximately 3.
It emerges that Optimized Search takes roughly logB N I/Os for N data elements. That is, we keep dividing a list of N elements by the block size until we find our search value.
If we wanted to express this even more accurately, we’d take note of the fact that when we divide a list by B, we produce B + 1 sections.
To wrap this nicely in a Big O bow, we’d say that the speed of Optimized Search is O(logB + 1 N). As you’ve seen, this is much faster than O(log2 N). In fact, the greater B is, the faster the algorithm.
The Impracticality of Optimized Search
While the Optimized Search algorithm seems great at face value, it can’t be implemented in reality—at least not in the particular way I’ve described it. The entire premise of Optimized Search is that we tell the computer to create a block using elements scattered across the computer’s memory. However, there’s a problem with this approach.
The thing is, when a computer performs an I/O, we don’t get to tell it how to form its block; it does so automatically. And when a computer creates a block, it only does so using a chunk of contiguous memory. We simply don’t get to tell the computer to form a block out of elements interspersed throughout the data.
But there’s good news. While this version of Optimized Search may not be practical, there’s a data structure out there that operates on the same principles. This data structure uses a similar approach to Optimized Search and drastically reduces the number of I/Os needed for external-memory search. It’s no surprise that this data structure is popular.
