Boolean Arrays

We’ve looked at a couple of examples where sets offer considerable speed benefits. In particular, we took full advantage of a hash table’s O(1) lookups to achieve some really fast code.

The interesting thing, though, is that there’s an even faster set data structure than a hash table. Don’t get me wrong; hash tables are great for serving as sets. But in certain scenarios, other data structures can be even faster. One such data structure is the Boolean array. The name may sound fancy, but it’s simply a regular array in which we only store the values True or False. The array [True, True, False, True, False, False, True] is a Boolean array.

A Boolean array can serve as a set when our data consists of integers that lie in a relatively limited range—similar to the earlier counting sort example. With such a data set, we can use the array’s index to signify one of the integers of our data. For example, suppose we want to store a set that contains the integers 1, 4, 5, and 9. We can do so with a Boolean array that looks like this:

If you look carefully, you’ll see that the indexes 1, 4, 5, and 9 are all set to True. This is a simple trick for using a Boolean array to represent a set of integers.

Using a Boolean Array to Find Duplicates

Let’s now go back to the previous examples of finding duplicates and counting sort. We’ll swap out the hash table for a Boolean array and see what happens. We’ll start with finding duplicates. The code is almost identical to our previous implementation. It’s just that now we use an array instead of a hash table:

We initialize our array by making it a Boolean array containing 1,000 False values. We’ve made it 1000 with the assumption that our data will consist of integers that lie in the range from 0 to 999. If your data has a different range, you’d update this number accordingly.

One might reasonably assume that the efficiency of this code should be the same as when we used a hash table. With either a hash table or a Boolean array, in a worst-case scenario, we iterate over all N values of the input array and insert them into a set. Yet, when I benchmark the two competing code snippets, I get different results.

This is the speed of our hash table version over the course of five runs:

That’s pretty fast! But look at my results of benchmarking the Boolean array code:

The Boolean array code is definitely faster. So, despite both versions seemingly consisting of the same steps, the Boolean array approach wins the race. This is because looking up values in an array is faster than looking up values in a hash table. With a hash table, the computer has to perform a hash function on each value to determine where it lives. With an array, no such computation is needed; a computer knows how to find an index without a hash function.

Note that you can use Boolean arrays even if the range doesn’t start at 0. If, say, the range of integers is from 3000 to 4000, you can still use a Boolean array in the same way. That is, you simply add 3000 to each index in the array to figure out what integer that index truly represents. So, the index 0 represents the integer 3000 of the Boolean array, and index 456 represents the integer 3456.

Using a Boolean Array for Counting Sort

We’ve looked at the Boolean array version of duplicate detection. Let’s return to our other application—counting sort—and modify its code to use a Boolean array instead of a hash table:

Here, we initialize a Boolean array designed to represent the integers 0 through 9999. The code is the same as before, except that our set is housed in a Boolean array rather than a hash table.

My benchmarking results also show that the Boolean array code is faster than its hash table counterpart, although not by as large a margin as with finding duplicates. Here are the results for when these snippets work to sort 9,000 values:

The hash table version yields these speeds:

The Boolean array code runs at this speed:

For this example, the Boolean array approach is about 1.5 times faster than its hash table counterpart. It emerges that choosing the right set data structure can make a real difference.

Space-Saving Sets

We’ve seen how sets, whether in the form of a hash table or a Boolean array, can boost our code’s speed in various applications. However, these benefits don’t come for free.

Although the brute-force approach of finding duplicates is a slow O(N²), it does have a saving grace in that it doesn’t take up any extra space. That is, the brute-force algorithm doesn’t create any additional data structures. However, the set-based approaches create a set that didn’t exist before. These sets take up space!

To be precise, the hash table set holds up to N values, as we insert each of the input array values into the hash table. The Boolean array also takes up space, as it holds R values. That is, if our range of data is 0 to 9999, the Boolean array holds 10,000 Boolean values. And so, the speed that we gained by using a set comes with a trade-off that we must consume extra space. There’s no way around the fact that a set will take up memory. That being said, I will now introduce to you a new set data structure that can take up way less space than either a hash table or Boolean array and yet still offer O(1) lookups: bit vectors.