Friday, June 05, 2015

[jlexsgxt] Packed array

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 :