Re: Compact Data

From: pinkfloydhomer_at_[hidden]
Date: 2001-03-19 08:10:18

--- In boost_at_y..., Michiel Salters <Michiel.Salters_at_c...> wrote:
> std::vector<bool> is probably the most efficient way to stuff any 
random
> number of bits into the smallest space, without domain-specific
> knowledge. 
> 

No. Handling all the dirty details oneself and packing everything 
into ints with bitwise operations is the most effecient way. This is 
not a big problem, but it might as well be encapsulated so no one 
have to reinvent this with all the bugs that follow and all the time 
that is wasted.

> But this might be quite inefficient for hash-tables. Optimizing 
space-time
> tradeoffs is very implementation-dependant. E.g. misaligned reads 
are
> more expensive on Sparcs than on x86 , so stuffing 5 bytes of data
> in 8 bytes of memory might or might not be the fastest solution.
> 
> W.r.t. to your general claim, I'd argue that the ability to store 
data
> efficiently in memory is of limited use: most programs just don't 
need
> that much data at a time. That allows the use of virtual memory.
> 
> Michiel Salters

I am talking about the case where a design decision has been made 
that favors low space complexity _far_ higher than low time 
complexity. Dynamic Programming designs in general are good examples: 
If you have just performed some exponential-time search of some 
space, and you want to save your the result for later use (which is 
the general idea in DP) you don't care if your lookups have high 
constant access times. 

The point is that one should be able to make a design decision such 
as the above (a Dynamic Programming design), without the 
implementation being a problem.