LIPIcs.ISAAC.2017.44.pdf
- Filesize: 0.5 MB
- 12 pages
Document
On-the-Fly Array Initialization in Less Space
Authors
-
Part of:
Volume:
28th International Symposium on Algorithms and Computation (ISAAC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-07
Cite AsGet 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
https://doi.org/10.4230/LIPIcs.ISAAC.2017.44
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.
Keywords
- data structures
- space efficiency
- constant-time initialization
- on-the-fly initialization
- arrays
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
-
Andrei Alexandrescu. The D Programming Language. Addison-Wesley, 2010.
- 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.
- 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.
- 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.
- 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.
- 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.
-
James Gosling, Bill Joy, Guy Steele, Gilad Bracha, and Alex Buckley. The Java Language Specification, Java SE 8 Edition. Oracle America, 2015.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.