A list of bits, compacted in memory so that 8 elements use 1 byte of storage.
Python, 121 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | import listmixin # Uses recipe 440656
import array
# Public domain
class BitList(listmixin.ListMixin):
"""
List of bits.
The constructor takes a list or string containing zeros and ones,
and creates an object that acts like list().
This class is memory compact (uses 1 byte per every 8 elements).
"""
def __init__(self, other=()):
self.data = array.array('B')
self.length = len(other)
if hasattr(other, 'capitalize'):
# Initialize from string.
for i in xrange((len(other) + 7) // 8):
c = other[i*8:(i+1)*8]
byte = 0
for j in xrange(len(c)):
if c[j] != '0':
byte |= 1<<j
self.data.append(byte)
else:
# Initialize from sequence.
for i in xrange((len(other) + 7) // 8):
c = other[i*8:(i+1)*8]
byte = 0
for j in xrange(len(c)):
if c[j]:
byte |= 1<<j
self.data.append(byte)
def _constructor(self, iterable):
return BitList(iterable)
def __len__(self):
return self.length
def _get_element(self, i):
return (self.data[i>>3]>>(i&7))&1
def _set_element(self, i, x):
index = i>>3
mask = (1<<(i&7))
if x and x != '0':
if not self.data[index] & mask:
self.data[index] |= mask
else:
if self.data[index] & mask:
self.data[index] ^= mask
def _resize_region(self, start, end, new_size):
"""
Resize slice self[start:end] so that it has size new_size.
"""
old_size = end - start
if new_size == old_size:
return
elif new_size > old_size:
delta = new_size - old_size
self.length += delta
add_bytes = (self.length + 7) // 8 - len(self.data)
self.data.extend(array.array('B', [0] * add_bytes))
for i in xrange(self.length-1, start+new_size-1, -1):
self._set_element(i, self._get_element(i - delta))
elif new_size < old_size:
delta = old_size - new_size
for i in xrange(start+new_size, self.length-delta):
self._set_element(i, self._get_element(i + delta))
self.length -= delta
del_bytes = len(self.data) - (self.length + 7) // 8
assert del_bytes <= len(self.data)
del self.data[len(self.data)-del_bytes:]
def __getstate__(self):
return (self.to_binary(), len(self))
def __setstate__(self, (data, length)):
self.__init__()
self[:] = BitList.from_binary(data, length)
def to_binary(self):
"""
Return base256_binary_str.
"""
return self.data.tostring()
def from_binary(base256_binary_str, num_bits):
"""
Return new BitList from base256_binary_str and number of bits.
"""
ans = BitList()
if len(base256_binary_str) != (num_bits+7)//8:
raise ValueError('invalid length')
ans.length = int(num_bits)
ans.data = array.array('B')
ans.data.fromstring(base256_binary_str)
return ans
from_binary = staticmethod(from_binary)
def set_bit(self, i, x):
"""
Set bit i to x (extending to the right with zeros if needed).
"""
i = int(i)
if i >= len(self):
self.extend([0] * (i + 1 - len(self)))
self[i] = x
def get_bit(self, i):
"""
Get bit i (or zero if i >= len(self)).
"""
i = int(i)
if i >= len(self):
return 0
return self[i]
|
If a list of bits in Python is created via the builtin list class, the resulting object takes up sizeof(void )n bytes of memory. This class makes a time vs memory tradeoff, so that 8 elements require 1 byte of memory. On a machine with 32-bit addressing, this class requires 1/32 of the memory that the builtin Python list class requires (for large list sizes).
The BitList class is intentionally naive in its implementation, so be warned that it will be much slower than the builtin list class.
