| Worst-case-efficient dynamic arrays in practice | |
| Author: | Jyrki Katajainen |
| Published in: | Proceedings of the 15th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 9685, Springer (2016), 167–183 |
| Full text: |  PDF (303 kB) |
| DOI: | 10.1007/978-3-319-38851-9_12 |
| Copyright: | © Springer International Publishing Switzerland |
| Abstract: | The basic operations of a dynamic array are
operator[], push_back, and
pop_back. This study is an examination of
variations of dynamic arrays that support these operations at O(1)
worst-case cost. In the literature, many solutions have been proposed,
but little information is available on their mutual superiority. Most
library implementations only guarantee O(1) amortized cost per
operation. Four variations with good worst-case performance were
benchmarked: (1) resizable array relying on doubling, halving, and
incremental copying; (2) level-wise-allocated pile; (3) sliced array
with fixed-capacity slices; and (4) block-wise-allocated pile. Let
|V| denote the size of the values of type V and
|V*| the size of the pointers to values of type V,
both measured in bytes. For an array of n values and a slice of S
values, the space requirements of the considered variations were at
most 12 |V| n + O(|V*|), 2 |V| n +
O(|V*| lg n), |V| (n + S) + O(|V*|
n / S), and |V| n + O((|V| + |V*| +
|V**|) √n) bytes, respectively. A sliced array that
uses a few per cent of extra space turned out to be a reasonable
solution in practice. In general, for worst-case-efficient
variations, the operations were measurably slower than those for the
C++ standard-library implementation. Moreover, slicing can
make the structures fragile, so measures to make them more robust
are proposed. |
| Related: |  HTML (Source code) HTML (Slides) |
| BibLATEX: | @inproceedings{Kat2016C,
author = {Jyrki Katajainen},
title = {Worst-case-efficient dynamic arrays in practice},
booktitle = {Proceedings of the 15th International Symposium on Experimental
Algorithms},
series = {Lecture Notes in Computer Science},
volume = {9685},
publisher = {Springer},
year = {2016},
pages = {167--183},
}
|