License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.44
URN: urn:nbn:de:0030-drops-82527
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8252/
Hagerup, Torben ;
Kammer, Frank
On-the-Fly Array Initialization in Less Space
Abstract
We show that for all given n,t,w in {1,2,...} with n<2^w, an array of n entries of w bits each can be represented on a word RAM with a word length of w bits in at most nw+ceil(n(t/(2 w))^t) bits of uninitialized memory to support constant-time initialization of the whole array and O(t)-time reading and writing of individual array entries. At one end of this tradeoff, we achieve initialization and access (i.e., reading and writing) in constant time with nw+ceil(n/w^t) bits for arbitrary fixed t, to be compared with nw+Theta(n) bits for the best previous solution, and at the opposite end, still with constant-time initialization, we support O(log n)-time access with just nw+1 bits, which is optimal for arbitrary access times if the initialization executes fewer than n steps.
BibTeX - Entry
@InProceedings{hagerup_et_al:LIPIcs:2017:8252,
author = {Torben Hagerup and Frank Kammer},
title = {{On-the-Fly Array Initialization in Less Space}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {44:1--44:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-054-5},
ISSN = {1868-8969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8252},
URN = {urn:nbn:de:0030-drops-82527},
doi = {10.4230/LIPIcs.ISAAC.2017.44},
annote = {Keywords: data structures, space efficiency, constant-time initialization, on-the-fly initialization, arrays}
}
Keywords: |
|
data structures, space efficiency, constant-time initialization, on-the-fly initialization, arrays |
Collection: |
|
28th International Symposium on Algorithms and Computation (ISAAC 2017) |
Issue Date: |
|
2017 |
Date of publication: |
|
07.12.2017 |