Document Open Access Logo

On-the-Fly Array Initialization in Less Space

Authors Torben Hagerup, Frank Kammer

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2017.44.pdf
  • Filesize: 0.5 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • data structures
  • space efficiency
  • constant-time initialization
  • on-the-fly initialization
  • arrays

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Torben Hagerup and Frank Kammer. On-the-Fly Array Initialization in Less Space. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 44:1-44:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.44

Author Details

Torben Hagerup
Frank Kammer

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google Scholar
  2. Andrei Alexandrescu. The D Programming Language. Addison-Wesley, 2010. Google Scholar
  3. D. Angluin and L. G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. Syst. Sci., 18(2):155-193, 1979. URL: http://dx.doi.org/10.1016/0022-0000(79)90045-X.
  4. Amos Fiat, J. Ian Munro, Moni Naor, Alejandro A. Schäffer, Jeanette P. Schmidt, and Alan Siegel. An implicit data structure for searching a multikey table in logarithmic time. J. Comput. Syst. Sci., 43(3):406-424, 1991. URL: http://dx.doi.org/10.1016/0022-0000(91)90022-W.
  5. Gianni Franceschini and Roberto Grossi. No sorting? Better searching! ACM Trans. Algorithms, 4(1):2:1-2:13, 2008. URL: http://dx.doi.org/10.1145/1328911.1328913.
  6. Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci., 47(3):424-436, 1993. URL: http://dx.doi.org/10.1016/0022-0000(93)90040-4.
  7. Kimmo Fredriksson and Pekka Kilpeläinen. Practically efficient array initialization. J. Softw. Pract. Exper., 46(4):435-467, 2016. URL: http://dx.doi.org/10.1002/spe.2314.
  8. James Gosling, Bill Joy, Guy Steele, Gilad Bracha, and Alex Buckley. The Java Language Specification, Java SE 8 Edition. Oracle America, 2015. Google Scholar
  9. Torben Hagerup. Sorting and searching on the word RAM. In Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998), volume 1373 of LNCS, pages 366-398. Springer, 1998. URL: http://dx.doi.org/10.1007/BFb0028575.
  10. Torben Hagerup and Frank Kammer. Succinct choice dictionaries. Computing Research Repository (CoRR), arXiv:1604.06058 [cs.DS], 2016. URL: http://arxiv.org/abs/1604.06058.
  11. Torben Hagerup and Frank Kammer. On-the-fly array initialization in less space. Computing Research Repository (CoRR), arXiv:1709.10477 [cs.DS], 2017. URL: http://arxiv.org/abs/1709.10477.
  12. IEC/IEEE International Standard; Behavioural languages - Part 1-1: VHDL Language Reference Manual. IEC 61691-1-1:2011(E) IEEE Std 1076-2008, 2011. URL: http://dx.doi.org/10.1109/IEEESTD.2011.5967868.
  13. Takashi Katoh and Keisuke Goto. In-place initializable arrays. Computing Research Repository (CoRR), arXiv:1709.08900 [cs.DS], 2017. URL: http://arxiv.org/abs/1709.08900.
  14. J. Ian Munro. An implicit data structure supporting insertion, deletion, and search in O(log² n) time. J. Comput. Syst. Sci., 33(1):66-74, 1986. URL: http://dx.doi.org/10.1016/0022-0000(86)90043-7.
  15. Gonzalo Navarro. Spaces, trees, and colors: The algorithmic landscape of document retrieval on sequences. ACM Comput. Surv., 46(4):52:1-52:47, 2014. URL: http://dx.doi.org/10.1145/2535933.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact