|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
The Python virtual machine represents bool values False and True using the int values 0 and 1, respectively. In effect, it uses a 32-bit number to represent one bit of information. Therefore, we can realize a significant reduction in the memory space required to represent a set if we use an array of bits instead of an array of bools. Furthermore, by using bitwise operations to implement the basic set operations such as union and intersection, we can achieve a commensurate reduction in execution time. Unfortunately, these improvements are not free--the operations insert, __contains__, and withdraw, all slow down by a constant factor.
Since Python does not directly support arrays of bits,
we will simulate an array of bits using an array of ints.
Program 
illustrates how this can be done.
The constant BITS is defined as the number
of bits in a single int.
Program: SetAsBitVector class __init__ method.
In addition to self,
the __init__ method takes a single argument 
,
which specifies the universe and, consequently,
the number of bits needed in the bit array.
The __init__ method creates an array of ints
of length 
,
where 
is the number of bits in an int,
and sets the elements of the array to zero.
The running time of the __init__ method is 
.
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.