# Efficiency of using long integers to hold bitmaps

jepler at unpythonic.net jepler at unpythonic.net
Mon Jul 11 04:46:20 CEST 2005

```You'll find that using Python Longs unsuitable if you *change* the
bitmaps---All numeric types are immutable, so you'll copy the bitmap
each time you perform an operation like "set bit".

numarray has a 'bit' typecode, though I'm not sure how such an array is
actually stored---from a quick look, it appears it's stored one bit per
byte:
>>> numarray.ones((3,3), 'Bool').tostring()
'\x01\x01\x01\x01\x01\x01\x01\x01\x01'

A Python object layer around array.array('B') would not necessarily be
fast, but it would at least avoid the copying problem, and be memory
efficient.
import array

class BitArray2D:
def __init__(self, rows, cols):
self.rows = rows
self.cols = cols
nbytes = (rows * cols + 7) / 8
self._data = array.array('B', ) * nbytes

def __getitem__(self, (r,c)):
# TODO: check r, c in bounds
idx = r + c * self.rows
byte = idx / 8
bit = 1 << (idx%8)
return bool(self._data[byte] & bit)

def __setitem__(self, (r, c), v):
# TODO: check r, c in bounds
idx = r + c * self.rows
byte = idx / 8
bit = 1 << (idx%8)
if v:
self._data[byte] |= bit
else:
self._data[byte] &= ~bit

b = BitArray2D(10, 10)
print b._data
for x in range(10):
b[x,x] = b[9-x,x] = 1
print b._data
print
for x in range(10):
for y in range(10):
print " *"[b[x,y]],
print

Jeff
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20050710/bcd389fa/attachment.sig>
```