[Pyrex] array.array vs long ints for bit vectors

[Nitin Madnani]

Thanks for the detailed reply, John. Let me answer some of your  
questions and ask some more of mine.

> For a start, what operations do you want to perform on this "bit  
> vector"?
>
> Let's assume at the very least it should have get/set like a list,  
> but contained objects are restrained to belong to set([0, 1]).
>
> Maybe it should also support something like this:
>
> three = Bitvector([1, 1,])
> six = Bitvector([ 0, 1, 1])
> seven = Bitvector([1, 1, 1])
> two = Bitvector([0, 1])
> assert three | six == seven
> assert three & six == two
>
> Which operations are required only inside the extension, and which  
> operations need to be exposed to the user of the extension?
>

The only operations I need are setting bits, getting the bits that  
are not set etc. Nothing too fancy. I am probably going to be the  
only user of this extension as this is research code for now.

> "grow" and "needed" are a little contradictory. Do you want an  
> *exact* size, so that you can do this:
>
> zero = Bitvector(size=20, contents=[0])
> all_ones = ~zero
>
> and know exactly how long the result will be?
>
> What makes you think a long int would grow unconscionably longer  
> than needed? How long is your longest map going to be? In any case,  
> just think int, which morphs seamlessly into long as and when  
> required. A 20-bit map would fit into an int.
>
> Another thing to worth contemplating: given the amount of going- 
> over by Tim Peters that the long int code has had, if long ints  
> waste more memory on leading zeroes than n bits [where n is < 32  
> and could be determined by inspecting the code], then the end of  
> the world is nigh.
>

My bit-vector sizes can vary from 10-bits to 60-bits with an average  
length of around 25-30 bits. So, would a long int be the best way  
then ? I was just worried that I would be wasting too much memory.

> "This" wouldn't be doing the storing. *You* would be [mis]using a  
> byte array as a bit array.
>

Hmm. So, is there a correct way to use array.array for bit vectors?

> *Every* type necessarily has more than one bit of baggage. [Sorry;  
> the cheer squad was hollerin' "Pun! Pun! Pun!"]

I guess I deserved that :)

Thanks again !
Nitin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.copyleft.no/pipermail/pyrex/attachments/20051030/0c331b5e/attachment.html