arXiv:1711.00275cs.DS
Fast Dynamic Arrays
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
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 multiset from the standard library on sequences with up to $10^8$ elements. Our fastest implementation uses much less space than multiset while providing speedups of $40\times$ for access operations compared to multiset and speedups of $10.000\times$ compared to vector for insertion and deletion operations while being competitive with both data structures for all other operations.
This is cool. I wanted to comment on the necessity of knowing the approximate size of N a priori, but this is very clearly stated on the github page. Interesting alternatives that also support insertion, deletion, and lookup (is there a name for this interface?) are AVL trees…
meukView on HNParent context