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
> number of bits into the smallest space, without domain-specific
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
> tradeoffs is very implementation-dependant. E.g. misaligned reads
> 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
> efficiently in memory is of limited use: most programs just don't
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk