Welcome, guest | Sign In | My Account | Store | Cart

A list of bits, compacted in memory so that 8 elements use 1 byte of storage.

Python, 121 lines
  1
  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.

Created by Connelly Barnes on Tue, 4 Oct 2005 (PSF)
Python recipes (4591)
Connelly Barnes's recipes (7)

Required Modules

Other Information and Tasks