What specific optimizations can be made to this BitArray class, and how can they be implemented?

Question

Here is the current code for the BitArray class needing optimization (implemented on big integers):

import itertools

################################################################################

class BitArray:

    def __init__(self, values=[], max_size=128):
        self.__data = []
        self.__size = 0
        self.__bits = max_size << 3 # Bytes -> Bits
        self.extend(values)

    ########################################################################

    # String Operators

    def __repr__(self):
        return '{}({}, {})'.format(self.__class__.__name__,
                                   self, self.__bits >> 3)

    def __str__(self):
        return repr(list(self))

    ########################################################################

    # Iteration Methods

    def __iter__(self):
        size = len(self)
        for index in range(size):
            if len(self) != size:
                raise RuntimeError()
            yield self[index]

    def __reversed__(self):
        size = len(self)
        for index in range(size - 1, -1, -1):
            if len(self) != size:
                raise RuntimeError()
            yield self[index]

    ########################################################################

    # Container Methods

    def __len__(self):
        return self.__size

    def __contains__(self, item):
        return any(value == item for value in self)

    def __getitem__(self, key):
        div, mod = divmod(self.__get_index(key), self.__bits)
        return bool(self.__data[div] >> mod & 1)

    def __setitem__(self, key, value):
        div, mod = divmod(self.__get_index(key), self.__bits)
        if value:
            self.__data[div] |= 1 << mod
        else:
            self.__data[div] &= ~(1 << mod)

    def __delitem__(self, key):
        div, mod = divmod(self.__get_index(key), self.__bits)
        value = self.__data[div]
        self.__data[div] = value >> 1 & -(1 << mod) | value & (1 << mod) - 1
        set_mask = 1 << (self.__bits - 1)
        for div in range(div + 1, len(self.__data)):
            value = self.__data[div]
            if value & 1:
                self.__data[div - 1] |= set_mask
            self.__data[div] = value >> 1
        self.__size -= 1
        if not len(self) % self.__bits:
            del self.__data[-1]

    ########################################################################

    # Comparison Operators

    def __eq__(self, other):
        return self.__cmp__(other) == 0

    def __gt__(self, other):
        return self.__cmp__(other) > 0

    def __lt__(self, other):
        return self.__cmp__(other) < 0

    def __ne__(self, other):
        return self.__cmp__(other) != 0

    def __ge__(self, other):
        return self.__cmp__(other) >= 0

    def __le__(self, other):
        return self.__cmp__(other) <= 0

    ########################################################################

    # Math Operators

    def __add__(self, other):
        value = self.__class__(self, self.__bits >> 3)
        value.extend(other)
        return value

    def __mul__(self, other):
        value = self.__class__([], self.__bits >> 3)
        for _ in range(other):
            value.extend(self)
        return value

    def __rmul__(self, other):
        return self * other

    def __iadd__(self, other):
        self.extend(other)
        return self

    def __imul__(self, other):
        size = len(self)
        for _ in range(other - 1):
            for index in range(size):
                self.append(self[index])
        return self

    ########################################################################

    # List Methods

    def append(self, item):
        index = len(self) % self.__bits
        if not index:
            self.__data.append(0)
        if item:
            self.__data[-1] |= 1 << index
        self.__size += 1

    def extend(self, iterable):
        for item in iterable:
            self.append(item)

    def count(self, item):
        return sum(1 for value in self if value == item)

    def index(self, item, start=None, stop=None):
        for index in range(
            0 if start is None else self.__get_index(start),
            len(self) if stop is None else self.__get_index(stop)):
            if self[index] == item:
                return index
        raise ValueError()

    def reverse(self):
        for index in range(len(self) >> 1):
            self[index], self[~index] = self[~index], self[index]

    def pop(self, index=None):
        index = len(self) - 1 if index is None else self.__get_index(index)
        value = self[index]
        del self[index]
        return value

    def remove(self, item):
        for index, value in enumerate(self):
            if value == item:
                del self[index]
                return
        raise ValueError()

    def sort(self, *, key=lambda item: item, reverse=False):
        reverse, lo, hi = bool(reverse), 0, len(self) - 1
        while lo < hi:
            if bool(key(self[lo])) is not reverse:
                while lo < hi:
                    if bool(key(self[hi])) is reverse:
                        break
                    hi -= 1
                else:
                    break
                self[lo], self[hi] = self[hi], self[lo]
            lo += 1

    def insert(self, index, item):
        for index in range(self.__get_index(index), len(self)):
            temp = item
            item = self[index]
            self[index] = temp
        self.append(item)

    ########################################################################

    # Helper Methods

    def __cmp__(self, other):
        for a, b in itertools.zip_longest(self, map(bool, other)):
            if a != b:
                if None in {a, b}:
                    return (b is None) - (a is None)
                return a - b
        return 0

    def __get_index(self, key):
        size = len(self)
        if key < 0:
            key += size
        if not 0 <= key < size:
            raise IndexError()
        return key

These are some tests used to make sure that the code is still working after making various changes to it:

# Test Range Check
x = BitArray([], 1)
x.append(True)
try:
    x[5] = True
except IndexError:
    pass
else:
    raise RuntimeError()
try:
    y = x[5]
except IndexError:
    pass
else:
    del y
    raise RuntimeError()

# Test Append, Set, Get
x = BitArray([], 1)
for _ in range(7):
    x.append(False)
x.append(True)
assert x[7]
assert not x[6]
x[6] = True
x[7] = False
assert x[6]
assert not x[7]

# Test Extend and Compare
x = BitArray([False, False])
y = BitArray([False, False])
assert x.__cmp__(y) == 0
x[0] = True
assert x.__cmp__(y) == +1
y[0] = y[1] = True
assert x.__cmp__(y) == -1
x[1] = True
x.append(False)
assert x.__cmp__(y) == +1
x[2] = True
assert x.__cmp__(y) == +1
y.append(True)
y.append(False)
assert x.__cmp__(y) == -1
y[3] = True
assert x.__cmp__(y) == -1

# Test Addition, Multiplication
x = BitArray([False, True])
y = BitArray([True, False])
assert x + y == BitArray([False, True, True, False])
assert x * 3 == x + x + x
assert y * 3 == y + y + y
assert 3 * x == x + x + x
z = BitArray(x)
x += y
assert x == z + y
z = BitArray(y)
y *= 3
assert y == z + z + z

# Test Reverse
x = BitArray([False, True])
y = BitArray([True, False])
x.reverse()
assert x == y

# Test Remove
x = BitArray([False, True])
x.remove(False)
x.remove(True)
try:
    x.remove(False)
except ValueError:
    pass
else:
    raise RuntimeError()
try:
    x.remove(True)
except ValueError:
    pass
else:
    raise RuntimeError()

# Test Delete, Pop
x = 0b1110011111100111
y = BitArray((x >> shift & 1 for shift in range(x.bit_length())), 1)
del y[15], y[2], y[-1]
assert len(y) == 13
del y[-1]
assert len(y) == 12
assert not y[11] and not y[10] and y[8]
y[8] = False
del y[6]
assert y._BitArray__data[0] == 0b1110011
assert y.pop(0)
assert not y.pop()

Edit: Sometimes I write code for fun and the benefit of others. It was disappointing to not find a module like this in the standard library. This is an exercise of writing a good BitArray class that anyone can use. As a result, this code was created to:

1. act similarly to the list data type
2. have an efficient implementation
3. use int array with maximum bit length

Answer 1

Overall implementation decisions

The first question is whether you have implemented this in the correct language. Python has its low level data structures implemented in C for a reason. A BitArray will be used like those low level data structures, and I suspect it would be better implemented in C for speed.

The second question is your choice of data structure. You use a list of ints. There are two alternative strategies you could consider. One is to use a byte array It works like a list, but it specialized to hold byte sized ints as you are doing. The other is to use the mpz type from the gmpy module. It holds long integers, of any size you need. It provides methods to get and set bits. Of course it will end up doing something similar to what you've done here, but by using the gmpy module, you can have it be done in C.

Comments on some of the code

def __iter__(self):
    size = len(self)

Its going to be slightly less efficient to call len, rather then accessing size directly.

    for index in range(size):
        if len(self) != size:
            raise RuntimeError()

I wouldn't check this. Python doesn't consistently give exceptions when modifying an object while iterating over it. It only does it in cases where it necessary to avoid a SEGFAULT. So I'd just going on and let the chips fall where they may.

        yield self[index]

You can actually also just remove this function. If you don't provide a __iter__ function, python handles it by calling __getitem__ with increasing indexes until getting a IndexError All you've done here is implement the default handling.

def sort(self, *, key=lambda item: item, reverse=False):

I'm not really sure why you would ever want to sort a list of 1s and 0s.

    reverse, lo, hi = bool(reverse), 0, len(self) - 1
    while lo < hi:
        if bool(key(self[lo])) is not reverse:

What if somebody uses a key like lambda item: int(item) + 5 Because you convert everything to bool, you won't detect the difference between 5 and 6. And you won't sort the same way as a python list.

You also call key a lot, but since there are only two values, True and False, perhaps you should only call it twice and store the values.

            while lo < hi:
                if bool(key(self[hi])) is reverse:
                    break
                hi -= 1
            else:
                break
            self[lo], self[hi] = self[hi], self[lo]

This swap operation is actually going to be fairly expensive. You have to jump into another function, do a division, bit twiddling, etc and you have to do it four times for the swap.

        lo += 1

I think the whole method could be faster by building a new __data from scratch.

one_bytes, one_bits = divmod(total_ones, 8)
zero_bytes, zero_bits = divmod(total_zeros, 8)
self.__data = [0] * zero_bytes + [255] * one_bytes 
# handling the leftover bits is a bit tricky, but hopefully you get the idea