2

Is there a data structure in Python 3 that is an array of Boolean True or False? Additionally would this array be more memory efficient than an array of bytes?

I need to be able to change a value from True to False and access it by index; but I don't need to be able to change the size of the array.

edit: additionally, if a move command would be faster than indexing, this would be nice also

mikeLundquist
  • 769
  • 1
  • 12
  • 26
  • Possible duplicate of [How to create an array of bits in Python?](http://stackoverflow.com/questions/11669178/how-to-create-an-array-of-bits-in-python) – ShadowRanger Apr 19 '16 at 17:59

2 Answers2

1

How about using array?

import array
a = array.array("B", [0]*10) #fix size of 10 - all False

a[1] = 1 # Mutable, Yay!
print(a)

It will use the least amount of memory and will give you a O(1) indexing

Yoav Glazner
  • 7,936
  • 1
  • 19
  • 36
  • Would this array be more memory efficient than an array of bytes? – mikeLundquist Apr 19 '16 at 17:43
  • FYI, [`bytearray`, available since 2.6](https://docs.python.org/2/library/functions.html#bytearray) doesn't require an import or use of format codes & is much more efficient for certain purposes (in 2.x, `array` doesn't support the buffer protocol; it can't be used w/`memoryview` or other APIs that need "bytes-like objects"; `bytearray` supports the buffer protocol). Also, initializing the `array` with `[0] * x means making a temporary `list` 4-8x the size of the result, then iterating it; `array.array('B', b'\0' * 10)` (or `b'\1' * 10) is 2x faster, and gets even faster as the size increases. – ShadowRanger Apr 19 '16 at 17:53
  • @user4757074: `array.array('B')` _is_ a (dynamic) array of bytes (in the C sense), just like `bytearray`. Each additional value would cost (amortized, it grows by a multiplicative process to minimize reallocs) one additional byte to store, vs. a `list` or `tuple` which would cost one pointer sized variable for each value (so 4 or 8 bytes on 32 and 64 bit architectures respectively), so long as the `list`/`tuple` is filled with 0/`False and 1/`True` only (which are singletons in CPython, so you don't pay object overhead for each separate reference to them). – ShadowRanger Apr 19 '16 at 17:57
1

Usually, it's best to pay the expense of using a byte per value rather than a bit, and you can use bytearray (a built-in since 2.6) for this purpose:

a = bytearray(100)            # 100 values all initialized to 0/False
# or initially true:
b = bytearray(b'\x01' * 100)  # 100 values all initialized to 1/True

# While you'll get 0 and 1 back, True and False can be assigned to it
a[1] = True
b[1] = False

This is usually be the best option, as it's more efficient to use byte addressing in most cases, unless it would cause data to spill from RAM to a swap file.

If you really need the space for a lot of flags, you'd need a third party package that optimizes to get one bit per value, e.g. bitarray (C extension for maximum speed, but still slower than bytearray for many purposes) or bitvector or bitstring (Pure Python, to minimize compilation complications, and sometimes provide additional features more easily, but reliably slower than bytearray when not memory constrained).

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271