Asp Forum - BitVector - comp.lang.python

diffuser78

3/10/2008 4:27:00 AM

Hi,

I am trying to solve a genetic algorithm problem where I want to read
a bitvector of very large size (say 10000) and manipulate bits based
on certain algorithms.

I am a newbie in Python. What data structure are good to read such
huge data set. Are there any built in classes for bit fiddling.

Every help is greatly appreciated,

Thanks

5 Answers

Gabriel Genellina

3/10/2008 4:49:00 AM

On 10 mar, 01:26, DanielJohnson <diffuse...@gmail.com> wrote:
> Hi,
>
> I am trying to solve a genetic algorithm problem where I want to read
> a bitvector of very large size (say 10000) and manipulate bits based
> on certain algorithms.
>
> I am a newbie in Python. What data structure are good to read such
> huge data set. Are there any built in classes for bit fiddling.
>
> Every help is greatly appreciated,
>
> Thanks

Aaron Brady

3/10/2008 6:39:00 AM

> > I am trying to solve a genetic algorithm problem where I want to read
> > a bitvector of very large size (say 10000) and manipulate bits based
> > on certain algorithms.

Here's one on the Python website:
http://search.live.com/results.aspx?q=python+bitvector&src=IE...
=> http://pypi.python.org/pypi/Bit...
=> http://cobweb.ecn.purdue.edu/~kak/dist/BitVecto...
code=> http://cobweb.ecn.purdue.edu/~kak/dist/BitVector_1.3_CodeOn...

"The bits of a bit array are stored in 16-bit unsigned ints."

However, Python has variable size longs. Do you want something less
elaborate?

Here is what I think of when you say bitvector:

bA= bitvector()
bA[3]= 0
bA[7]= 1
bA[2].set()
bA[1]^= b[9]
bA[2:6].set()
rangeA= ba[2:7]
rangeA= "011101"
rangeA.clear()

bytearray is kind of close, but new in Py 3.0. How close is it to the
perspective of the application you're writing?

Here's some of it straight off the console:

>>> b= bytearray(5)
>>> b
bytearray(b'\x00\x00\x00\x00\x00')
>>> b[1]= 1
>>> b
bytearray(b'\x00\x01\x00\x00\x00')
>>> list(b)
[0, 1, 0, 0, 0]

John Machin

3/10/2008 6:58:00 AM

On Mar 10, 3:26 pm, DanielJohnson <diffuse...@gmail.com> wrote:
> Hi,
>
> I am trying to solve a genetic algorithm problem where I want to read
> a bitvector of very large size (say 10000) and manipulate bits based
> on certain algorithms.
>
> I am a newbie in Python. What data structure are good to read such
> huge data set. Are there any built in classes for bit fiddling.
>

Bitwise operations like & | ^ << >> etc work on long integers. This
happens at C speed. An alternative (in pure Python) is found via:
http://pypi.python.org/pypi...

HTH,
John

Paul Rubin

3/10/2008 6:05:00 PM

John Machin <sjmachin@lexicon.net> writes:
> Bitwise operations like & | ^ << >> etc work on long integers. This
> happens at C speed.

The problem is if you want to set a bit, you have to allocate a whole
new long integer.

Ross Ridge

3/10/2008 6:52:00 PM

DanielJohnson <diffuser78@gmail.com> wrote:
>I am trying to solve a genetic algorithm problem where I want to read
>a bitvector of very large size (say 10000) and manipulate bits based
>on certain algorithms.
>
>I am a newbie in Python. What data structure are good to read such
>huge data set. Are there any built in classes for bit fiddling.

A 10000 bit data set is by no means huge. Depending on exactly what
operations you want to perform converting your "bitvector" to a byte
array, one bit per byte may be fast way to go. This increases the size
of data set by 8 times, but it's probably the fastest way in Python to
test and set individual bits.

Here's a couple of functions I wrote for very quickly converting a
"bitvector" in the form of a string (eg. read from a file) in to a
byte array:

import string
import array
import binascii

_tr_16 = string.maketrans("0123456789abcdef",
"\x00\x01\x02\x03"
"\x10\x11\x12\x13"
"\x20\x21\x22\x23"
"\x30\x31\x32\x33")
_tr_4 = string.maketrans("0123",
"\x00\x01"
"\x10\x11")
_tr_2 = string.maketrans("01", "\x00\x01")

def string_to_bit_array(s):
"""Convert a string to an array containing a sequence of bits."""
s = binascii.hexlify(s).translate(_tr_16)
s = binascii.hexlify(s).translate(_tr_4)
s = binascii.hexlify(s).translate(_tr_2)
a = array.array('B', s)
return a

_tr_rev_2 = string.maketrans("\x00\x01", "01")
_tr_rev_4 = string.maketrans("\x00\x01"
"\x10\x11",
"0123")
_tr_rev_16 = string.maketrans("\x00\x01\x02\x03"
"\x10\x11\x12\x13"
"\x20\x21\x22\x23"
"\x30\x31\x32\x33",
"0123456789abcdef")
def bit_array_to_string(a):
"""Convert an array containing a sequence of bits to a string."""
remainder = len(a) % 8
if remainder != 0:
a.fromlist([0] * (8 - remainder))
s = a.tostring()
s = binascii.unhexlify(s.translate(_tr_rev_2))
s = binascii.unhexlify(s.translate(_tr_rev_4))
return binascii.unhexlify(s.translate(_tr_rev_16))

I've used these functions to implement a data compression algorithim
in Python. The algorithm still runs very slow in Python, but it runs
much faster than it would have if I had used Python's bitwise operators.

Ross Ridge

--
l/ // Ross Ridge -- The Great HTMU
[oo][oo] rridge@csclub.uwaterloo.ca
-()-/()/ http://www.csclub.uwaterloo.c...
db //

comp.lang.python