Efficiency of using long integers to hold bitmaps
jepler at unpythonic.net
jepler at unpythonic.net
Sun Jul 10 22:46:20 EDT 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', [0]) * 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>
More information about the Python-list
mailing list