Data structure to manipulate long strings of bits

Question

In Python, what is the best data structure of n bits (where n is about 10000) on which performing the usual binary operations (&, |, ^) with other such data structures is fast?

score 5 · Accepted Answer · edited May 23 '17 at 12:27

"Fast" is always relative :)

The BitVector package seems to do what you need. I have no experience concerning performance with it though.

There is also a BitString implementation. Perhaps you do some measurements to find out, which one is more performant for your specific needs?

If you don't want a specific class and do not need things such as slicing or bit counting, you might be ok simply using python's long values which are arbitrary length integers. This might be the most performant implementation.

This qestion seems to be similar, although the author need fewer bits and requires a standard library.

score 2 · Answer 2 · answered Feb 22 '12 at 13:07

2

In addition to those mentioned by MartinStettner, there's also the bitarray module, which I've used on multiple occations with great results.

PS: My 100th answer, wohooo!

answered Feb 22 '12 at 13:07

Lauritz V. Thaulow

49,139
12
73
92

1

Might be even more performant than my suggestions since it's implemented in C. OTOH you might have some troubles installing it since it needs a working C compiler. See http://stackoverflow.com/questions/780127/installing-bitarray-in-python-2-6-on-windows for possible solutions :) – MartinStettner Feb 22 '12 at 14:24

Data structure to manipulate long strings of bits

2 Answers2