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.ESA.2017.16
URN: urn:nbn:de:0030-drops-78309
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7830/
Go to the corresponding LIPIcs Volume Portal

Bille, Philip ; Christiansen, Anders Roy ; Ettienne, Mikko Berggren ; Gørtz, Inge Li

Fast Dynamic Arrays

pdf-format:
LIPIcs-ESA-2017-16.pdf (0.6 MB)

Abstract

We present a highly optimized implementation of tiered vectors, a data structure for maintaining a sequence of n elements supporting access in time O(1) and insertion and deletion in time O(n^e) for e > 0 while using o(n) extra space. We consider several different implementation optimizations in C++ and compare their performance to that of vector and set from the standard library on sequences with up to 10^8 elements. Our fastest implementation uses much less space than set while providing speedups of 40x for access operations compared to set and speedups of 10.000x compared to vector for insertion and deletion operations while being competitive with both data structures for all other operations.

BibTeX - Entry

@InProceedings{bille_et_al:LIPIcs:2017:7830,
  author =	{Philip Bille and Anders Roy Christiansen and Mikko Berggren Ettienne and Inge Li G\ortz},
  title =	{{Fast Dynamic Arrays}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7830},
  URN =		{urn:nbn:de:0030-drops-78309},
  doi =		{10.4230/LIPIcs.ESA.2017.16},
  annote =	{Keywords: Dynamic Arrays, Tiered Vectors}
}

Keywords: Dynamic Arrays, Tiered Vectors
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI