Practically efficient array initialization
Kimmo Fredriksson, Pekka Kilpeläinen · Software Practice and Experience · 2015
Initialization of an array, out of which only a small initially unknown portion will eventually be used, is a frequent need in programming. A folklore solution for initializing an array of n entries in constant time uses 2n⌈log2n⌉ extra bits to realize a stack of back pointers to the actually used entries of the array. Navarro has given a succinct version of this technique, which requires only n + o(n) bits of auxiliary storage. We describe, analyze, and experimentally compare these solutions and their space-efficient but theoretically suboptimal alternatives based on a simple bitmap for keeping track of the array entries which have been assigned a value. Experimental results suggest that each of the methods has its niche of excellence, which are roughly as follows: the theoretically optimal solutions based on a stack of back pointers perform in general best on sparse arrays, whose access frequency is less than 1% of the number of their entries. Brute-force initialization of the entire array seems generally to give the best overall performance for dense arrays whose access frequency is over 10% of their size. For the remaining cases of arrays with 1–10% access frequency, the methods which use a simple bitmap appear to give the best performance. The experiments show that the choice of a suitable implementation may yield substantial, up to hundreds of times speed-ups in the performance of initializable array operations. Copyright © 2015 John Wiley & Sons Ltd.