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?
--
http://mail.python.org/mailman/listinfo/python-list
