On-the-fly array initialization in less space

DOI10.4230/LIPICS.ISAAC.2017.44zbMATH Open1457.68074arXiv1709.10477OpenAlexW2963670382MaRDI QIDQ5136264FDOQ5136264

Torben Hagerup, Frank Kammer

Publication date: 25 November 2020

Abstract: We show that for all given $n,t,win1,2,\mathrm{...}$ 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+lceiln(t/(2w){)}^{t}ceil$ 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+lceiln/w^{t}ceil$ 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(logn)$-time access with just $nw+1$ bits, which is optimal for arbitrary access times if the initialization executes fewer than $n$ steps.

Full work available at URL: https://arxiv.org/abs/1709.10477

Recommendations

• Extra space during initialization of succinct data structures and dynamical initializable arrays
• Compact dynamic rewritable (CDRW) arrays
• scientific article; zbMATH DE number 1830754
• scientific article; zbMATH DE number 2185599
• scientific article

zbMATH Keywords

data structuresarraysspace efficiencyconstant-time initializationon-the-fly initialization

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Title not available (Why is that?)
• Spaces, Trees, and Colors
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Surpassing the information theoretic bound with fusion trees
• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• No sorting? better searching!
• An implicit data structure for searching a multikey table in logarithmic time
• Space-Efficient Euler Partition and Bipartite Edge Coloring

Cited In (4)

• In-place initializable arrays
• Space-efficient vertex separators for treewidth
• Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays.
• Inferring complete initialization of arrays

This page was built for publication: On-the-fly array initialization in less space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136264)