Most efficient way of storing 1024*1024 bits

[Dan Bishop]

Tor Erik Sønvisen wrote:
> Hi
>
> I need a time and space efficient way of storing up to 6 million bits.

The most space-efficient way of storing bits is to use the bitwise
operators on an array of bytes:

import array

class BitList(object):
   def __init__(self, data=None):
      self._data = array.array('B')
      self._length = 0
      if data is not None:
         self.extend(data)
   def __len__(self):
      return self._length
   def __getitem__(self, index):
      if index < 0:
         index += self._length
      if index < 0 or index >= self._length:
         raise IndexError('BitList index out of range')
      byte_index, bit_index = divmod(index, 8)
      return int(bool(self._data[byte_index] & (1 << bit_index)))
   def __setitem__(self, index, value):
      if index < 0:
         index += self._length
      if index < 0 or index >= self._length:
         raise IndexError('BitList index out of range')
      byte_index, bit_index = divmod(index, 8)
      byte = self._data[byte_index]
      bitmask = 1 << bit_index
      byte &= ~bitmask & 0xFF
      if value:
         byte |= bitmask
      self._data[byte_index] = byte
   def __repr__(self):
      return 'BitList([%s])' % ', '.join(str(bit) for bit in self)
   def append(self, value):
      if not self._length % 8:
         self._data.append(0)
      self._length += 1
      self[-1] = value
   def extend(self, values):
      for v in values:
         self.append(v)

> Time efficency is more important then space efficency

In that case, you're better off simply using a list of bools.

> as I'm going to do searches through the bit-set.

What kind of searches?