Fast Dynamic Arrays

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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

458 Downloads (Pure)

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) for > 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 108 elements. Our fastest implementation uses much less space than set while providing speedups of 40× for access operations compared to set and speedups of 10.000× compared to vector for insertion and deletion operations while being competitive with both data structures for all other operations.
Original languageEnglish
Title of host publicationProceedings of 5th Annual European Symposium on Algorithms
Publication date2017
Pages16:1--16:13
ISBN (Print)978-3-95977-049-1
DOIs
Publication statusPublished - 2017
Event25th European Symposium on Algorithms (ESA 2017) - Vienna, Austria
Duration: 4 Sept 20176 Sept 2017

Conference

Conference25th European Symposium on Algorithms (ESA 2017)
Country/TerritoryAustria
CityVienna
Period04/09/201706/09/2017

Keywords

  • Dynamic Arrays
  • Tiered Vectors

Fingerprint

Dive into the research topics of 'Fast Dynamic Arrays'. Together they form a unique fingerprint.

Cite this