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', [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