Most efficient way of storing 1024*1024 bits

[Tor Erik Sønvisen]

Hi

I need a time and space efficient way of storing up to 6 million bits. Time
efficency is more important then space efficency as I'm going to do searches
through the bit-set.

regards tores

[bonono]

C ?

Tor Erik Sønvisen wrote:

Hi

I need a time and space efficient way of storing up to 6 million bits. Time
efficency is more important then space efficency as I'm going to do searches
through the bit-set.

regards tores

[Paul Rubin]

"Tor Erik Sønvisen" <to***@stud.cs. uit.no> writes:

I need a time and space efficient way of storing up to 6 million bits. Time
efficency is more important then space efficency as I'm going to do searches
through the bit-set.

Umm, what kind of searches do you want to do? For speed you want to
use built-in functions wherever you can, string.find and that kind of
thing. So choose your data format accordingly.

[Mike Meyer]

"Tor Erik Sønvisen" <to***@stud.cs. uit.no> writes:

I need a time and space efficient way of storing up to 6 million bits. Time
efficency is more important then space efficency as I'm going to do searches
through the bit-set.

Six megabytes is pretty much nothing on a modern computer. I'd store
the things as a string of "0" and "1", and then use .find (or maybe
the in keyword) for doing the searches.

This doesn't work very well if you're going to mutate the string,
though.

<mike
--
Mike Meyer <mw*@mired.or g> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

[Paul Rubin]

Mike Meyer <mw*@mired.or g> writes:

Six megabytes is pretty much nothing on a modern computer. I'd store
the things as a string of "0" and "1", and then use .find (or maybe
the in keyword) for doing the searches.

This doesn't work very well if you're going to mutate the string,
though.

You can use re.search on array.array byte vectors. I don't know how
the speed compares with string.find.

[Alex Martelli]

Paul Rubin <http://ph****@NOSPAM.i nvalid> wrote:
...

You can use re.search on array.array byte vectors. I don't know how
the speed compares with string.find.
Pretty well, though of course one should measure on representative cases
for one's specific application needs:

Helen:~ alex$ python -mtimeit -s'import re, array' -s'x=999999*"x"'
-s'x=x+"a"+x' \ 'x.find("a")'

100 loops, best of 3: 13.3 msec per loop

Helen:~ alex$ python -mtimeit -s'import re, array' -s'x=999999*"x"'
-s'x=x+"a"+x' 're.search("a", x)'
100 loops, best of 3: 8.73 msec per loop

Helen:~ alex$ python -mtimeit -s'import re, array' -s'x=999999*"x"'
-s'x=x+"a"+x' -s'x=array.array ("c",x)' 're.search("a", x)'
100 loops, best of 3: 8.72 msec per loop
Alex

[Bengt Richter]

On Wed, 2 Nov 2005 13:55:10 +0100, "Tor Erik Sønvisen" <to***@stud.cs. uit.no> wrote:

Hi

I need a time and space efficient way of storing up to 6 million bits. Time
efficency is more important then space efficency as I'm going to do searches
through the bit-set.

Very dependent on what kind of "searches" -- e.g., 1024*1024 suggests the
possibility of two dimensions. Quad-trees? How sparse is the data? Etc.
What kinds of patterns are you going to search for?

Regards,
Bengt Richter

[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.

[Dan Bishop]

Tor Erik Sønvisen wrote:

Hi

I need a time and space efficient way of storing up to 6 million bits.
The most space-efficient way of storing bits is to use the bitwise
operators on an array of bytes:

import array

class BitList(object) :
def __init__(self, data=None):
self._data = array.array('B' )
self._length = 0
if data is not None:
self.extend(dat a)
def __len__(self):
return self._length
def __getitem__(sel f, index):
if index < 0:
index += self._length
if index < 0 or index >= self._length:
raise IndexError('Bit List index out of range')
byte_index, bit_index = divmod(index, 8)
return int(bool(self._ data[byte_index] & (1 << bit_index)))
def __setitem__(sel f, index, value):
if index < 0:
index += self._length
if index < 0 or index >= self._length:
raise IndexError('Bit List index out of range')
byte_index, bit_index = divmod(index, 8)
byte = self._data[byte_index]
bitmask = 1 << bit_index
byte &= ~bitmask & 0xFF
if value:
byte |= bitmask
self._data[byte_index] = byte
def __repr__(self):
return 'BitList([%s])' % ', '.join(str(bit) for bit in self)
def append(self, value):
if not self._length % 8:
self._data.appe nd(0)
self._length += 1
self[-1] = value
def extend(self, values):
for v in values:
self.append(v)
Time efficency is more important then space efficency
In that case, you're better off simply using a list of bools.
as I'm going to do searches through the bit-set.

What kind of searches?

[Brandon K]

BTW, it'd be 6 megabits or 750kb ;)

Six megabytes is pretty much nothing on a modern computer.

----== Posted via Newsgroups.com - Usenet Access to over 100,000 Newsgroups ==----
Get Anonymous, Uncensored, Access to West and East Coast Server Farms!
----== Highest Retention and Completion Rates! HTTP://WWW.NEWSGROUPS.COM ==----