Worst-case-efficient dynamic arrays in practice

TY - GEN

T1 - Worst-case-efficient dynamic arrays in practice

AU - Katajainen, Jyrki

N1 - Conference code: 15

PY - 2016

Y1 - 2016

N2 - 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-wiseallocated pile; (3) sliced array with fixed-capacity slices; and (4) blockwise-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.

AB - 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-wiseallocated pile; (3) sliced array with fixed-capacity slices; and (4) blockwise-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.

UR - http://www.scopus.com/inward/record.url?scp=84977497683&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-38851-9_12

DO - 10.1007/978-3-319-38851-9_12

M3 - Article in proceedings

AN - SCOPUS:84977497683

SN - 978-3-319-38850-2

T3 - Lecture notes in computer science

SP - 167

EP - 183

BT - Experimental Algorithms

A2 - Goldberg, Andrew V.

A2 - Kulikov, Alexander S.

PB - Springer

T2 - 15th International Symposium on Experimental Algorithms

Y2 - 5 June 2016 through 8 June 2016

ER -