Three ways of doing packed arrays, of increasing complexity:
Elements with 2^N possible values, packed bitwise, possibly overlapping machine word boundaries. The library handles the bit-shifting and twiddling behind the scenes.
Elements with N possible values, not necessarily a power of two. As many elements as possible are packed into a machine word. The library handles radix conversion of a machine word behind the scenes.
Elements with N possible values, not necessarily a power of two. The entire array is stored as a multi-precision integer then interpreted as base N. The library handles arbitrary precision radix conversion behind the scenes. This is computationally extremely expensive, perhaps for only when space is at a premium.
A hybrid of the latter two is pack a small number of elements into a medium-sized multi-precision chunk, then store the multiple chunks.
No comments :
Post a Comment