z-logo
Premium
Practically efficient array initialization
Author(s) -
Fredriksson Kimmo,
Kilpeläinen Pekka
Publication year - 2016
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.2314
Subject(s) - initialization , computer science , programming language
Summary 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 2 n ⌈log2 n ⌉ 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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here