Most efficient way of storing 1024*1024 bits

[Steven D'Aprano]

On Wed, 02 Nov 2005 13:55:10 +0100, Tor Erik Sønvisen wrote:

> Hi
> 
> I need a time and space efficient way of storing up to 6 million bits. 

[inserts pinky in corner of mouth]

Six MILLION bits!!!

That's almost 750K. Are you sure your computer will handle that much data?


> Time 
> efficency is more important then space efficency as I'm going to do searches 
> through the bit-set.

Could you be more vague if you tried? Searching for what? Does your data
have structure you can exploit? Can you put it in a tree structure? Are
you going to be inserting and deleting data?

If you can handle your six million bits in lots of eight, store them as a
character string.

If you can keep your data sorted, then you can do binary searches instead
of linear searches. If your data is hashable, you can store it in a
dictionary and potentially get up to constant-time search speeds.

Or forget about manipulating bits, and just store your data as bools in
a list.

Explain your problem a little better, and you may get some better advice.


-- 
Steven.