Worst-case-efficient dynamic arrays in practice
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 mutu...
Main Author: | |
---|---|
Other Authors: | , |
Format: | Article in Journal/Newspaper |
Language: | English |
Published: |
Springer
2016
|
Subjects: | |
Online Access: | https://curis.ku.dk/portal/da/publications/worstcaseefficient-dynamic-arrays-in-practice(a2ee96f1-21fe-40dc-8388-e41b5785d486).html https://doi.org/10.1007/978-3-319-38851-9_12 http://www.scopus.com/inward/record.url?scp=84977497683&partnerID=8YFLogxK |
id |
ftcopenhagenunip:oai:pure.atira.dk:publications/a2ee96f1-21fe-40dc-8388-e41b5785d486 |
---|---|
record_format |
openpolar |
spelling |
ftcopenhagenunip:oai:pure.atira.dk:publications/a2ee96f1-21fe-40dc-8388-e41b5785d486 2024-06-09T07:49:56+00:00 Worst-case-efficient dynamic arrays in practice Katajainen, Jyrki Goldberg, Andrew V. Kulikov, Alexander S. 2016 https://curis.ku.dk/portal/da/publications/worstcaseefficient-dynamic-arrays-in-practice(a2ee96f1-21fe-40dc-8388-e41b5785d486).html https://doi.org/10.1007/978-3-319-38851-9_12 http://www.scopus.com/inward/record.url?scp=84977497683&partnerID=8YFLogxK eng eng Springer info:eu-repo/semantics/closedAccess Katajainen , J 2016 , Worst-case-efficient dynamic arrays in practice . in A V Goldberg & A S Kulikov (eds) , Experimental Algorithms : 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings . Springer , Lecture notes in computer science , vol. 9685 , pp. 167-183 , 15th International Symposium on Experimental Algorithms , St. Petersborg , Russian Federation , 05/06/2016 . https://doi.org/10.1007/978-3-319-38851-9_12 contributionToPeriodical 2016 ftcopenhagenunip https://doi.org/10.1007/978-3-319-38851-9_12 2024-05-16T11:29:16Z 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. Article in Journal/Newspaper The Pointers University of Copenhagen: Research 167 183 |
institution |
Open Polar |
collection |
University of Copenhagen: Research |
op_collection_id |
ftcopenhagenunip |
language |
English |
description |
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. |
author2 |
Goldberg, Andrew V. Kulikov, Alexander S. |
format |
Article in Journal/Newspaper |
author |
Katajainen, Jyrki |
spellingShingle |
Katajainen, Jyrki Worst-case-efficient dynamic arrays in practice |
author_facet |
Katajainen, Jyrki |
author_sort |
Katajainen, Jyrki |
title |
Worst-case-efficient dynamic arrays in practice |
title_short |
Worst-case-efficient dynamic arrays in practice |
title_full |
Worst-case-efficient dynamic arrays in practice |
title_fullStr |
Worst-case-efficient dynamic arrays in practice |
title_full_unstemmed |
Worst-case-efficient dynamic arrays in practice |
title_sort |
worst-case-efficient dynamic arrays in practice |
publisher |
Springer |
publishDate |
2016 |
url |
https://curis.ku.dk/portal/da/publications/worstcaseefficient-dynamic-arrays-in-practice(a2ee96f1-21fe-40dc-8388-e41b5785d486).html https://doi.org/10.1007/978-3-319-38851-9_12 http://www.scopus.com/inward/record.url?scp=84977497683&partnerID=8YFLogxK |
genre |
The Pointers |
genre_facet |
The Pointers |
op_source |
Katajainen , J 2016 , Worst-case-efficient dynamic arrays in practice . in A V Goldberg & A S Kulikov (eds) , Experimental Algorithms : 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings . Springer , Lecture notes in computer science , vol. 9685 , pp. 167-183 , 15th International Symposium on Experimental Algorithms , St. Petersborg , Russian Federation , 05/06/2016 . https://doi.org/10.1007/978-3-319-38851-9_12 |
op_rights |
info:eu-repo/semantics/closedAccess |
op_doi |
https://doi.org/10.1007/978-3-319-38851-9_12 |
container_start_page |
167 |
op_container_end_page |
183 |
_version_ |
1801382862443773952 |