Re: [C++] Array of variables that have size of one bit
From: Martijn Lievaart (m_at_remove.this.part.rtij.nl)
Date: 12/14/03
- Next message: Martijn Lievaart: "Re: [C++] Vector - guaranteed to be contiguous?"
- Previous message: James Connell: "Re: Doesn't Wprk - Is There a Way?"
- In reply to: Aggro: "Re: [C++] Array of variables that have size of one bit"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sun, 14 Dec 2003 21:37:25 +0100
On Sat, 13 Dec 2003 22:53:11 +0000, Aggro wrote:
> Martijn Lievaart wrote:
>
>> Bart and Anthony already gave the direct answer to your question, but I
>> want to step back a bit. Why do you need this? Maybe there are other
>> techniques to achieve the same result.
>>
>> For instance, if at most a few the bits are set, you could use a so called
>> sparse matrix. A sparse matrix records only what positions are set. A
>> straight forward implementation would be to use a vector<long> that holds
>> the positions of the bits that are one. Or if more bits are set, but
>> very clustered, other techniques apply that can give great memory savings.
>> Besides, with these amounts of memory, memory savings translate in speed
>> savings, even if the algorithms get more complex.
>
> Majority of the bits need to be set. But when settings bits it is known
> that they have atleast 1 step between them. The distance changes so much
> that we can call it random. And we basicly go throught the array several
> times and each time we set some bits to 0.
>
> So we just drop bits off and see what we got left when all the loops are
> executed. This can actually take months to complite, because calculation
> is done with large numbers. ( talking about numbers that have more than
> 100 digits, hopefully a lot more ).
>
> So it is possible that we run few loops, drop off few bits, save the
> result and continue calculation next day.
Some random thoughts.
Sounds like a project that has the money to buy a few Gig of memory,
probably even can buy non-i386 machines with larger memoryspace, so space
savings get less interesting. For speed, there are two major factors:
- If you hit the swap, you pay heavily. Just use enough real memory.
- Locality of reference. If operations jump from one cpu-cache page to
another, you also pay heavily, though not as bad as the swap. You may want
to consider your memory access patterns.
But it seems like both considerations are not applicable for your project.
If you are setting/clearing bits all of the time, a raw bitmap is probably
indeed what you want. OTOH, /if/ memory is at a premium, /and/
setting/clearing bits only occurs as the result of large calculations (so
the time it takes is neglectible compared to the calculations), you may
want to look into compressing the bitmap.
Another way to compress the bitmap is with run-length-encoding. As with
the previously mentioned just-record-positions, you'll have to insert and
delete items into the map as bits get set/cleared. So you probably want
something tree-like where you can easily insert a new page.
Whatever method you choose, you can encapsulate the details in a class,
which brings us squarly back to the original question (which has been
answered by others). But if you have the memory, I probably would not
bother with compressing.
HTH,
M4
- Next message: Martijn Lievaart: "Re: [C++] Vector - guaranteed to be contiguous?"
- Previous message: James Connell: "Re: Doesn't Wprk - Is There a Way?"
- In reply to: Aggro: "Re: [C++] Array of variables that have size of one bit"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
