Benchmarking Space

We can benchmark space just as we can time, and thankfully, it’s easy to do with Python. Here’s how we can use Python to measure how many bytes the integer 2 takes up, for example:

	import sys

	object = 2
	sys.getsizeof(object)

For me, this outputs 28, which means that our object—which is the integer 2—takes up 28 bytes. (One byte is equivalent to eight bits.) I mentioned earlier that integers generally take up 32 bits, which should be only 4 bytes. However, I also mentioned that Python crams extra stuff into objects, so it’s hard to always predict precisely how much space a particular object will take up.

To benchmark the space consumption of the various counting sort algorithms, I inserted the sys.getsizeof() method into the three different implementations of counting sort. Specifically, I called the getsizeof() function on the underlying data structure within each implementation. Here’s what this looks like for the bit vector implementation:

	import sys
	import bit_vector


	def counting_sort(array):
	set = bit_vector.BitVector(1000)

	for value in array:
	set.set_bit(value)

	print(sys.getsizeof(set.integers))
	return set.values()

Note that here I checked the space of set.integers rather than simply set. This is because in this context, set is a BitVector instance, and when we run sys.getsizeof() on a class instance, Python measures the space of the instance itself without all the data it references. To get the actual data, I had to run sys.getsizeof(set.integers).

I then shuffled the numbers 0 through 999 and ran counting sort for each implementation (hash table, Boolean array, and bit vector). When I compare the space consumption of each implementation, I get:

Hash Table	36,960 bytes
Boolean Array	8072 bytes
Bit Vector	312 bytes

I think these results speak for themselves and show how incredibly tiny a bit vector can be, and yet still contain all of our set data.

Bit Vector Overkill

A bit vector isn’t going to save you space in all scenarios. In particular, bit vectors are not ideal for sparse sets. A sparse set is a set in which there’s a relatively large range of possible values, but only relatively few values across that range. For example, suppose the range of possible values is 0 through 999. No matter how many values the set will ultimately hold, our bit vector will contain 1,000 bits to accommodate all 1,000 possible set values. So, even if our set only contained five values, our bit vector would take as much space as it takes to hold 1,000 values.

However, with a hash table, if we’re only going to store five values, the hash table will be quite small. When I benchmark it, Python tells me that a hash table with five values takes up only 232 bytes of space, which is smaller than the 1,000-value bit vector that takes up 312 bytes.

It emerges that a bit vector is ideal for sets that are more dense, meaning that the number of values in the set is somewhat closer to the range of possible values. For example, a bit vector of 1,000 bits that holds 800 values is relatively dense. Specifically, it has a density of 80 percent.

You may have to do some benchmarking of the space within your particular application to figure out at what point it will be worth it to use a hash table vs. a bit vector.

No matter what, though, a bit vector will always be smaller than a Boolean array. This is because both data structures create as many pieces of data as there are in the possible range of values. However, a Boolean array will create a new Boolean object for each possible value, while a bit vector will create a new integer for every 32 values.